Beginner Programming Challenge #9

[cprofitt]

This is my final try with python:
It now attempts to determine if it should process the whole file at once or in chunks to conserver memory. Maybe one day I can figure out a good way to check free memory from within the program, so it can compensate automatically (and not cause the system to swap)

Interesting code.

I liked the time to completion code... very nice.

[Sinkingships7]

Last call for programs. I will begin judging tomorrow. If you need more time, don't hesitate to send me a PM or post here.

[Lux Perpetua]

I'm not a beginner in any reasonable definition, but there's no real possibility of someone copying this and getting away with it. I recently started learning ARM assembly for fun, and I used this as an exercise to help me along. To run this, if you don't run an ARM system, you'll need (1) an ARM assembler, (2) an ARM linker, and (3) an ARM user-space emulator. There are no other dependencies (not even libC). On Arch Linux, you can get (1) and (2) from the package cross-arm-elf-binutils, but there probably isn't a Ubuntu equivalent. It looks like you can get them from here, though:

http://www.gnuarm.com/

The qemu emulator, which hopefully has a Ubuntu package, includes ARM support via the program qemu-arm (item (3) in my list).

Some notes about the code:

The integer division instruction isn't standard on ARM processors. Integer division (by 10, specifically) is actually pretty useful if you want to print out integers in base 10. I wrote my own "print_int" function, which requires a "div10" function for division by 10, which I also wrote.

There's one more cool thing I'd like to point out about the code, something you can only do in assembly language, and can't do without considerable difficulty unless all instructions have the same size in memory. (All ARM instructions are 4 bytes long, and "Thumb"-mode instructions, which I used for the code table (explained in the next sentence), are 2 bytes long.) I made a table of blocks of instructions, and I use the input character as an index into it to select the right behavior. For input characters '0', ..., '9', the corresponding block will update the running digit sum. For inputs 'a', ..., 'z', the corresponding code block will increment the counter (in a table) for that letter. For all other characters, the block does nothing. (Actually, I slightly lied that this can only be done in assembly language: in theory, a switch/case construct in C or C++ could be compiled to a similar structure. However, this is completely at the compiler's discretion, so it doesn't really count, since you can't implement it directly.)

I won't say the rest is self-explanatory, since it's still assembly, but hopefully the comments will guide any interested readers.

        .section .data
        
        /* For output */
error_msg1:
        .ascii "No file specified\n"
error_msg1_end:
        error_msg1_length = (error_msg1_end - error_msg1)
        
error_msg2:
        .ascii "Couldn't find file\n"
error_msg2_end:
        error_msg2_length = (error_msg2_end - error_msg2)

string1:
        .ascii "Sum = "
string2:
        .skip 1
        .ascii  " = "

        .align 2
        
        .arm
        
        /* This table will count the occurrences of each letter */
count_table:
        .skip   26*4

        .align 2
        .global _start

        /* Program entry point */
_start:
        /* [sp] = argc, [sp+4] = argv[0], [sp+8] = argv[1], etc. */
        ldr     r0, [sp]                
        cmp     r0, #2
        bge     argc_okay

        /* Too few command-line arguments were given */
        mov     r0, #2                  @ 2 for stderr
        adr     r1, error_msg1
        mov     r2, #error_msg1_length
        swi     0x900004                @ `write' syscall
        
        mov     r0, #1
        swimi   0x900001                @ `exit' syscall

