Project Euler-Problem 17

Description

From 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?

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.

Solution

Disclaimer: This problem is one of several that went through several iterations, and I’m still not completely happy with it.However, it works, and produces a result in less than one second, so good enough I guess.

This problem is fairly straight-forward. Simply iterate through all the numbers from one to one thousand and count up the letters. The only real trick is how you figure out how many letters are in each word. So for this problem, lets do something a little different and look at what the end result will be:

(1..1000).reduce(0) { |sum, n| sum + letters_for(n) }

Pretty simple stuff. All we need to do now is define the letters_for method and we're done.

There are only a few actual words used in generating the text representations of the number from one to one thousand. Namely, each of the numbers from one to twenty has its own name. From there each group of ten numbers is just a new word by itself or hyphenated with one of the numbers from one to nine. This keeps going until we get to one hundred, which introduces another new word. And finally, one thousand introduces one more word.

Now that we know we only have a few actual words we need to keep track of, I just stuffed all of those lengths into a hash for easy lookup.

class Problem017
  LETTERS = {
    1 => 3, 2 => 3, 3 => 5, 4 => 4, 5 => 4, 6 => 3, 7 => 5, 8 => 5, 9 => 4, 10 => 3,
    11 => 6, 12 => 6, 13 => 8, 14 => 8, 15 => 7, 16 => 7, 17 => 9, 18 => 8, 19 => 8,
    20 => 6, 30 => 6, 40 => 5, 50 => 5, 60 => 5, 70 => 7, 80 => 6, 90 => 6, 
    100 => 7, 1000 => 8, 0 => 0
  }
end

The last piece is to implement our letters_for method by just adding up the pieces of the text by looking them up in the hash. This is the part I am not very happy with and may change in the future. It just seems very procedural and not very Ruby-esque.

class Problem017
  def letters_for(n)
    sum = 0
    sum += LETTERS[n / 1000] + LETTERS[1000] and n %= 1000 if n >= 1000
    sum += LETTERS[n / 100] + LETTERS[100] and n %= 100 if n >= 100
    sum += AND if sum > 0 and n > 0
    sum += LETTERS[n - n%10] + LETTERS[n%10] and n = 0 if n >= 20
    sum += LETTERS[n]
  end
end

As you can see, we just add however many “thousands” there are, plus the word “thousand”. Then we do the same for “hundred”. Then there is a small piece that adds the “and” between the hundreds and the tens/ones if both are present.¹  Finally, we add in a possibly hyphenated word for the numbers twenty to ninety-nine, or if the number is less then twenty, we add the proper word.

Notice that I’ve included zero as having no letters here. This is so that the addition for the hyphenated words works out correctly. For instance:

# The last two lines for 30
sum += 30 + 0 and n = 0 
sum += 0

# The last two lines for 31
sum += 30 + 1 and n = 0
sum += 0

The full source and specifications can be seen on github. Next time, finding the maximum sum travelling from the top of the triangle to the base.

¹This part is a little weird since in the United States, it is incorrect to include the and, but in certain European countries it is required. As the problem states it is looking for the British version, we need to add this in.