Friday, August 17, 2012

Euler problem 19

I started writing this blog entry a year ago. It's about an Euler problem I solved in F#. The code makes more sense to me now than it did a year ago and I haven't touched F# since then. I guess I'm just way smarter now.



Solving Euler problem no. 19 is the solution I'm most proud of. It's the first problem that I solved in F# with no assistance by the 'net.

The problem:
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
It isn't an overly complex problem but there a couple of tricky aspects. The approach that I used was to start on the first Sunday of 1901 (6th Jan) and add seven days over and over (i.e., only counting Sundays) until the end of 2000. I could have used the .NET DateTime type to solve this problem very easily, but I decided to see if I could solve the problem using my own date type.

I solved the problem by using a few F# features, namely:
  • pattern matching
  • tuple
  • record
  • list
The first problem was February. February is a prickly month. Pattern matching will solve it! The febDays function accepts a year as a parameter and returns the number of days that February has.

    let febDays y = match y with
                            | y when y % 400 = 0 -> 29
                            | y when y % 100 = 0 -> 28
                            | y when y % 4 = 0 -> 29
                            | _ -> 28

After February was ready, I needed to know the number of days in any month, given the month (as a number) and the year. I used pattern matching again. Therefore,

    let daysInMonth (m, y) =
            match m with
            | 2 -> febDays y
            | 4 | 6 | 9 | 11 -> 30
            | _ -> 31

The other interesting function was to be able to add a day to a date. I did:

    let addDay date =
        match date.day with
        | d when d < 1 || d > daysInMonth(date.month, date.year) -> failwith "Not a valid day of the month."
        | d when d = daysInMonth(date.month, date.year) -> match date.month with
                                      | m when m < 1 || m > 12 -> failwith "Not a valid month."
                                      | m when m = 12 -> { day = 1; month = 1; year = date.year + 1}
                                      | _ -> { day = 1; month = date.month + 1; year = date.year}
        | _ -> { day = date.day + 1; month = date.month; year = date.year}

The code above isn't the whole solution, but it's the interesting parts. As you can see, I pretty much pattern matched the whole solution. It's a shame that C# doesn't have pattern matching because it's a really powerful language concept.

No comments:

Post a Comment