FSharp.it

Unlike the first puzzle, which required some maths knowledge, in the second one we have to prove to be able to recursively process the filesystem.

I think that this puzzle should be quite easy to solve for the system administrators and in general those used to scripting languages.

Here is the text of the second Google Treasure Hunt 2008 problem:

Here is a random zip archive for you to download:
GoogleTreasureHunt08_1767743498252291641.zip

Unzip the archive, then process the resulting files to obtain a numeric result. You’ll be taking the sum of lines from files matching a certain description, and multiplying those sums together to obtain a final result. Note that files have many different extensions, like ‘.pdf’ and ‘.js’, but all are plain text files containing a small number of lines of text.

Sum of line 4 for all files with path or name containing jkl and ending in .txt
Sum of line 1 for all files with path or name containing zzz and ending in .xml
Hint: If the requested line does not exist, do not increment the sum.

Multiply all the above sums together and enter the product below.

As usual, the puzzle may seem challenging at a first glance, so it is important to break it into smaller (and simpler) pieces.

First of all, we have to get the list of files ending with a given extension and containing a specific substring in their name.

There is an overloaded version of the Directory.GetFiles() function which takes two parameters, the directory to be searched and a pattern to be found in the files.

Then we have to filter the results checking if the complete filenames (path + filename) contain the given substring.

This first sub-problem can be solved with the following F# code:

#light
open System.IO

let file_list dir pattern content =
  let rec allFiles dir pattern =
      seq
          { for file in Directory.GetFiles(dir, pattern) do
              yield file
            for subdir in Directory.GetDirectories(dir) do
              for file in allFiles subdir pattern do
                  yield file }
  let elems = allFiles dir pattern
  let filt (str : string) = str.Contains(content)
  Seq.filter filt elems

Now we have the list of all files that satisfy the requirements of the exercise.

The next step is to open them (they are plain text files, despite their extensions) and take the numeric value from the right line, if present.

Let’s write a function to accomplish this task for a single file and then map it to the entire list:

let getvalue numline filename =
  let lines = File.ReadAllLines(filename)
  let linevalue (lines : string[]) numline =
    let realindex = numline - 1
    if lines.Length > realindex then
      System.Int32.Parse(lines.[realindex])
    else
      0
  linevalue lines numline

The File.ReadAllLines(filename) function returns an array of strings, one for each line of the source file.

Arrays in F# have indexes starting from 0, so we have to subtract 1 from the line number supplied by the user to get the real index.

We also have to be sure that the searched line exists. In this case we return its content, otherwise we return zero.

We have now all the elements we need to compute one of the numbers requested by the exercise, we should only supply the appropriate parameters in this way:

let treasurehunt2 dir pattern content numline =
  file_list dir pattern content |> Seq.map (getvalue numline) |> Seq.fold (+) 0

For instance, to solve the first line of my puzzle we have to run the following command, assuming that the archive was unzipped in C:\google:

treasurehunt2 "C:\google" "*.txt" "jkl" 5

I hope you don’t need my help to run this command twice with different parameters and multiply the results to get your answer to the quiz!

A couple of days ago Google launched a contest called Treasure Hunt 2008, which will be composed of 4 puzzles.

Only the first of these quizzes is already available at http://treasurehunt.appspot.com/, and the new ones will be posted once per week.

At the end of the four puzzles there will be some prizes, even if nothing has been revealed yet.

Here is the description of the first puzzle:

A robot is located at the top-left corner of a n x k grid.
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.
How many possible unique paths are there?
(Note: Answer must be an exact, decimal representation of the number. Image not to scale.)

If the number of rows is r and the number of columns c, the robot can move r-1 steps down and c-1 steps to the right to get to the bottom-right corner of the grid.

The number we want to find is the combination of r1 and c1, and this can be easily computed using the binomial coeficient:

Let’s assume r1 = r-1 and c1 = c-1, and write some F# code to get the solution to our problem:

#light
open Microsoft.FSharp.Math.BigInt

let robot rows columns =
  let r1 = rows - 1I
  let c1 = columns - 1I
  (factorial (r1 + c1)) / ((factorial r1) * (factorial c1))

This first puzzle was very easy to solve, if you go to the Treasure Hunt website now, you’ll find the next exercise.

I’ll give it a try, if you are interested just drop a comment and we’ll discuss it here.

Once in a while I give a look at the web server log to find out how people landed in this blog and yesterday there was someone that entered the following search string into Google:

Given a random List of integers, write a function that removes all the duplicate values

This site appears as the first result, even if there is no solution for that problem, but I want to help you anyway, unknown visitor!

