Project Euler - Problem 17

It's been to long since I posted a solution to one of these challenges. How time flies when you're having fun.

Here's the problem:
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?

Here is the python code:

  1. #!/usr/bin/env python
  3. ones = {'1': 'one', '2': 'two', '3': 'three', '4': 'four', '5': 'five',
  4. '6': 'six', '7': 'seven', '8': 'eight', '9': 'nine', '0': ''}
  6. tens = {'2': 'twenty', '3': 'thirty', '4': 'forty', '5': 'fifty',
  7. '6': 'sixty', '7': 'seventy', '8': 'eighty', '9': 'ninety'}
  9. teens = {'10': 'ten', '11': 'eleven', '12': 'twelve', '13': 'thriteen',
  10. '14': 'fourteen', '15': 'fifteen', '16': 'sixteen', '17': 'seventeen',
  11. '18': 'eighteen', '19': 'nineteen'}
  13. hundreds = {0: 0, 1: "onehundredand", 2: "twohundredand",
  14. 3: "threehundredand", 4: "fourhundredand",
  15. 5: "fivehundredand", 6: "sixhundredand",
  16. 7: "sevenhundredand", 8: "eighthundredand",
  17. 9: "ninehundredand" }
  19. if __name__ == "__main__":
  20. tot = 0
  21. for h in xrange(10):
  22. for y in xrange(1,100):
  23. try:
  24. t,o = tuple(str(y))
  25. if t is '1':
  26. tot += len("{h}{t}".format(h=hundreds[h], t=teens[t + o]))
  27. else:
  28. tot += len("{h}{t}{o}".format(h=hundreds[h], t=tens[t],
  29. o=ones[o]))
  30. except ValueError:
  31. tot += len("{h}{o}".format(h=hundreds[h], o=ones[str(y)]))
  32. tot += len('onethousand')
  33. print tot

Even though I wrote it, I still look at it and think "that's not mine." It's been a long time since I wrote a for loop within a for loop. There isn't anything wrong with it, it's just not my style. This time however I wasn't really able to come up with a solution that would allow me to break out of the two for loops.

The one part of the code that I was surprised "worked" war breaking up the digits by turning the number to a string then a tuple. This allowed me to easily test an exception. This exception will only be thrown 10% of the time. While exceptions might be expensive, the other 90% of the time the code hums along without using a conditional. Everything has costs, but I think that the cost of throwing an exception 10% of the time as opposed to testing a conditional 100% of the time is a cost I'm willing to accept.

I will admit that I did not code up another solution in a different programming language. While part of that is due to being lazy - it's good for the soul once and a while - I'm also not sure how I can code this up in a functional language. I'm sure it can be done, I just don't know how (If anyone has a link or idea please share it.) But because I do like to compare things I tweaked the code to run within python 3.3.0. The differences in time are so minimal that I'm not even going to post it. If you're really inspired you can read the python 3 code here.

Questions and comments welcomed. One quick side note to my readers: I'm getting married this year (Yay!) and a lot of my free time is spent juggling and planning. So I might not be blogging as frequently as usual. Thanks for your patience.

If you made it this far down into the article, hopefully you liked it enough to share it with your friends. Thanks if you do, I appreciate it.

Bookmark and Share