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.
The Problem
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.
The Solution
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
isTriplet
returns true
if 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.
- Use
Seq.unfold
to generate a sequence of possible triplets - Use
Seq.filter
to filter out triplets that don’t add up to 1000 - Use
Seq.filter
to 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, incState
and generator
. incState
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