Skip to content

Project Euler Problem 17

October 26, 2011

Project Euler Problem 17, although sounding scary, is not difficult, indeed.

We begin with presenting each decimal positional number as array of position quantities in natural order, i.e. [thousands;hundreds;tens;ones].
Then we make function asWords to “write it down” as words, like we do quantities on checks.
The rest is easy: take the interval, make words of each member, remove spaces, count letters that remained into an aggregate sum.

open System.Text

let inline glue (sb: StringBuilder) (word: string) (quantity: string) =
    sb.Append(sprintf "%s%s" quantity word) |> ignore

// n -> [|thousands; hundreds; tens; ones|]
let asPositional n =
    Seq.unfold (fun (x,y) ->
        if y >= 1 then
            Some (x/y, (x%y, y/10))
        else None)
        (n,1000)
    |> Seq.toArray

let tens =
    [""; ""; "twenty"; "thirty"; "forty";
    "fifty"; "sixty"; "seventy"; "eighty"; "ninety"]
let teens =
    ["ten"; "eleven"; "twelve"; "thirteen"; "fourteen";
    "fifteen"; "sixteen"; "seventeen"; "eighteen"; "nineteen"]
let ones =
    [""; "one"; "two"; "three"; "four";
    "five"; "six"; "seven"; "eight"; "nine"]

let asWords (num: int array) =
    let sb = StringBuilder()
    if num.[0] <> 0 then
        glue sb " thousand" ones.[num.[0]]
        if num.[1] = 0 && (num.[2] <> 0 || num.[3] <> 0) then glue sb " and " ""
    if num.[1] <> 0 then
        glue sb " hundred" ones.[num.[1]]
        if num.[2] <> 0 || num.[3] <> 0 then glue sb " and " ""
    if num.[2] = 1 then
        glue sb "" teens.[num.[3]]
    else
        if num.[2] >= 2 then
            glue sb "" tens.[num.[2]]
        glue sb "" ones.[num.[3]]
    sb.ToString()

let lettersCount (numAsWords: string) =
    numAsWords.Replace (" ","") |> String.length

let problem017 () =
    [1..1000]
    |> List.map (asPositional >> asWords >> lettersCount)
    |> List.sum
Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: