FSharp.it

Since 2005 Microsoft sponsors an annual scripting competition called Winter Scripting Games, whose competitors are given a series of exercises to be solved with VBShell, Powershell or Perl scripts.

I confess that I only discovered this competition a couple of days ago, and I think that some of the proposed exercises can be useful to practice F# as I’m doing with Project Euler.

There are two Divisions (Beginner and Advanced) with 10 problems each, and today we’ll try to solve the first exercise of the Beginner division, called Pairing Off:

In this event we’ll be working with a standard deck of playing cards. A standard deck consists of four suits: Hearts, Spades, Clubs, and Diamonds. Within each suit are the numbers two through ten, plus a Jack, a Queen, a King, and an Ace.

Given a random set of five cards, your task is to find out how many pairs are in that set. In other words, if your five cards are the 2 of hearts, the 4 of spades, the 4 of clubs, the queen of diamonds and the queen of spades, you have 2 pairs: 2 fours and 2 queens. As another example, you might have a 3 of clubs, a 3 of diamonds, a 3 of hearts, a 10 of spades and an ace of hearts. In that case you have 3 pairs: 3 of clubs and 3 of diamonds; 3 of diamonds and 3 of hearts; and 3 of clubs and 3 of hearts.

Let’s write the F# solution and then we’ll comment it line by line:

#light
open System

let deck =
    [| for y in ["Hearts"; "Spades"; "Clubs"; "Diamonds"]
      for x in [1 .. 13] -> (x,y) |]

let swap a i j =
    let t = a.[i]
    a.[i] <- a.[j]
    a.[j] <- t

let shuffle a =
    let rand = new Random()
    Array.iteri (fun i _ -> swap a i (rand.Next(Array.length a))) a

let rec pairs elem list =
    match list with
    | [] -> 0
    | x::xs when (fst x) = elem -> 1 + pairs elem xs
    | x::xs -> pairs elem xs

let rec count_pairs hand =
    match hand with
    | [] -> 0
    | x::xs -> pairs (fst x) xs + count_pairs xs

do shuffle deck
let hand = deck |> Seq.to_array |> Seq.take 5

let answer = hand |> count_pairs

First of all we need to simulate a deck of cards, with four suits and 13 cards for each suit, and this is done at line 4 thanks to array comprehension.

We need now to shuffle the deck, in order to randomly get five different cards every time we run the application. To do so, we defined the shuffle function at line 13, which swaps the elements of an array in-place, i.e. without returning a new object.

In fact the shuffle function is of type array -> unit, and unit is a special type that means “no value”.

When this function is applied to our deck, it iterates each element and swaps it with a random selected one from the same array, using the swap function defined at line 8.

Since the shuffle function doesn’t return anything, to call it we have a special syntax: instead of “let” we have to use the “do” keyword, as in line 28.

We are now able to create a card deck and shuffle it, the next step will be writing a function to count the number of pairs contained in a hand of cards.

To accomplish this task we have two functions, called count_pairs and pairs. The idea is to take the first card and check how many couples can be formed with the cards next to it.

The count_pairs function simply applies the pairs function to each element of the hand array, and the pairs function counts how many times the numeric part of the given card is equal to the number contained in the other cards.

To get our answer we just create a random hand of five cards and then apply the pairs_count function to it.

Nice, isn’t it? Please let me know if you liked this article and you’d like to read some other on this topic, I’ll be glad to write more.

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.

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!

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.

This time we are gonna “cheat“.

As in Problem 20 we have to sum the digits of a number, so we can just copy and paste the whole code and edit a single line to have a working solution.

The problem says:

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?

The only difference between this exercise and the last one is the number to evaluate.

However, as for the factorial, F# already provides us with a native function for the powers of a numbers, so the final code will be:

#light
open Microsoft.FSharp.Math.BigInt

let rec digits n =
    match n with
    | n when n < 10I -> n
    | n ->
        let x, y = divmod n 10I
        y + digits x

let answer = digits (pow 2I 1000I)

If you compare this exercise with the last one, you can see that we actually changed one line, i.e. line 11.

Do you really want me to explain this code?