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?

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.

The Solution

Ah, the classics. Converting numbers to words.

I've written dozens of variations of this algorithm in the last 25+ years. It seems every programming class and every language book has a variation of this exercise.

Let's start by making a Map that we can use to convert numbers to words.

let words = [
    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"
    1000, "one thousand"]

let wordMap = words |> Map.ofList

Since we only have to deal with numbers up to 1000, the algorithm is simple enough:

• If the number exists in our map, return that
• If the number is less than 100, return the word for tens portion and the word for the ones portion.
• Otherwise, the number is > 100 and < 1000. The range is exclusive because the map lookup already covered both 100 and 1000. Thus, all that remains is to compute the word for the hundreds place, and call then call the function recursively for what's left.

let rec toWords n =
    match wordMap.TryFind n with
    | Some v -> v
    | _ ->
        if n < 100 then
            let ones = n%10
            wordMap.[n-ones] + "-" + wordMap.[ones]
        else
            let hundreds = n/100
            let tens = n%100
            if tens = 0 then
                wordMap.[hundreds] + " hundred"
            else
                wordMap.[hundreds] + " hundred and " + (toWords tens)

With that in place, we get our answer:

let charCount s =
    s |> Seq.filter (fun c -> c <> ' ' && c <> '-') |> Seq.length

seq { 1..1000 }
|> Seq.map toWords
|> Seq.sumBy charCount

Other Posts in This Series