Post a Comment On: Scattered Thoughts

Project Euler's seventeenth problem wants to know:

How many letters would be needed to write all the numbers in words from 1 to 1000?

For example, in the British style, one would write out 256 as "two hundred and fifty-six". We are told not to count spaces and hyphens so 21 letters are needed for this number.

My approach is to decompose a number into a tuple containing the number of thousands, hundreds, tens and ones in the number. However, to make things simpler for me I chose to special case all the numbers under 20 since their spelling is a irregular. That is, instead of saying something like "ten plus one" we say "eleven". It is easier to break that out at this stage in the problem.

Here is my F# code to decompose a number:

let decompose x =     let thousands x = (x/1000)*1000    let hundreds  x = ((x - thousands x)/100)*100    let tens      x =         let temp = ((x - thousands x - hundreds x)/10)*10        match temp with        | _ when 0 < temp && temp < 20 -> 0        | _                            -> temp    let ones      x = (x - thousands x - hundreds x - tens x)    (thousands x, hundreds x, tens x, ones x)
Just to show how this works, here is the decomposition of some example numbers:
> decompose 256;;val it : int * int * int * int = (0, 200, 50, 6)
> decompose 512;;val it : int * int * int * int = (0, 500, 0, 12)
The next piece of the puzzle is to take a section of the decomposed number and return the number of letters used to write it out:

let letters x =    match x with    |    1 ->  3    // one    |    2 ->  3    // two    |    3 ->  5    // three    |    4 ->  4    // four    |    5 ->  4    // five    |    6 ->  3    // six    |    7 ->  5    // seven    |    8 ->  5    // eight    |    9 ->  4    // nine    |   10 ->  3    // ten    |   11 ->  6    // eleven    |   12 ->  6    // twelve    |   13 ->  8    // thirteen    |   14 ->  8    // fourteen    |   15 ->  7    // fifteen    |   16 ->  7    // sixteen    |   17 ->  9    // seventeen    |   18 ->  8    // eighteen    |   19 ->  8    // nineteen    |   20 ->  6    // twenty    |   30 ->  6    // thirty    |   40 ->  5    // forty    |   50 ->  5    // fifty    |   60 ->  5    // sixty    |   70 ->  7    // seventy    |   80 ->  6    // eighty    |   90 ->  6    // ninety    |  100 -> 10    // one hundred    |  200 -> 10    // two hundred    |  300 -> 12    // three hundred    |  400 -> 11    // four hundred    |  500 -> 11    // five hundred    |  600 -> 10    // six hundred    |  700 -> 12    // seven hundred    |  800 -> 12    // eight hundred    |  900 -> 11    // nine hundred    | 1000 -> 11    // one thousand    |    _ ->  0
Now, given a decomposed number, compute the total number of letters used to write it out:

let length (a, b, c, d) =    match (a, b, c, d) with     | (_, _, 0, 0) -> letters a + letters b    | (0, 0, _, _) -> letters c + letters d    | (_, _, _, _) -> letters a + letters b + letters c + letters d + 3
Note that the 3 in the last case is to account for the word "and".

Finally, to find out how many letters are needed to write out the numbers from one to 1000:

{1..1000} |> Seq.map decompose |> Seq.map length |> Seq.sum |> printfn "count = %A"