Project Euler — Problem 9 Solution

Problem

A Pythagore­an triplet is a set of three nat­ur­al num­bers, a < b < c, for which,

a2 + b2 = c2

For exam­ple, 32 + 42 = 9 + 16 = 25 = 52.

There exists exact­ly one Pythagore­an triplet for which a + b + c = 1000.

Find the prod­uct abc.

Solution

let isPythagoreanTriplet(numbers : int list) =
    match List.sort(numbers) with
    | [a; b; c] -> a*a + b*b = c*c
    | _ –> false

let getTriplets =
    seq {
        for a = 1 to 1000 do
            for b = 1 to 1000 do
                for c = 1 to 1000 do
                    if a + b + c = 1000 then yield [a; b; c]
    }

let pythagoreanTriplet = getTriplets |> Seq.filter isPythagoreanTriplet |> Seq.head
let product = pythagoreanTriplet |> Seq.fold (fun acc x -> acc * x) 1

Here I’ve cre­at­ed a func­tion called isPythagore­anTriplet, which takes a inte­ger list and checks whether it’s a pythagore­an triplet. If this is the first time you’ve seen the match …. with syn­tax, it’s used to match a pat­tern in F#. The pat­terns are eval­u­at­ed from top to bot­tom, the first pat­tern decom­pos­es a sort­ed ver­sion of the sup­plied int list into three val­ues a, b and c, and eval­u­ates whether a, b and c makes a pythagore­an triplet:

| [a; b; c] -> a*a + b*b = c*c

If the list does not have exact­ly three ele­ments, then the next pat­tern is eval­u­ate. The _ char­ac­ter is the wild­card char­ac­ter and in this case it sim­ply returns false always. e.g.:

isPythagoreanTriplet [3;4;5;0];;
val it : bool = false

isPythagoreanTriplet [];;
val it : bool = false

isPythagoreanTriplet [3;4;5];;
val it : bool = true

The get­Triplets func­tion on the hand, sup­plies a sequence of all triplets which match­es the a + b + c = 1000 require­ment. Note that I used the yield key­word to pro­duce val­ues that become part of the returned sequence.

The next line of code sim­ply iden­ti­fies the first (Seq.head) triplet from the above sequence which is a pythagore­an triplet.

And final­ly, the prod­uct of the pythagore­an triplet is cal­cu­lat­ed using the Seq.fold func­tion (iden­ti­cal to the func­tion used in the prob­lem 8 solu­tion, which describes the func­tion in more detail).