argc_okay:      
        ldr     r0, [sp, #8]            @ filename from argv[1]
        mov     r1, #0                  @ 0 = O_RDONLY
        swi     0x900005                @ open syscall
        movs    r8, r0                  @ r8 = file desc. for reading
        bpl     open_okay
        
        /* There was an error opening the file */
        mov     r0, #2                  @ 2 for stderr
        adr     r1, error_msg2
        mov     r2, #error_msg2_length
        swi     0x900004                @ `write' syscall

        mov     r0, #1
        swimi   0x900001                @ `exit' syscall


open_okay:     
        mov     r5, #0                  @ r5 tracks the sum of digits
        adr     r7, count_table
        adr     r6, loop1_begin

        /* We'll put each input character on the stack.
         * Technically, we only need a byte for this, but
         * the APCS stipulates that sp should always be word-aligned.
         */

        sub     sp, sp, #4              @ space for input
        
loop1_begin:   
        mov     r0, r8                  @ file descriptor for reading
        mov     r1, sp                  @ input destination
        mov     r2, #1                  @ input size (1 byte)
        swi     0x900003                @ execute `read' syscall
        subs    r0, r0, #1              @ check return value
        bmi     loop1_end               @ (if we couldn't read anything)
        
        ldrsb   r0, [sp]
        adr     r1, code_table
        movs    r2, r0
        bmi     loop1_begin             @ (if it's outside ASCII range)
        add     r1, r1, r0, LSL #3

        add     r1, r1, #1              @ for thumb mode
        /*  now r1 = code_table + 8*(input byte value) + 1 */

        /* We compute this here to save space in the code table */
        sub     r3, r7, #'a'*4
        add     r3, r3, r2, LSL #2

        bx      r1

        /* This is an array of blocks of executable code,
         * indexed by the input character. Each ASCII character has a
         * block of four thumb instructions (i. e., 8 bytes).
         */

        .thumb

code_table:
        .rept   48                      @ ['\0', '0)
        bx      r6
        .skip   6
        .endr

        .rept   10                      @ ['0', '9']
        sub     r2, #'0'
        add     r5, r2
        bx      r6
        .skip   2
        .endr
        
        .rept   39                      @ ('9', 'a')
        bx      r6
        .skip   6
        .endr

        .rept   26                      @ ['a', 'z']
        ldr     r1, [r3]
        add     r1, #1
        str     r1, [r3]
        bx      r6
        .endr

        .rept   5                       @ ('z', 0x7f]
        bx      r6
        .skip   6
        .endr
        
        .arm
        
loop1_end:
        mov     r0, #1                  @ 1 for stdout
        adrl    r1, string1
        mov     r2, #6
        swi     0x900004                @ `write' syscall

        mov     r0, r5
        bl      print_int
        bl      newline

        /* There's probably a more elegant way to set up
         * this loop...
         */
        mov     r4, #26
        add     r7, r7, #26 * 4
loop2_begin:
        sub     r1, r7, r4, LSL #2
        ldr     r6, [r1]

        /* Don't print anything if the count is zero */
        movs    r6, r6
        beq     loop2_test
        
        rsb     r0, r4, #'z'+1
        adrl    r1, string2
        strb    r0, [r1]

        mov     r0, #1
        mov     r2, #4
        swi     0x900004

        mov     r0, r6
        bl      print_int
        bl      newline
        
loop2_test:     
        subs    r4, r4, #1
        bne     loop2_begin
        
        mov     r0, #0
        swi     0x900001                @ `exit' syscall


        /* Auxiliary functions */

buffer:
        .skip 36
buffer_end:

        .align 2
        /* prints out r0 (in base 10) */
print_int:
        stmfd   r13!, {r4-r8, r10, r11, r14}

        movs    r5, r0
        rsbmi   r0, r0, #0
        
        adr     r4, buffer_end
dec_digits_loop:
        bl      div10
        
        add     r1, r1, #'0'
        strb    r1, [r4, #-1]!
        cmp     r0, #0
        bne     dec_digits_loop

        mov     r1, #'-'
        cmp     r5, #0
        strmib  r1, [r4, #-1]!

        mov     r0, #1
        mov     r1, r4
        adr     r2, buffer_end
        sub     r2, r2, r4
        swi     0x900004

        ldmfd   r13!, {r4-r8, r10, r11, r14}
        mov     pc, lr

        
        /* (r0, r1) = (r0 div 10, r0 mod 10)
         * This is a quick hack to divide an integer by 10.
         */
div10:
        mov     r2, r0
        
        mov     r0, r0, ASR #4
        add     r0, r0, ASR #1
        add     r0, r0, r0, ASR #4
        add     r0, r0, r0, ASR #8
        add     r0, r0, r0, ASR #16
        
        mov     r1, r0, LSL #1
        add     r1, r1, r0, LSL #3

        sub     r1, r2, r1
div10_correct_loop:
        subs    r1, r1, #10
        addpl   r0, r0, #1
        bpl     div10_correct_loop

        add     r1, #10
        mov     pc, lr

        
nl:
        .byte '\n'

        .align 2
        /* prints '\n'. Does not modify registers. */
newline:
        stmfd   r13!, {r0-r4, r14}
        
        mov     r0, #1
        adr     r1, nl
        mov     r2, #1
        swi     0x900004

        ldmfd   r13!, {r0-r4, r14}
        mov     pc, lr

To assemble:

arm-elf-as -o beginners_09.o beginners_09.s
arm-elf-ld -s -Ttext-segment 54 -o b09 beginners_09.o

(The prefix "arm-elf-" might be different for you, and you can omit the arguments -s -Ttext-segment 54 to the linker if you don't mind a larger executable.) To run:

qemu-arm b09 <filename>

There may be a few bugs, but it seems to work on the few files I tested it on. Also, it uses unbuffered input (making a separate syscall to read() for each byte), which probably hurts performance a bit. Implementing buffered input directly in ARM assembly would be a good exercise, but I didn't do it for this one.

[cprofitt]

Last call for programs. I will begin judging tomorrow. If you need more time, don't hesitate to send me a PM or post here.

Cool... it will be interesting to see the results... and then have the next challenge.

[Sinkingships7]

And the winner of the beginner's programming challenge #8 is...

cprofitt!

I chose his submission because it was to the point, made good use of built-in tools and, most importantly, was well-commented and therefore easy to read and understand by beginners.


Some honorable mentions:

howlingmadhowie for his Scheme implementation and for bringing stimulating conversation to the thread with talks of multithreading and speed.

Bodsda's Python implementation for EXTREMELY well-commented code.

falconindy for his simple-yet-effective C implementation.


It's up to cprofitt to come up with the next challenge. Thanks to all participants. I hope everyone was able to take something away from this challenge!

[s.fox]

Congratulations cprofitt Nicely done

Also well done to all those who entered, I really enjoyed looking through your submissions . I am already looking forward to the next challenge.

-Silver Fox

[Marlonsm]

Congrats for cprofit, and thanks for everybody here, I'm sure many people learned a lot here.

[cprofitt]

Thanks... I am... ah... Wow.

Now to find a good beginners 'problem' to solve.

I hope to have it up in the next 12-24 hours.

[mo.reina]

i know i'm late to the party but wanted to post my code anyway... it's a bit redundant, i've only started learning python...

total = 0
count = 0
final =[]

#open the file and assign its value to the variable "readfile"
readfile = open("file.txt", "r").read()
#loop for every line in "readfile"
for line in readfile:
  #check if line is a digit, if so sums it with the total
  if line.isdigit():
    total = total + int(line)
  #lines that are not digits
  else:
    #deletes if newline is present (avoids the counting of newlines)
    if line == "\n":
      del line
    #places value in temporary var "holder"
    else:
      holder = line
      #checks "readfile" for every instance of the value in the var "holder"
      for item in readfile:
	#increments the number of times the value of "holder" is present
        if item == holder:
          count += 1
      #records the value of "holder" and the number of times it is present
      string = holder, "=", count
      #checks if there is a duplicate in the final list (otherwise the duplicate elements are counted again)
      if string in final:
        del string
      else:
        final.append(string)
      count = 0
print "total = ", total
for line in final:
  print line

[lavinog]

i know i'm late to the party but wanted to post my code anyway... it's a bit redundant, i've only started learning python...

Some things to experiment with:

    total = total + int(line)

can be replaced with:

    total += int(line)

It doesn't change the behavior (not sure if there would be any speed benefits), but it is less code to type.

readfile = open("file.txt", "r").read()

can be replaced with:

readfile = open("file.txt")

same reason as above.

    if line == "\n":
      del line

    if len(line.strip())==0:
      continue

strip removes non-printable characters.
continue will skip to the next value in the for loop (eliminates the need for the else statement, and nested if statements)
del line is a wasted step since it will get reassigned anyway.

You also don't need to copy line into a holder, just continue to use line for your tests:

        if item == line:
          count += 1
      #records the value of "line" and the number of times it is present
      string = line, "=", count

      if string in final:
        del string
      else:
        final.append(string)

      if string not in final:
        final.append(string)

Again, no need to del string...it will be done automatically.

      string = holder, "=", count

Although your string setup works, you may want to learn how to do it this way:

      string = '%s = %s' % (holder, count)

You algorithm works, but it is inefficient. If the input file contains 100 repeated 'a' characters, your algorithm will count all 'a's 100 times.
Instead find a way to count each character once.
Two ways to do this:
make a list of each possible character (a-z) and iterate through the list counting each one.
or
Utilize python's dictionary type and check to see if a character already exists in the dictionary.
You can also just add a list for characters that have already been counted, and check that the character isn't in the list (This will be the easiest to implement in your code without a major rewrite.)