Claudio Cherubino's blog Life of a Googler

22May/095

Project Euler in F# – Problem 28

Sometimes, when I find a problem like Project Euler problem 28, I remember that human beings are smarter than computers. :)

Let's read the problem statement, it doesn't seem easy at first glance:

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of both diagonals is 101.

What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?

If we don't think of anything creative, we are forced to write an algorithm to draw that 1001x1001 number spiral and then sum both diagonals together.

However, we can start noticing that the number in the top-right position is always n^2, where n is the length of one side of the spiral. In the example, the spiral is 5 by 5 and the top-right value is 25. In a 3 by 3 spiral it would be 9, 49 in a 7 by 7 spiral and so on.

If we concentrate on the outer ring of the spiral, then the inner sum can be obtained by recursion, so we only need to find a trick for the top-left, bottom-left and bottom-right numbers.

They are 21, 17 and 13 in a 5x5 spiral, so it seems like they can be computed starting from the top-right number and repeatedly subtracting 4 (i.e. n - 1).

Let's check this theory with the 3x3 spiral: the top-right number is 9, the other corners are 7, 5 and 3. We are indeed subtracting 2 (i.e. n - 1) each time!

Let's summarize: given a n x n spiral we have to sum n^2, n^2 - (n-1), n^2 - 2(n-1) and n^2 - 3(n-1).

Some elementary math and we get 4n^2 - 6n + 6 for each ring of the spiral.
The base case of the recursion is the 1x1 spiral and in that case the (degenerate) diagonal sum is 1.

Given these premises it is very easy to write the F# code to implement the algorithm:

let rec euler28 n =
  match n with
  | 1 -> 1
  | _ -> euler28 (n-2) + (4 * n * n) - (6 * n) + 6

An improvement of the code above would be using tail recursion, which means that the last operation of the function should be a recursive call. This leads to a reduction of the stack space used from O(n) to O(1) and let us avoid stack overflow exceptions:

let tail_euler28 n =
  let rec spiral n sum =
    match n with
    | 1 -> sum + 1
    | _ -> spiral (n - 2) (sum + (4 * n * n) - (6 * n) + 6)
  spiral n 0

As it is usually done in tail recursion, we define an accumulator parameter (sum in the example) which is used to store the partial result of the computation, eliminating the need to keep the state on the stack.

In both solutions I've left a bug that can lead to an infinite loop. Can you spot it?

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
17Dec/081

Project Euler in F# – Problem 55

As in the last post, in the description of Project Euler problem 55 there is a detailed step-by-step solution of the problem itself and we just have to write the F# code to perform the tasks.

The only thing that I really had to understand is the definition of Lychrel numbers:

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

As usual, it is suggested to break down the problem into little pieces that can be easily solved with a few lines of code each.

First, we need a function to reverse an integer and another one to check whether a number is palindromic, i.e. it is equal to its reverse.

Then we define a function that will be used during each iteration to take a number and sum it with its reverse. This new number is the one that will be checked next for being a palindrome inside the isLychrel function.

If we found a palindrome then the number under testing is not a Lychrel, otherwise we can start the next iteration up to a maximum of 50 times. If we hit this limit then we can conclude the number is a Lychrel.

We have now all the pieces required to answer the original question. Just take all numbers smaller then 10000, filter the Lychrel ones and count them:

#light

let reverse n =
  n.ToString().ToCharArray()
  |> Array.rev
  |> Array.map (fun x -> x.ToString())
  |> Array.reduce_left (^)
  |> bigint.Parse

let isPalindromic n =
  n = reverse n

let reverseAndAdd n =
  n + reverse n

let isLychrel n =
  let rec isLychrelIter n i =
    match i with
    | 50 -> true
    | _ ->
      let r = reverseAndAdd n
      if isPalindromic r then
        false
      else
        isLychrelIter r (i+1)
  isLychrelIter n 1

let answer = [1I .. 10000I]
             |> Seq.filter (fun x -> isLychrel x)
             |> Seq.length
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?

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
8Oct/081

Project Euler in F# – Problem 36

A number (in general a word) is palindromic when it can be read in the same way from left to right and in the opposite direction, i.e. it is "symmetrical".

According to the definition, a number can be palindromic when written in base10 and not palindromic in base2, but there are some numbers that are palindromic in both bases.

In Project Euler Problem 36 we have to find all these numbers between 1 and 1 million:

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

To solve this problem we need two helper functions, one to check whether a number is palindromic and another one to convert a number from base10 to base2:

#light
open Microsoft.FSharp.Math

let isPalindromic n =
  let chars = n.ToString().ToCharArray()
  chars = Array.rev chars

let toBinary (n : BigInt) =
  let rec toBinary1 a v =
    match v with
    | 0I -> a
    | _ ->
      let q,r = BigInt.DivMod (v,2I)
      toBinary1 (r.ToString()::a) q
  toBinary1 [] n |> List.reduce_left (^) |> BigInt.Parse

