This took me a lot longer to solve than it should have. In fact, I got the solution right, then started over from scratch. The end result was much better.
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
First, let’s define some functions that let us know when we have the right answer:
let max = 1000 let isTriplet (a,b,c) = a*a + b*b = c*c let isSpecial (a,b,c) = a+b+c=max
a,b,c is a Pythagorean triplet.
isSpecial returns true if the sum of
a,b,c is 1000.
If both return true for an
a,b,c, that’s our answer.
Since we like expressing our problems as a pipeline, here’s the plan of attack.
Seq.unfoldto generate a sequence of possible triplets
Seq.filterto filter out triplets that don’t add up to 1000
Seq.filterto filter out non-Pythagorean triplets
- The first one of those is our answer.
The first thing we need is a sequence generator. This is made up of two functions,
finds the next triplet.
let incState = function | a,b,c when b<>(max-1) && c=max -> a,b+1,b+2 | a,b,c when b=(max-1) && c=max -> a+1,a+2,a+3 | a,b,c -> a,b,c+1
I could have made this slightly simpler, but since the problem definition specifies that a < b < c, I wanted to make sure that the result of this function obeyed that rule. Doing so decreases the possible sequences from 1 billion to about 160 million, which is quite the improvement.
let generator ((a,_,_) as state) = if a>=(max-1) then None else Some(state, (incState state))
The above generates a sequence of triplets by incrementing the state until
a hits 999.
Now that we can tell if we have the answer and we have a sequence of possible answers, finding the answer is easy:
Seq.unfold generator (1, 2, 997) |> Seq.filter isSpecial |> Seq.filter isTriplet |> Seq.head