My take at ProjectEuler #17 - counting counting characters

Question

I tried to tackle #17 problem on Project Euler:

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?

I tried to solve it using dictionary. The code is working fine for n = 99, but the solution for 999 is off by 36. Any ideas on what might be going wrong? Any ideas on how I could make it more efficient?

def number_let_count(n):
    sum_let = 0
    numbers = {0: '', 1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine',
               10: 'ten', 11: 'eleven', 12: 'twelve', 13: 'thirteen', 14: 'fourteen', 15: 'fifteen', 16: 'sixteen', 17: 'seventeen', 18: 'eighteen', 19: 'nineteen'
               ,20: 'twenty', 30: 'thirty', 40: 'forty', 50: 'fifty', 60: 'sixty', 70: 'seventy', 80: 'eighty', 90: 'ninety', 100: 'hundred'}
    for int in range(1,n+1):
        if int in numbers and int != 100:
            sum_let += len(numbers[int])
        else:
            if int in range(21,100):
                sum_let += len(numbers[(int//10) * 10]) + len(numbers[int % 10])
            elif int in range(100,1000):
                if int % 100 == 0:
                    sum_let += len(numbers[(int//100)]) + len(numbers[100])
                else:
                    sum_let += len(numbers[(int//100)]) + len(numbers[100]) + len('and') + len(numbers[((int % 100)//10) * 10]) + len(numbers[(int % 100) % 10]) 
    return sum_let

As your code does not solve strictly speaking solve the problem, it is a bit awkward to review : it would probably be more interesting for you to make the "and" work first because otherwise, comments might not be so helpful. — SylvainD, Nov 8 '14 at 14:35
@jonrsharpe and Josay Fixed. Thanks for pointing out. Apparently drun me thought that it makes it inclusive. — ambitious_roi, Nov 8 '14 at 15:55

SylvainD · Accepted Answer · 2014-11-09 12:53:51Z

A matter of priorities

Make it work, make it right, make it fast : at the moment, your code does not work in that sense that it does not give the solution to the project euler problem.

Nevertheless, I'll try to give you hints to rewrite your code in such a way that it returns the same results as it does currently but in a better way.

In order to do so, I've written a few assertions to be more confident when I perform changes.

assert number_let_count(5) == 19  # given by project euler
assert number_let_count(100) == 864  # found by running your code
assert number_let_count(345) == 6178  # idem
assert number_let_count(1000) == 21077  # idem and we know this result is wrong

Style

You code looks mostly good. Something that I find really confusing (and so does my text editor) is the fact that you named your variable int : i would probably be better.

Then, the logic can be rewritten by removing a level of nesting in the ifs using elif.

Here is what I have at this point :

def number_let_count(n):
    sum_let = 0
    numbers = {0: '', 1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine',
               10: 'ten', 11: 'eleven', 12: 'twelve', 13: 'thirteen', 14: 'fourteen', 15: 'fifteen', 16: 'sixteen', 17: 'seventeen', 18: 'eighteen', 19: 'nineteen'
               ,20: 'twenty', 30: 'thirty', 40: 'forty', 50: 'fifty', 60: 'sixty', 70: 'seventy', 80: 'eighty', 90: 'ninety', 100: 'hundred'}
    for i in range(1,n+1):
        if i in numbers and i != 100:
            sum_let += len(numbers[i])
        elif i in range(21,100):
            sum_let += len(numbers[(i//10) * 10]) + len(numbers[i % 10])
        elif i in range(100,1000):
            if i % 100 == 0:
                sum_let += len(numbers[(i//100)]) + len(numbers[100])
            else:
                sum_let += len(numbers[(i//100)]) + len(numbers[100]) + len('and') + len(numbers[((i % 100)//10) * 10]) + len(numbers[(i % 100) % 10])
    return sum_let

Making debugging easier

Now that you know that your code is wrong, you might as well try to make it easier to debug. My suggestion is to work with strings until the very last moment so that you can print it whenever you need. At the end, you just need to get the length of the string and you are done.

def number_let_count(n):
    numbers = {0: '', 1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine',
               10: 'ten', 11: 'eleven', 12: 'twelve', 13: 'thirteen', 14: 'fourteen', 15: 'fifteen', 16: 'sixteen', 17: 'seventeen', 18: 'eighteen', 19: 'nineteen'
               ,20: 'twenty', 30: 'thirty', 40: 'forty', 50: 'fifty', 60: 'sixty', 70: 'seventy', 80: 'eighty', 90: 'ninety', 100: 'hundred'}
    ret = ""
    and_ = "and"
    for i in range(1,n+1):
        if i in numbers and i != 100:
            ret += numbers[i]
        elif i in range(21,100):
            ret += numbers[(i//10) * 10] + numbers[i % 10]
        elif i in range(100,1000):
            if i % 100 == 0:
                ret += numbers[(i//100)] + numbers[100]
            else:
                ret += numbers[(i//100)] + numbers[100] + and_ + numbers[((i % 100)//10) * 10] + numbers[(i % 100) % 10]
    return len(ret)

This is making your code slower (performing string concatenations instead of additions) but you shouldn't be able to notice this because we are working with pretty small values. Also, this is a first step for an actual optimisations to be performed once it works : you just need to replace whatever involves string with their length variant :

def number_let_count(n):
    numbers = {0: '', 1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine',
               10: 'ten', 11: 'eleven', 12: 'twelve', 13: 'thirteen', 14: 'fourteen', 15: 'fifteen', 16: 'sixteen', 17: 'seventeen', 18: 'eighteen', 19: 'nineteen'
               ,20: 'twenty', 30: 'thirty', 40: 'forty', 50: 'fifty', 60: 'sixty', 70: 'seventy', 80: 'eighty', 90: 'ninety', 100: 'hundred'}
    numbers = {i:len(s) for i,s in numbers.items()}
    ret = 0 # ""
    and_ = len("and")
    for i in range(1,n+1):
        if i in numbers and i != 100:
            ret += numbers[i]
        elif i in range(21,100):
            ret += numbers[(i//10) * 10] + numbers[i % 10]
        elif i in range(100,1000):
            if i % 100 == 0:
                ret += numbers[(i//100)] + numbers[100]
            else:
                ret += numbers[(i//100)] + numbers[100] + and_ + numbers[((i % 100)//10) * 10] + numbers[(i % 100) % 10]
    return ret

Here, 'len' is called only a few times.

I'll keep on working on the "slow" versions because it is a better starting point for your investigations but you know what you can do when it works.

Rewrite interval checks

Computing if i in range(100, 1000) is slow because we'll compare i to many values. What you want to know if just if i is bigger than 100 and (stricly) smaller than 1000. Python has a cool way to write this (you won't find this in all programming languages) : if 100 <= i < 1000.

for i in range(1,n+1):
    if i in numbers and i != 100:
        ret += numbers[i]
    elif 21 <= i < 100:
        ret += numbers[(i//10) * 10] + numbers[i % 10]
    elif 100 <= i < 1000:
        if i % 100 == 0:
            ret += numbers[(i//100)] + numbers[100]
        else:
            ret += numbers[(i//100)] + numbers[100] + and_ + numbers[((i % 100)//10) * 10] + numbers[(i % 100) % 10]

Now, the first check begs to be rewritten as a range check too. A cool thing to notice is that cases such as forty as properly handled by ret += numbers[(i//10) * 10] + numbers[i % 10] because the second term will correspond to "". For that reason, we can simply write : if 0 < i <= 20.

Then successive range checks do not make that much sense : it is probably not interesting checking if i is bigger than 21 if we know it is stricly bigger than 20. Similarly for 100.

Then, the whole logic can be rewritten (adding some logs you might find useful):

for i in range(1,n+1):
    if i < 1:
        print("Oops, did not handle", i)
    elif i <= 20:
        ret += numbers[i]
    elif i < 100:
        ret += numbers[(i//10) * 10] + numbers[i % 10]
    elif i < 1000:
        if i % 100 == 0:
            ret += numbers[(i//100)] + numbers[100]
        else:
            ret += numbers[(i//100)] + numbers[100] + and_ + numbers[((i % 100)//10) * 10] + numbers[(i % 100) % 10]
    else:
        print("Oops, did not handle", i)
return len(ret)

Divisions and modulos

Isn't it a pain to have to perform to operations to have the quotient and the remainder of a division ? It is not anymore with the pretty cool divmod

for i in range(1,n+1):
    if i < 1:
        print("Oops, did not handle", i)
    elif i <= 20:
        ret += numbers[i]
    elif i < 100:
        tens, units = divmod(i, 10)
        ret += numbers[10 * tens] + numbers[units]
    elif i < 1000:
        hundreds, units = divmod(i, 100)
        if units:
            tens, units2 = divmod(units, 10)
            ret += numbers[hundreds] + numbers[100] + and_ + numbers[10 * tens] + numbers[units2]
        else:
            ret += numbers[hundreds] + numbers[100]
    else:
        print("Oops, did not handle", i)

Another hint for one of the bugs

Try to see how "119" gets converted to a string.

Thank you for putting so much time into the answer. I really appreciate it and it helped me a lot. However, I do not really understand how does the "range" differ from setting up an interval? — ambitious_roi, Nov 9 '14 at 19:10
"if a < b < c" compares a to b and if needed b to c. "if b in range(a, c)" compare b to a, then if needed to a+1 then if needed to a+2 then... til c-1. You'll check up to c-a elements. Also, you cannot easily change this to just becomes a "if b < c". — SylvainD, Nov 10 '14 at 8:10

Arvind Padmanabhan · Accepted Answer · 2014-11-09 11:50:37Z

If your goal has been to learn Python from first principles, then your code is okay. I agree with Josay that it can be simplified to reduce calls to len()

If your goal is solve the problem in the quickest possible way, then use can use an existing module named num2words. I used two calls to replace. You can instead use regex but it runs slower. The code is quite simple: we are using list comprehension, getting a generator expression and passing that to sum() function. The hyphen comes because for example, 21 is written as twenty-one.

from num2words import num2words
print(sum(len(num2words(x).replace('-','').replace(' ','')) for x in range(1,1000)))

ambitious_roi · Accepted Answer · 2014-11-08 21:56:07Z

I know what was wrong. There was a problem with 10 < i % 100 < 20. For example, "eleven" was interpreted as "tenone". The fixed version of code can be find below. Please let me know what I could do differently.

def number_let_count(n):
#works only for n<1000
sum_let = 0
numbers = {0: '', 1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine',
           10: 'ten', 11: 'eleven', 12: 'twelve', 13: 'thirteen', 14: 'fourteen', 15: 'fifteen', 16: 'sixteen', 17: 'seventeen', 18: 'eighteen', 19: 'nineteen'
           ,20: 'twenty', 30: 'thirty', 40: 'forty', 50: 'fifty', 60: 'sixty', 70: 'seventy', 80: 'eighty', 90: 'ninety', 100: 'hundred'}
for i in range(1,n+1):
    if i in numbers and i != 100:
        sum_let += len(numbers[i])
    else:
        if i in range(21,100):
            sum_let += len(numbers[(i//10) * 10]) + len(numbers[i % 10])
        elif i in range(100,1000):
            if i % 100 == 0:
                sum_let += len(numbers[(i//100)]) + len(numbers[100])
            else:
                sum_let += len(numbers[(i//100)]) + len(numbers[100]) + len('and')
                if 10<i % 100<20:
                    sum_let += len(numbers[i%100])
                else:
                    sum_let += len(numbers[((i % 100)//10) * 10]) + len(numbers[(i % 100) % 10]) 
return sum_let

I'm glad to see you managed to make this work. You don't really need to post an answer with this. Just to be sure and to save every one some time: this code works, right? — SylvainD, Nov 9 '14 at 0:49
Hi @Josay, yes this code works, but it is probably far from optimal. Thanks for helping me out! I realized what was wrong in the middle of a street haha. — ambitious_roi, Nov 9 '14 at 1:46

Stack Exchange Network

current community

your communities

more stack exchange communities

My take at ProjectEuler #17 - counting counting characters

3 Answers 3

Your Answer

Not the answer you're looking for? Browse other questions tagged python beginner programming-challenge python-3.x numbers-to-words or ask your own question.

Hot Network Questions

My take at ProjectEuler #17 - counting counting characters

3 Answers 3

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged python beginner programming-challenge python-3.x numbers-to-words or ask your own question.

Related

Hot Network Questions