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 if
s 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.
range[...]
?! \$\endgroup\$ – jonrsharpe Nov 8 '14 at 8:54