let euler36 = [1I .. 1000000I] |>
              List.filter isPalindromic |>
              List.filter (fun x -> x |> toBinary |> isPalindromic) |>
              List.reduce_left (+)

The first function checks if a number is palindromic by converting it into an array of digits and checking if this array is equal to its reverse one.

Then we have the toBinary function that is based itself on an inner function called (with a lot of originality) toBinary1.

This recursive function uses the list a to store the remainders of the repeated divisions by 2, until the original number is over.

These digits, converted as strings, are joined with ^, the string concatenation operator and eventually the result is converted to a BigInt.

To find the answer to the problem we start with the list of all numbers between 1 and 1 million and take (filter) only the elements which are palindromic in base10.

After this first step, we filter the list again, this time keeping only those numbers that are palindromic when converted to base2.

The last step is the easiest, we only need to sum the numbers left to get the answer to the problem.

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.

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?

17Apr/083

Project Euler in F# – Problem 45

A long time has passed since I last posted the solution of one of Project Euler's problems.

Problem 45 is related to figurate numbers, i.e. numbers that can be represented as geometrical patterns.

In particular, we are going to find a number that is triangular, pentagonal and hexagonal at the same time:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
Triangle: Tn=n(n+1)/2
Pentagonal: Pn=n(3n?1)/2
Hexagonal: Hn=n(2n?1)

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

A trivial solution will be computing the lists of triangular, pentagonal and hexagonal numbers and then find their intersection. However, we don't know how big the searched number can be, so we are not able to determine when to stop the generation of each list.

Hence we need a smarter solution, based on the mathematical properties of these numbers.

First of all, every hexagonal number is also a triangular number, so our problem is reduced to finding the smallest hexagonal pentagonal number greater than 40755.

Then we can generate the hexagonal numbers and check whether they are also pentagonal, stopping at the first one found.

According to the definition, we can test if a positive integer x is a pentagonal number by computing:

Test for pentagonal numbers

If n is an integer, then x is the nth pentagonal number. If n is not an integer, then x is not pentagonal.

Let's look at the F# code:

#light
open System
open Microsoft.FSharp.Math.BigInt

let hexagonal n = n * (2I * n - 1I)
let isPentagonal x = ((sqrt(to_float (24I * x + 1I)) + 1.0) % 6.0) = 0.0

let nums = 144I |> Seq.unfold (fun i -> Some (i, i + 1I))
let answer = nums |> Seq.map hexagonal |> Seq.find isPentagonal

At lines 5 and 6 we define the functions to compute the nth hexagonal number and to check if an integer x is pentagonal.

Then we start generating the hexagonal numbers to be tested, starting from the 144th, since the solution must be greater than 40755, that is the 143th hexagonal number.

In the last line we just return the first number for which isPentagonal is true, without having to know when to stop thanks to lazy evaluation, which allows us to continue generating numbers only when actually needed.

The solution to the problem is greater than I could imagine, that's why we need to use BigInt instead of normal integers.

What do you think about the approach I followed to solve this problem?

12Feb/082

Project Euler in F# – Problem 22

Unlike pure functional programming languages, F# is a multi-paradigm language, so you can mix object-oriented code with functional one, mainly to exploit the features of the .Net framework.

In Project Euler Problem 22 we are asked to open a file (imperative paradigm) containing a long list of names, sort them and perform some calculation on the characters composing the text.

Here is the description of the exercise:

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

In order to open the given file, we rely on the IO functions provided by the .Net Base Class Library (BCL), that we can access thanks the open statement at line 2 of the following code:

#light
open System.IO

let names = File.ReadAllText("names.txt").Split([|','|]) |> Seq.to_list
let couples = names |> List.map (fun x -> x.Replace("\"", "")) |> List.sort compare |> List.zip [1 .. names.Length]

let score (pos, str) =
    let value = str |> Seq.map (fun x -> (1 + Char.code x - Char.code 'A')) |> Seq.fold1 (+)
    value * pos

let answer = couples |> Seq.map score |> Seq.fold1 (+)

At line 4 we read the whole content of the names.txt file, split it on the "," (comma) characters and store the result in a list called names.

Since the names written in the file are enclosed by double quotes, we have to remove all of them with the Replace function before we can alphabetically sort the list.

When names is sorted, we combine (zip) it with another list containing the position of each element inside the sequence itself, i.e. the numbers from 1 to the length of the names list.

The result is a sequence of tuples (position, name) such as (938, "COLIN").

At line 7 we define the main function of this exercise, called score. It takes a couple (position, name) and returns the name score, which is computed multiplying the alphabetical value of the name by its position.

The value of a name is obtained by summing the position in the alphabet of each character composing the name itself.

The Char.code function converts the value of a Unicode character to an integer, so we just need to subtract from it the code of the first letter of the alphabet ("A") to get its alphabetical position.

Please notice that using "A" as the first element works because in the input file all names are written with uppercase characters only.

Then we multiply the alphabetical value of the name by its position to return the score of the couple passed as argument.

The exercise asks us to sum the scores of all elements in the input file, so we map the score function and sum the results with fold1 (+), getting the correct answer.