In fact, we can make use of the Set data type to easily solve the problem.

According to the definition, a Set represents a collection of elements without duplicates.
So, if we create a Set from the given list, all duplicate values will be automatically filtered.

This can be done in a single line, I’ll call the function nub because this is the name of the corresponding Haskell one:

let nub xs = xs |> Set.of_list |> Set.to_list

As I said, to return a List without duplicate values we just need to create a Set from it and then create a List from the new Set.

Do you think it is fair to act this way or should I say that I’m cheating?

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.

Encoding techniques are useless if you don’t have a way to restore the original message from the compressed data.

A couple of days ago, we saw how to implement the Run-Length Encoding (RLE) algorithm to encode an array of elements and now we are going to describe how to restore the original array.

To decode an array encoded with RLE we take the (length, element) couples, replicate each element by its length and then concatenate the output.

Let’s see the F# implementation:

#light

let decode src =
  let rec decode_block (num, elem) =
    match num with
    | 0 -> []
    | _ -> elem :: decode_block (num-1, elem)
    in List.concat (List.map decode_block src)

At line 8 we concatenate the output of the decode_block function applied to each couple of the src array.

Decode_block is a recursive inner function, which is very easy to understand. In fact, it just repeats elem the number of times indicated by num.

This is everything you need to know to encode and decode arrays (or anything else) by using the RLE algorithm. There are, of course, better compression techniques, if you want we can try to look at them in the future.

According to Wikipedia:

Run-length encoding (RLE) is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. This is most useful on data that contains many such runs: for example, relatively simple graphic images such as icons, line drawings, and animations.

Run-length encoding is used in fax machines. It is relatively efficient because most faxed documents are mostly white space, with occasional interruptions of black.

We will implement now the RLE algorithm in F#, writing a function that will take a list as argument and return a new list of couples (N,E), where N is the number of duplicates of the element E.

Let’s show the code:

#light

let pack src =
  let rec pack2 src tmp out =
    match src with
    | [] ->
        if (tmp = [])
          then out
        else (List.append out [tmp])
    | h::t ->
      if (tmp = [])
        then (pack2 t [h] out)
      else
        if (h = (List.hd tmp))
          then (pack2 t (h::tmp) out)
        else (pack2 t [h] (List.append out [tmp]))
    in (pack2 src [] [])

let encode src = List.map (fun b -> (List.length b, List.hd b)) (pack src)

let source = ['a'; 'a'; 'a'; 'a'; 'b'; 'c'; 'c'; 'a'; 'a'; 'd'; 'e'; 'e'; 'e'; 'e']
let answer = source |> encode

First of all we need to pack consecutive duplicates of list elements into sublists, and this is done by the pack function.

Inside pack we define an inner function, called pack2, which is not accessible from outside this block. This also allows us to transform each call like “pack src” to “pack2 src [] []“, adding two more arguments to the call.

This inner function moves elements from src to tmp while they are duplicates, and when a different element appears, the list contained in tmp is appended to out.

This process continues until the source list is exhausted, then the out list contains the packed output.

If you want to follow this procedure step-by-step, in the following image you can see the content of src, tmp and out at the beginning of each iteration, using ['a'; 'a'; 'a'; 'a'; 'b'; 'c'; 'c'; 'a'; 'a'; 'd'; 'e'; 'e'; 'e'; 'e'] as input.

Now, the actual run-length encoding is trivial. We just have to pack the source list and then apply a function on each element that takes a list of duplicates and returns a couple (N,E), where N is the number of elements and E is the first element (they are all the same).

In our case the final result will be:

[(4, 'a'); (1, 'b'); (2, 'c'); (2, 'a'); (1, 'd'); (4, 'e')]

In the next article I’ll present the decoding algorithm, even if I’m quite sure you can easily write it on your own.

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.

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?

When I was attending the first year of my university course, a teacher of mine used Haskell to teach us the basics of software development.

It was amazing, functional programming makes you think differently about programming.

In the functional paradigm functions are used in their real mathematical sense.
Hence, they are only computation objects and there is no information about state or mutable data.

Functional programming languages exist since more than 50 years ago, LISP is one of them, but they have never been seriously adopted outside the academia.

Now, the computer science world is gradually moving toward functional programming.

There is a lot of hype surrounding Erlang, a functional language originally developed by Ericsson, and in 2007 Microsoft presented F#, which is a multi-paradigm language targeting .Net and largely based on OCaml.

In this blog I’ll write down my progresses in learning this language and I hope that you can profit from my experience.

I’ll come back to you soon with the first article, if you want in the meanwhile you can start from the links on the right side of the page.

Bye!