Post a Comment On: Scattered Thoughts

The next Project Euler problem on my list is number 19:

How many Sundays fell on the first of the month during the twentieth century?

For this problem it seemed to me that the easiest attack would be to create a sequence containing all the first days of each month in the given range and then filter it by testing whether the day in question was a Sunday. To make this work I would need a way of calculating the day of the week from the date. Fortunately, once again Wikipedia came to the rescue.

Following the algorithm from this article we define a few helper functions. To calculate the century we say:

let century y = 2 * (3 - (y/100)%4)
To determine whether we have a leap year:

let leap y =     if y%400 = 0         then true         else             if y%100 = 0                 then false                 else                     if y%4 = 0                         then true                         else false
For the month table I used a pattern match expression which takes the month number and whether it's a leap year or not:

let month l m =    match m with    |  0 -> if l then 6 else 0    |  1 -> if l then 2 else 3    |  2 -> 3    |  3 -> 6    |  4 -> 1    |  5 -> 4    |  6 -> 6    |  7 -> 2    |  8 -> 5    |  9 -> 0    | 10 -> 3    | 11 -> 5
Note that this match generates a warning to the effect that there are cases which may not be covered:

      match m with
  ----------^
stdin(19,11): warning FS0025: Incomplete pattern matches on this expression. For example, the value '12' may indicate a case not covered by the pattern(s).

In this case I am controlling all the inputs and I know that I would never make a mistake so I decided not to worry about it.

Next I needed to compute the year value:

let year y = y%100 + (y%100)/4
With these helpers, given a date tuple in the form (y, m, d) the day of the week it falls on is given by:

let day (y, m, d) = (century y + year y + month (leap y) m + d)%7
In this scheme Sunday is day 0.

The list of dates I want to examine are given by this sequence:

let dates =     seq {         for y in 1901..2000 do            for m in 0..11 do                yield (y, m, 1) }
Putting the pieces together to solve the puzzle:

dates |> Seq.filter (fun x -> day x = 0) |> Seq.length |> printfn "count = %A"