Claudio Cherubino's blog Life of a Googler

7Dec/081

Project Euler in F# – Problem 53

Some of the problems proposed by Project Euler actually present the solution together with the description of the problem itself.

This is the case with Problem 53:

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, ^(5)C_(3) = 10.

In general,
^(n)C_(r) =
n!

r!(n?r)!
,where r ? n, n! = n×(n?1)×...×3×2×1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: ^(23)C_(10) = 1144066.

How many, not necessarily distinct, values of ^(n)C_(r), for 1 ? n ? 100, are greater than one-million?

The only knowledge required in this problem is the binomial coefficient, but its formula is also described in the text above, so we can simply generate all couples (n, r) and check if the value of the binomial coefficient is greater than one million.

In F# this is equivalent to coding a function for the binomial coefficient and testing the items of a sequence:

#light
open Microsoft.FSharp.Math

let binomial_coefficient n k = BigInt.Factorial n /
                               (BigInt.Factorial k * BigInt.Factorial (n-k))

let answer =
  seq { for n in 1I .. 100I do
          for k in 1I .. n -> n,k } |> Seq.filter (fun (a,b) -> binomial_coefficient a b > 1000000I ) |> Seq.length

The approach adopted is almost the same that I used to solve Project Euler problem number 9. It is not the smartest nor the quickest since it is essentially a brute-force algorithm, but without any doubt it is the easiest to implement.

Which optimizations would you consider?

8Feb/084

Project Euler in F# – Problem 5 (alternative solution)

There was some buzz concerning my last post on Project Euler Problem 5, since the solution presented implemented a naive brute-force algorithm and its performance was very poor.

In my mind it was only meant to be an introductory article devoted to presenting a first solution to a common problem, the least common multiple (LCM) of a set of numbers, and I planned to write a second post (the one you are reading now) to show how a "smart" algorithm could lead to outstanding performance.

Let's read the text of the exercise another time:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

As we already explained, the exercise just asks us to find the least common multiple of all numbers from 1 to 20, and we can compute it by using the greatest common divisor of these numbers.

In fact, we have that:

lcm (a,b) = a * b / gcd (a,b)

In order to compute the LCM of the numbers from 1 to 20, we start computing the LCM of the first two numbers (1 and 2) and then we go on computing the LCM of the result and the third element of the sequence. We go on this way until all elements have been included in the computation.

The application of the same function to all elements of a sequence while keeping an "accumulator" is called folding, and it is a common practice in functional programming.

Let's look at the code:

#light
open Microsoft.FSharp.Math.BigInt

// Greater Common Divisor
let rec gcd a b =
 match b with
 | b when b = 0I -> a
 | b -> gcd b (a % b)

// Least Common Multiple
let lcm a b = a * b / (gcd a b)

let answer = Seq.fold1 lcm [1I .. 20I]

At line 11 we defined the least common multiple as explained above, while at line 5 we have the implementation of the Euclidean algorithm for the Greatest Common Divisor.

Then we simply fold the lcm function on the sequence [1 .. 20] and we get the output.

Do you remember how much time our "optimized" algorithm in the last article takes to perform the same calculation? 25 seconds.

The solution presented here only needs 15 milliseconds!

25Jan/080

Project Euler in F# – Problem 9

Today's exercise is Project Euler Problem 9, that says:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Therefore this time we have to find a triplet (a, b, c), but a brute-force approach would require a billion combinations, since the three numbers can range from 1 to 1000.

However, we can reduce the number of tests exploiting a little algebra.

First of all, c = 1000 - a - b, so only two variables are in play, leading us to a million choices.

Then we go down to half a million, thanks to the constraint that a < b.

According to these premises, here is the F# code:

#light
let sq x = x * x

let ab =
    { for a in 1 .. 1000
      for b in a .. 1000 -> a,b } |> Seq.filter (fun (a,b) -> sq a + sq b = sq (1000 - a - b) ) |> Seq.hd

let answer =
    let a = fst ab
    let b = snd ab
    let c = 1000 - a - b
    a * b * c

At line 5 we enumerate all items of a collection created with list comprehension, i.e. the numbers between 1 and 1000.

Inside this loop we have another loop, but in this case we are interested in all numbers bigger than the current item of the outer collection, i.e. all numbers between a and 1000.

Then, we filter all couples (a, b) keeping only those for which we have: a² + b² = (1000 - a - b)².

According to the text of the exercise, there exists exactly one Pythagorean triplet that satisfies the equation a + b + c = 1000, so we can apply the Seq.hd (head) function to take the first (and only) element of the generated sequence.

At lines 9, 10 and 11 we evaluate a, b and c and finally we multiply them to get the answer.