Claudio Cherubino's blog Life of a Googler

30Apr/084

Project Euler in F# – Problem 48

The following problem from Project Euler is one of those supposed to be solved either with intensive computation or a "smarter" approach.

Here is the description of problem number 48:

The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.

Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.

If our language allows us to evaluate the series mentioned above (and F# does!), we can just do it and then take the last 10 digits of the result as required.

This can be implemented by the following F# code:

#light
open Microsoft.FSharp.Math.BigInt

let last10 num = num % (pow 10I 10I)

let answer = [1I .. 1000I] |> Seq.map (fun x -> pow x x) |> Seq.fold (+) 0I |> last10

The first problem is extracting the last ten digits from a given number, and this is done by dividing the number by 10^10 and returning the remainder of the division (line 4).

Then we have to generate the series n^n for all n from 1 to 1000 and sum the items.

This sum is actually a huge number (more than 3000 digits) but we are only interested in the last ten digits, so we can use the pipeline operator (|>) to pass it to the last10 function.

The only caveat is to use BigInt, otherwise the numbers we are talking about will never fit into the other numeric data types.

Easy, isn't it?

Tagged as: , , , , , , 4 Comments
23Jan/082

Project Euler in F# – Problem 6

The exercises proposed by Project Euler are ordered by difficulty, and the one I'll discuss today is ranked sixth.

However, I think it is one of the easiest to solve, since it doesn't require any trick and the solution is already written in its text:

The sum of the squares of the first ten natural numbers is,
1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 ? 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

We just have to evaluate two formulas and then perform a subtraction, so let's go directly to the F# code:

#light
let numbers = [1 .. 100]

let diff =
   (numbers |> Seq.fold (+) 0 |> (fun x -> x*x)) -
   (numbers |> Seq.sumByInt (fun x -> x*x))

You should already know the pipeline operator, which is massively used in F#.

Seq.fold is used to apply a function (in our case the sum operator) to all the elements of a collection (i.e. the list of numbers) starting from a base value that we set equal to zero.

Then we pass the result to a function that takes a number and returns its square, actually giving us the square of the sum of the first 100 numbers.

In the next line of the diff function we evaluate the sum of the squares of the first 100 numbers.

It is done thanks to the Seq.sumByInt function that returns the sum of the results generated by applying the given function (i.e. the square function) to each element of the collection.

That's it, no tricks and no special mathematical knowledge required, I told you!

Tagged as: , , , , , , 2 Comments
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?

Tagged as: , , , , , , , , , 2 Comments
   

Twitter Updates

Posting tweet...

Follow me

Google+ Twitter Linkedin