The Problem

The nth term of the sequence of triangle numbers is given by, t_n = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t₁₀. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

The Solution

The most obvious place to start is by writing a function for t_n

let t n = n * (n + 1) /2

Whew! I'm glad we got that complicated beasty out of the way.

Now, I suspect that we're going to be seeing the same triangle numbers over and over again, so I think it might be helpful to be able to find them quickly. Let's create a Map of the first 1000 triangle numbers.

let triangleNumbers = 
    Seq.unfold (fun state -> Some(t state, state + 1)) 1
    |> Seq.map (fun x -> (x,x))
    |> Seq.take 1000
    |> Map.ofSeq

And we can use that to create a function that determines if a given n is a triangle number.

let isTriangle n = Map.containsKey n triangleNumbers

Next, we need a way to turn a word into its numeric value, per the problem definition.

let toNumeric (s : string) =
    s
    |> Seq.map (fun v -> int(v) - int('A') + 1)
    |> Seq.sum

string can be treated as Seq<char> so we simply map each character to its integer value, subtract the integer value for 'A', and add 1.

Now we can solve the problem:

let splitByMany (c : char[]) (s : string) = 
    s.Split(c, System.StringSplitOptions.RemoveEmptyEntries)

System.IO.File.ReadAllText(@"C:\Development\ProjectEuler\FSharpSolutions\WordsProblem42.txt")
|> splitByMany [| '"'; ',' |]
|> Seq.map(fun w -> (w,toNumeric w))
|> Seq.filter (fun (w,v) -> isTriangle v)
|> Seq.length

The above reads in all the words, splits them into an array, computes their numeric value, filters out any values that aren't triangle numbers, and returns the sequence length. The length of the sequence is the answer.

Other Posts in This Series