_personalPrez

Project Euler: 17

So today I REALLY wanted to code something, but I had absolutely no idea what to code. Usually, when stricken with such problems I make some nice GUIs, but I just wasn’t feeling that today. So I went back to ol’ Project Euler and decided to solve one of those problems that I COULD do, but didn’t want to dedicate the time to.

Problem 17 deals with converting integers into speakable English. To be more specific, making the following conversions…

2 -> “two”

14 -> “fourteen”

156 -> “one hundred and fifty-six”

Easy? Eh, kinda. It’s more logic than math, especially with the use of “and.” So the problem calls for the total number of letters used to write out all the numbers from 1 to 1,000 (including 1,000). Because I was so intrigued by this math-to-english number parser, I decided to make a library for it. Here’s the source code, written in Python, including comments :)

final = ''

## just some references
prefixes = 'one','two','three','four','five','six','seven'\
           ,'eight','nine','ten','eleven','twelve','thirteen'\
           ,'fourteen','fifteen','sixteen','seventeen','eighteen','nineteen'
tens = 'twenty-','thirty-','forty-','fifty-','sixty-',\
       'seventy-','eighty-','ninety-'

def parse(num, reset = 1):
    global final            # make final global so we can keep using it
    if reset == 1:
        final = ''          # workaround for our recursion-ness
    x = num
    if x > 99:                          # for the hundreds spot
        primeint = int(str(x)[0])
        if x % 100 <> 0:                # test if a multiple of 100
                                        #    (include 'and'?)
            final += (prefixes[primeint - 1] + ' hundred and ')
            parse(x % 100,0)            # recursion  
        else:
            final += (prefixes[primeint - 1] + ' hundred')
    elif x >= 20:                       # deals with tens
        primeint = int(str(x)[0])
        final += tens[primeint - 2]
        parse(x % 10,0)                 # some more recursion
    elif x > 0:                         # finishes off with teens and digits
        final += prefixes[x - 1]
    return final                        # return result

I used a lot of recursion here. Another way to approach this would be to create individual methods for each “step,” sorting out the hundreds, tens, and ones place. Then executing these functions in an appropriate order. I’m cool, so I did recursion.

My code essentially starts by looking for the hundreds spot, adds the appropriate strings, and then parses the remaining number. I kept a global variable, final, which is what contains the entire string.

Now that you have a nifty little parsing function, let’s go back to Project Euler.

## Project Euler 17 Solution by Jordan Scales
## 12/05/09
## If all the numbers from 1 to 1000 (one thousand)
##   inclusive were written out in words, how many letters would be used?

import numparser

total = 0                              # total letters
alpha = 'abcdefghijklmnopqrstuvwxyz'   # check alphabet
count = 1                              # counter

for count in range(1,1000):
    string = numparser.parse(count)    # converts integer to 'string'
    chars = 0
    for char in string:                # checks to see if character is
        if char in alpha:              #   is in the alphabet
            chars+=1                  
    total += chars
    print '%s: %s: %s letters' % (count, string, chars) # diagnostics

total += len('onethousand')            # add 1000 (just a workaround for now)
print '1000: one thousand: %s letters' % len('onethousand')
print 'Total characters: %s' % total

The code’s fairly self explanatory. I have a for loop from 1 to 1000, NOT including. I parse each integer, count the result’s letters - not including dashes!, and add them to a nice total. The output is buggy at parts, for instance “twenty-“. I could code in some workarounds, but I’ll find another way. I printed a lot of diagnostics because of a stupid little bug in the third to last nine, where I actually added ONE MORE character, the space, then I was supposed to.

Now everything works, and I still have a nice little parser for future “projects.” Feel free to use my code and publish it elsewhere, just give yours truly some credit.

Get coding,

/prez