python - Project Euler 17

3
votes

I've been trying to solve Euler 17 and have been running into some trouble. The definition of that problem is:

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

I wrote it in Python, and even after going through the code three or four times I still can't see what the problem is. It's long (I just started learning python, and I've never coded before), but I basically just defined different functions that take different number of digits and count up the number of letters in each. I end up with 21254 and it seems like the actual answer is 21124, so I'm off by exactly 130. Any help would be appreciated. 

# create dict mapping numbers to their
# lengths in English

maps = {}
maps[0] = 0
maps[1] = 3
maps[2] = 3
maps[3] = 5
maps[4] = 4
maps[5] = 4
maps[6] = 3
maps[7] = 5
maps[8] = 5
maps[9] = 4
maps[10] = 3
maps[11] = 6
maps['and'] = 3
maps['teen'] = 4
maps[20] = 6
maps[30] = 6
maps[40] = 5
maps[50] = 5
maps[60] = 6
maps[70] = 7
maps[80] = 6
maps[90] = 6
maps[100] = 7
maps[1000] = 8

# create a list of numbers 1-1000
def int_to_list(number):
    s = str(number)
    c = []
    for digit in s:
        a = int(digit)
        c.append(a)
    return c  # turn a number into a list of its digits
def list_to_int(numList):
    s = map(str, numList)
    s = ''.join(s)
    s = int(s)
    return s


L = []
for i in range(1,1001,1):
    L.append(i)

def one_digit(n):
    q = maps[n]
    return q
def eleven(n):
    q = maps[11]
    return q
def teen(n):
    digits = int_to_list(n) 
    q = maps[digits[1]] + maps['teen']
    return q
def two_digit(n):
    digits = int_to_list(n)
    first = digits[0]
    first = first*10
    second = digits[1]
    q = maps[first] + one_digit(second)
    return q
def three_digit(n):
    digits = int_to_list(n)
    first = digits[0]
    second = digits[1]
    third = digits[2]

    # first digit length
    f = maps[first]+maps[100]

    if second == 1 and third == 1:
        s = maps['and'] + maps[11]
    elif second == 1 and third != 1:
        s = digits[1:]
        s = list_to_int(s)
        s = maps['and'] + teen(s)
    elif second == 0 and third == 0:
        s = maps[0]
    elif second == 0 and third != 0:
        s = maps['and'] + maps[third]
    else:
        s = digits[1:]
        s = list_to_int(s)
        s = maps['and'] + two_digit(s)

    q = f + s
    return q
def thousand(n):
    q = maps[1000]
    return q

# generate a list of all the lengths of numbers

lengths = []


for i in L:
    if i < 11:
        n = one_digit(i)
        lengths.append(n)
    elif i == 11:
        n = eleven(i)
        lengths.append(n)
    elif i > 11 and i < 20:
        n = teen(i)
        lengths.append(n)
    elif i > 20 and i < 100:
        n = two_digit(i)
        lengths.append(n)
    elif i >= 100 and i < 1000:
        n = three_digit(i)
        lengths.append(n)
    elif i == 1000:
        n = thousand(i)
        lengths.append(n)
    else:
        pass

# since "eighteen" has eight letters (not 9), subtract 10
sum = sum(lengths) - 10
print "Your number is: ", sum
1
python

1 Answers

9
votes

Explaining the discrepancy

Your code is riddled with errors:

  1. This is wrong:

    maps[60] = 6

    Contribution to error: +100 (because it affects 60 to 69, 160 to 169, ..., 960 to 969).

  2. Several teenagers are mistaken:

    >>> teen(12)
7
>>> teen(13)
9
>>> teen(15)
8
>>> teen(18)
9

    Contribution to error: +40 (because it affects 12, 13, ..., 112, 113, ..., 918)

  3. And any number of the form x10:

    >>> three_digit(110)
17

    Contribution to error: 9 (because 110, 210, ... 910)

  4. The number 20 is not counted (you consider i < 20 and i > 20 but not i == 20).

    Contribution to error: −6

  5. The number 1000 is written "one thousand" in English but:

    >>> thousand(1000)
8

    Contribution to error: −3

  6. You subtract 10 at the end in an attempt to compensate for one of these errors.

    Contribution to error: −10

Total error: 100 + 40 + 9 − 6 − 3 − 10 = 130.

How you could have avoided these mistakes

By trying to work directly with letter counts you made it really hard for you to check your own work. How many letters are there in "one hundred and ten" again? Is it 17, or is it 16? It would have been much easier for you to test your work if you had adopted a strategy like this: 

unit_names = """zero one two three four five six seven eight nine ten
                eleven twelve thirteen fourteen fifteen sixteen seventeen
                eighteen nineteen""".split()
tens_names = """zero ten twenty thirty forty fifty sixty seventy eighty
                ninety""".split()

def english(n):
    "Return the English name for n, from 0 to 999999."
    if n >= 1000:
        thous = english(n // 1000) + " thousand"
        n = n % 1000
        if n == 0:
            return thous
        elif n < 100:
            return thous + " and " + english(n)
        else:
            return thous + ", " + english(n)
    elif n >= 100:
        huns = unit_names[n // 100] + " hundred"
        n = n % 100
        if n == 0:
            return huns
        else:
            return huns + " and " + english(n)
    elif n >= 20:
        tens = tens_names[n // 10]
        n = n % 10
        if n == 0:
            return tens
        else:
            return tens + "-" + english(n)
    else:
        return unit_names[n]

def letter_count(s):
    "Return the number of letters in the string s."
    import re
    return len(re.findall(r'[a-zA-Z]', s))

def euler17():
    return sum(letter_count(english(i)) for i in range(1, 1001))

With this approach it's easier to check your result:

>>> english(967)
'nine hundred and sixty-seven'