A Confession, Before We Begin

I'm skipping problem 18. I solved it under the 1-minute time limit, but I wasn't happy with it. Problem 67 is the same as problem 18, but with a much larger input. My code ran for a long, long time and never came up with the answer. If you're interest in a really good F# solution to that problem, look here. You can compare it to my non-optimal solution:

let splitBy (c : char) (s : string) = 
    s.Split([|c|], System.StringSplitOptions.RemoveEmptyEntries)

let input = [|
    "75"
    "95 64"
    "17 47 82"
    "18 35 87 10"
    "20 04 82 47 65"
    "19 01 23 75 03 34"
    "88 02 77 73 07 63 67"
    "99 65 04 28 06 16 70 92"
    "41 41 26 56 83 40 80 70 33"
    "41 48 72 33 47 32 37 16 94 29"
    "53 71 44 65 25 43 91 52 97 51 14"
    "70 11 33 28 77 73 17 78 39 68 17 57"
    "91 71 52 38 17 14 91 43 58 50 27 29 48"
    "63 66 04 68 89 53 67 30 73 16 69 87 40 31"
    "04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"
    |]

let lineToArray l =
    l 
    |> splitBy ' ' 
    |> Seq.map int 
    |> Array.ofSeq

let values = input |> Array.map lineToArray
let penRow = values.Length - 2
for y in penRow..(-1)..0 do
    for x in 0..values.[y].Length-1 do
        values.[y].[x] <- values.[y].[x] + 
            max values.[y+1].[x] values.[y+1].[x+1]
values.[0].[0]

So, with that behind us, let's move on.

The Problem

You are given the following information, but you may prefer to do some research for yourself. 1 Jan 1900 was a Monday. Thirty days has September, April, June and November. All the rest have thirty-one, Saving February alone, Which has twenty-eight, rain or shine. And on leap years, twenty-nine. A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400. How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

The Solution

It may feel like cheating, but I'm not above using the .NET Framework's features to solve these problems. For example, I reduced a couple of problems down to using the BigInteger type. I am learning F# for all the advantages it gives me. I want to learn F# and everything about it. To me, that means not solving problems the language and framework have already solved for me. And that includes dates.

open System

let last = DateTime(2000,12,31)
let first = DateTime(1901,1,1)

let rec countSundays (day : DateTime) total =
    let dayValue() =
        if day.Day = 1 && day.DayOfWeek = DayOfWeek.Sunday
        then 1
        else 0

    if day > last then total
    else
        let next = day.AddDays(1.0)
        let newTotal = total + dayValue()
        countSundays next newTotal

countSundays first 0

The recursive function countSundays takes a day parameter and an accumulator total. When it reaches the last day, it returns the total it has accumulated. Otherwise, it increments the day and adds 1 to the total if the day is a Sunday and also the first day of the month.

Other Posts in This Series