Monday, March 09, 2009

Welcome back F# junkies! In this installment of YAPES1, we’re tackling Project Euler problem nine.

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.

Like we’ve done before, we’ll break this problem down into steps:

  1. Generate a stream of Pythagorean triples.
  2. Find the Pythagorean triple whose sum is equal to 1000.
  3. Calculate the product of that triple.

Sound good?

The first order of business is to determine how to generate Pythagorean triples. It turns out that there are many ways to do this. However, to keep it simple, we will use Euclid’s classic formula:

Given a pair of positive integers m and n with m > n

a = 2mn, b = m2n2, c = m2 + n2

Truthfully, this formula doesn’t actually produce every possible Pythagorean triple. However, since the solution is within the set that it generates, that really isn’t a problem.

NeRd Note
To produce every Pythagorean triple, we would have to introduce an additional parameter, k, into the formula.
a = 2kmn, b = k(m2n2), c = k(m2 + n2)
This is left as an exercise for you, dear reader!

First, we’ll declare an F# function that calculates a Pythagorean triple using Euclid’s formula.

let getTriple m n =
  let a = 2*m*n
  let b = m*m - n*n
  let c = m*m + n*n

Using the above function, it’s easy to produce a stream of Pythagorean triples. Our strategy will be to start with the pair, m = 2 and n = 1. To generate the next pair, we’ll first check if n + 1 is less than m. If it is, we’ll use m and n + 1 as the next pair, otherwise we’ll use m + 1 and 1. Using Seq.unfold, we can use this algorithm to produce an infinite stream of Pythagorean triples:

let triples =
  Seq.unfold (fun (m,n) ->
                let res = getTriple m n
                let next = if n+1 < m then m,n+1 else m+1,1
                Some(res, next))

With our generator in place, we can easily solve the problem.

  |> Seq.find (fun (a,b,c) –> a+b+c = 1000)
  |> (fun (a,b,c) –> a*b*c)

While the above solution works well, we can abstract further to produce a more elegant solution. First, we’ll declare three functions to handle the three operations that we’re performing explicitly, sum, product and equals.

let sum (a,b,c) = a+b+c
let product (a,b,c) = a*b*c
let equals x y = x = y

Now, we can restate our solution using these functions with a bit of function composition to produce a truly beautiful solution.

  |> Seq.find (sum >> equals 1000)
  |> product

As we’ve seen once before, function composition is beautiful.

1Yet Another Project Euler Series

posted on Monday, March 09, 2009 7:05:47 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on