Claudio Cherubino's blog Life of a Googler

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
Comments (3) Trackbacks (0)
  1. What does Some(x, x.AddMonths(1)) do? I can’t seem to find any documentation for this function.

  2. The trick is to understand how unfold works: it takes a function to be repeatedly evaluated to generate the items of a lazy list.

    This function can be of any type but has to return an option type, which is a union type whose members are None and Some(x).

    When the function returns None, unfold stops iterating and generating new items, but if the output is Some(x, y) then x is added to the lazy list as its next element while y is passed to the function for the next iteration.

    In the code above, for each iteration we take the current date and add one month to generate to next value to be checked.

  3. My solution is:

    #light
    
    let answer =
        {1901 .. 2000} |>
        Seq.map (fun y -> {1 .. 12} |> Seq.map (fun m -> (y,m,1))) |>
        Seq.concat |>
        Seq.map (fun (y,m,d) -> new System.DateTime(y,m,d)) |>
        Seq.map (fun dt -> dt.DayOfWeek) |>
        Seq.filter (fun dow -> dow = System.DayOfWeek.Sunday) |>
        Seq.length
    

Leave a comment

(required)

No trackbacks yet.