Claudio Cherubino's blog Life of a Googler

7Feb/086

Project Euler in F# – Problem 5

The exercise we are going to face today is ranked as one of the easiest of Project Euler's, so I don't think you will have any problem in solving it.

However, it allows me to discuss a little bit on algorithm optimization and how to refine a working solution to obtain a better one.

The text of the exercise says:

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?

Some programming languages (for instance Haskell) provide a native function for evaluating the least common multiple (LCM) of two numbers, i.e. the smallest positive integer that is multiple of both numbers.

In F# we don't have this function, hence we have to write our own code to perform this calculation, and we need it to be able to find the LCM of a set of numbers and not only two.

Let's see the implementation of my algorithm:

#light
open System

let nums = 1 |> Seq.unfold (fun i -> Some (i, i + 1))

let divisibleByList list n =
    Seq.for_all (fun x -> n % x = 0) list

let answer = nums |> Seq.first (fun i -> if divisibleByList [1 .. 20] i then Some (i) else None)

My solution will simply take the integers starting from 1 and check if they are evenly divisible by all numbers from 1 to 20.

We don't know when to stop, so at line 4 we have to create an infinite list of integers.
To do so, we use the unfold function, which allows us to create a lazy list by passing another function to be repeatedly evaluated to provide the elements of the list.

In our case we start from 1 and for each iteration we add one to the previous value, without an upper limit.

At line 6 we have the definition of the divisibleByList function, which takes a list of numbers and an integer n and checks if n is evenly divisible by all the elements of the given list.

This is done by using Seq.for_all, which tests if all the elements of the sequence satisfy the given predicate.

We have now everything we need to find our solution.
Let's just feed the divisibleByList function with the elements of the infinite list of integers and stop when we find the first that satisfy our conditions, thanks to Seq.first.

The solution is complete, but it is not very fast, since it takes about 8 minutes to run in my computer.

We can improve this time by using some very simple math.
First of all, we are sure that the number we are looking for will be a multiple of 2, so we can skip all odd numbers, by changing line 4 with:

let nums = 2 |> Seq.unfold (fun i -> Some (i, i + 2))

With this simple change the execution time drops to 4 minutes, as the amount of integers to check is is actually halved.

I want to go a little further and instead of checking all even numbers we can just test the multiples of 20.
To do so, we change again line 4 with this new one:

let nums = 20 |> Seq.unfold (fun i -> Some (i, i + 20))

Now I can be proud of myself as the execution time is reduced to 25 seconds, twenty times less than the original solution!

Obviously this is not the only solution and there are smarter approaches, maybe we can see them in a future post.

22Jan/082

Sorting odd and even numbers in F#

An Italian Microsoft Evangelist posted today a small programming exercise on his blog, presenting the solution with LINQ.

The exercise says (translated from Italian by me):

Given a list of unordered numbers (for instance 1, 7, 9, 2, 3, 4, 3, 4, 2, 3, 4, 5, 2, 0, 9), create a new list with all even numbers first and then all the odd ones.

The proposed solution also goes a little further, showing not only how to split the original list into odd and even numbers, but also putting them in the correct order, thus returning "022244413335799".

The following is the C# code used:

List<int> elenco = new List<int> { 1,7,9, 2, 3, 4, 3, 4, 2, 3, 4, 5, 2, 0, 9 };
var pariEdispari = elenco.OrderBy(s => s % 2 != 0);
var pariEdispariOrdinati = elenco.OrderBy(s => s % 2 != 0).ThenBy(s => s);

foreach (var item in pariEdispariOrdinati)
{
      Console.WriteLine(item);
}

And now let's compare it with an F# approach:

#light
let numbers = [ 1; 7; 9; 2; 3; 4; 3; 4; 2; 3; 4; 5; 2; 0; 9 ]

let result = numbers |> List.sort Int32.compare |> List.partition (fun x -> x % 2 = 0)

print_any ((fst result) @ (snd result))

As you can easily see, everything is done at line 4, where we apply twice the pipeline operator (|>).

This operator allows to chain functions, passing the output of one of them to the next one.
The same line could be written as:

List.partition (fun x -> x % 2 = 0) (List.sort Int32.compare numbers)

Line 6 is only used to print the result, but it has to take into account that the output of List.partition is a tuple, so we have to concatenate the two elements that can be retrieved with the fst (first) and snd (second) functions.

The @ operator actually concatenates the two lists.

I'm not sure that this is the best (and most elegant) solution, but I think that it is way ahead than any imperative solution, do you agree with me?