Friday 5 September 2008

Project Euler Problem 19: A Century of Sundays

There's a hard way and an easy way to solve Problem 19 in our ongoing struggle with Project Euler, where we're asked to count how many Sundays fell on the first of the month during the twentieth century - being software developers and thus virtuously lazy by nature we wouldn't consider the tedious way, getting out all those old diaries (wherein entries invariably finish around January 5th) and actually counting whilst flicking over the pages.

The hard way is to use the information given in the problem definition and devise an algorithm for calculating days of the week that each date falls on. The easy way uses with gratitude the brainpower the .Net Framework developers invested in their work. It's Friday: I'll take the easy way.

Thanks to C#3.0 and LINQ, the actual code to the solution is a one-expressioner:

[EulerProblem(19, Title = "How many Sundays fell on the first of the month during the twentieth century?")]
public class Problem19
{
    public long Solve()
    {
        DateTime endDate = new DateTime(2000, 12, 31);
        DateTime startDate = new DateTime(1901, 1, 1);

        return startDate
            .Unfold(date => date.AddMonths(1))
            .TakeWhile(date => date <= endDate)
            .Count(date => date.DayOfWeek == DayOfWeek.Sunday);
    }
}

If it's Friday for you as well then I'll let you read the following explanatory notes: otherwise, work it out for yourself!

Remember my Unfold extension method? The one that takes a seed value (startDate in this case) and generates a sequence by repeatedly applying an expression to previous value in the sequence to create the next. That combined with the TakeWhile method represent the functional-programming equivalent of the for loop. The Count overload that I'm using here counts every item in a sequence matching a particular criterion. So the code I have above is equivalent to this:

DateTime endDate = new DateTime(2000, 12, 31);
DateTime startDate = new DateTime(1901, 1, 1);

int count = 0;
for (DateTime date = startDate; date < endDate; date = date.AddMonths(1))
{
    if (date.DayOfWeek == DayOfWeek.Sunday)
    {
        count++;
    } 
}

return count;

3 comments:

Unknown said...

But in real 1/1/1901 is a Tuesday.

Dan said...

1200 first days of the month in a year.
7 days in a week.
1200/7

Dan said...

In a century. My mistake.

Post a Comment