Project Euler – Problem 42 Solution

Problem

The nth term of the sequence of triangle numbers is given by, tn = ½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 = t10. 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?

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 started on this problem, I first read all the words in the downloaded text file into an array of strings, each being one of the two thousand words. Then I build a function to calculate the word value of a word and converted the word array into an array of word values. The max word value is useful here because it allows me to cap how many elements in the T sequence I should check.

  • Bryan Slatner

    Just a comment. In .NET, all strings are already seq so in many cases you can skip the step of converting to a char[] and use the Seq.xxx functions to operate on it instead.

  • Bryan Slatner

    Thank you, Disqus, for turning a fairly innocuous programmery string into a porn URL :)

  • Yan Cui

    yup, you’re right, the `ToCharArray` is redundant there