Claudio Cherubino's blog Life of a Googler

20Mar/092

Project Euler in F# – Problem 52

After a long break, let's resume with the Project Euler series.

The next one to be solved is Problem 52:

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

As usual, we have to break the problem into small pieces and solve these pieces one by one.

As in many other Project Euler problems we have to extract the digits of a number, and this is done by converting the number into a string (i.e. an array of characters) and then casting the characters to integers.

We also need a function to check if two numbers are made of the same digits. For each number we create a set from the sequence of its digits, in order to ignore the order of the items and discard duplicates. Then we apply the standard set comparison operator to get the result.

We have to multiply each positive integer by 2, 3, 4, 5 and 6, so we can define the multiples function, which takes an integer x and returns a list containing five elements, corresponding to 2x, 3x, 4x, 5x and 6x.

Thanks to these three functions, checking if a number and its multiples contain exactly the same digits is very easy. In fact, we generate the list of multiples and test all of them with the same_digits function.

The algorithm to get the answer to the problem is the following: generate an infinite list of integers (remember seq_unfold?), test each number with the check function and return the first value that passes the test.

#light

let digits n =
  n.ToString() |> Seq.map (string >> int)

let same_digits a b =
  Set.equal (Set.of_seq (digits a)) (Set.of_seq (digits b))

let multiples n =
  [2 .. 6] |> Seq.map (fun x -> n * x)

let check n =
  n |> multiples |> Seq.for_all (same_digits n)

let answer =
  1 |> Seq.unfold (fun i -> Some (i, i + 1)) |> Seq.first (fun x -> if check x then Some (x) else None)

There is also a well-known (and tricky) solution for this problem, which was presented in the book "The man who calculated". Did you know it?

Tagged as: , , , , 2 Comments
19Nov/083

Project Euler in F# – Problem 19

When someone asks me what are the advantages of F# in comparison with the other functional programming languages, usually the first thing I answer is the .Net Framework.

This framework provides the developers with a plethora of libraries and functions that cover almost all the requirements you can imagine and if you need something that is missing, you will surely develop it on top of solid basis.

I can prove this by showing you the F# solution to Project Euler problem number 19:

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

After the first time I read the problem I started wondering on how to check whether a given date is a Sunday and a "smart" solution suddenly came into my mind.

The .Net Framework contains a robust set of classes and functions to work on dates and F# can use them as C#, VB.Net and all the other supported languages.

The algorithm implemented works in the following way: we create a starting DateTime object representing 1 Jan 1901 and then continue adding 1 month (using the AddMonths function) until we get to year 2001.

For each DateTime objects returned by this sequence we check if its DayOfWeek property is equal to DayOfWeek.Sunday (.Net magic!). In this case we keep the value otherwise we simply discard it.

Eventually we just have to count the number of items (i.e. DateTime objects) left and we get the result.

Let's translate the algorithm into F# syntax and we get the following code:

#light
open System

let startDate = new DateTime(1901, 1, 1)

let euler19 = startDate
              |> Seq.unfold (fun (x : DateTime) -> Some(x, x.AddMonths(1)))
              |> Seq.take_while (fun (x : DateTime) -> x.Year < 2001)
              |> Seq.filter (fun (x : DateTime) -> x.DayOfWeek = DayOfWeek.Sunday)
              |> Seq.length
19Sep/083

Project Euler in F# – Problem 25

After a long break, let's try to resume with a regular publication scheme, starting with Project Euler's problem 25, an easy one, which says:

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn1 + Fn2, where F1 = 1 and F2 = 1.

...

The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

The problem definition also contains the algorithm to solve it, I told you it was easy.

Actually, we just have to write a function to compute the Fibonacci sequence and stop when a term contains a thousand digits.

Since we don't know when we are done evaluating the terms of the sequence we have to generate an infinite sequence and check every new item to see if we can stop.

Let's give a look at the F# code:

#light
open Microsoft.FSharp.Math.BigInt

let has1000Digits (n : Microsoft.FSharp.Math.BigInt) =
  n.ToString().Length = 1000

let euler25 =
  ((1I,1I) |> Seq.unfold
    (fun (n0, n1) ->
      (if has1000Digits n0 then None
        else Some(n0, (n1, n0 + n1))))
    |> Seq.length) + 1

The Seq.unfold function is used to generate the infinite sequence, returning Some when we want to continue and None when we are done searching (i.e. the term has 1000 digits).

In the latter case, the length of the sequence represents the number of elements generated before the one with a thousand digits, so we have to sum 1 to get the desired answer.

7Apr/083

Even Digits Multiple Of Nine

The mathematical exercise we are going to solve comes from mathschallenge.net and can be summarized in a single sentence:

Find the smallest multiple of nine containing only even digits.

We just need a function to check if a number contains only even digits and then pass to it the multiples of nine.

This algorithm can be translated into the following code:

#light
open System

let isEven n = (n % 2 = 0)

let rec allEvenDigits n =
    match n with
    | n when n < 10 -> isEven n
    | n -> (isEven (n % 10)) && (allEvenDigits (Int32.div n 10))

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

let answer = Seq.find allEvenDigits nums

The isEven function is just a "shortcut" for the modulus operator and it is used inside allEvenDigits, where it is applied to each digit of the given number.

Then, we have to generate the multiples of nine, but we don't know when to stop, so we need an infinite sequence, that can be produced by the Seq.unfold function.

At the end we use Seq.find, which takes a boolean function (allEvenDigits) and a sequence (nums), and returns the first element of the sequence for which the given function returns "true", i.e. the smallest multiple of nine containing only even digits, that is exactly what we had to find.