Project Euler — Problem 42 Solution

Problem

The nth term of the sequence of tri­an­gle num­bers is giv­en by, tn = ½n(n+1); so the first ten tri­an­gle num­bers are:

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

By con­vert­ing each let­ter in a word to a num­ber cor­re­spond­ing to its alpha­bet­i­cal posi­tion and adding these val­ues we form a word val­ue. For exam­ple, the word val­ue for SKY is 19 + 11 + 25 = 55 = t10. If the word val­ue is a tri­an­gle num­ber then we shall call the word a tri­an­gle word.

Using words.txt (right click and ‘Save Link/Target As…’), a 16K text file con­tain­ing near­ly two-thou­sand com­mon Eng­lish words, how many are tri­an­gle words?

Solution

open System.IO

// read the content of the file into an array of words

let words =
    File.ReadAllLines (@"C:\TEMP\words.txt")
    |> Array.map (fun s -> s.Replace("\"", ""))
    |> Array.collect (fun s -> s.ToUpper().Trim().Split(','))

// function to calculate the word value of a word
let wordValue word =
    word.ToString().ToCharArray()
    |> Array.map (fun c -> int(c) - int('A') + 1)
    |> Array.sum

// convert all words to their corresponding word values
let wordValues = words |> Array.map wordValue
let maxWordValue = wordValues |> Array.max

// the sequence of triangle numbers
let naturalNumbers = Seq.unfold (fun state -> Some(state, state + 1)) 1
let T n = n * (n + 1) / 2
let TSeq = naturalNumbers |> Seq.map T

let answer =
    TSeq
    |> Seq.takeWhile (fun t -> t <= maxWordValue)
    |> Seq.map (fun t -> wordValues |> Array.filter (fun n -> n = t) |> Array.length)
    |> Seq.sum

To get start­ed on this prob­lem, I first read all the words in the down­loaded text file into an array of strings, each being one of the two thou­sand words. Then I build a func­tion to cal­cu­late the word val­ue of a word and con­vert­ed the word array into an array of word val­ues. The max word val­ue is use­ful here because it allows me to cap how many ele­ments in the T sequence I should check.