Project Euler Problem #19 Counting Sundays

Spoiler Alert: As the About page of Project Euler says, "Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery." If you are currently attempting to solve this problem in the archives, please do not continue to read this post. I personally worked through all the problems I post on this blog and it has brought me immense satisfaction. 

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)?

Solution: 

Although this problem sounds a little hairy at first glance, it's really not that bad.

Here's the logic I used to solve it. You may want to look at a calendar to convince yourself of some of the points.

• Every month has at least 28 days so we can use that as a baseline
• Today is Saturday. After 28 days, it will be Saturday again. The same follows for any day of the week because 28 days is exactly 4 weeks. 
• As long as it's not a leap year, February has 28 days, meaning that whatever day of the week February 1 is, March 1 will be the same day of the week. 
• On leap years, March 1 will be the following day of the week. E.g. if February 1 is a Sunday, March 1 will be a Monday during leap years.
• Every year, the months after September, April, June and November start on the same day of the week as the previous month plus 2. E.g., if September 1 is a Wednesday, October 1 will be a Friday. The same calculation holds for the other three months following 30-day months.
• The remaining months have 31 days, so the months which follow them will begin on the same day of the week as the previous month plus 3. E.g., if January begins on a Friday, February will begin on a Monday. 
• The problem tells us that January 1, 1900 was a Monday, but we are asked about the years 1901-2000, so I looked up January 1, 1901, and found it was a Tuesday.
• "There is a leap year every year whose number is perfectly divisible by four - except for years which are both divisible by 100 and not divisible by 400." -Skywise Unlimited
• This means 2000 is a leap year, because it is divisible by 400, but 1900 is not, because it is not divisible by 400.

Now we just need to loop through 100 years, determining whether or not it is a leap year, and calculating the first day of every month. If it is a Sunday, we will add it to the total. 

In C#, it will look something like this:

Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            bool leapYear;
            int dayOfWeek = 3;
            int startingSundays = 0;            
            List<int> thirties = new List<int>() { 4, 6, 9, 11 };
            List<int> thirty_ones = new List<int>() { 1, 3, 5, 7, 8, 10, 12 };
 
            //Cycle through the century
            for (int year = 1; year < 101; year++)
            {
                //Every 4 years is a leap year
                leapYear = (year % 4 == 0) ? true : false;
 
                //Cycle through the months
                for (int month = 1; month < 13; month++)
                {
                    //Handle thirty-day months
                    if (thirties.Contains(month)) { dayOfWeek += 2; }
                    //Handle thirty-one day months
                    else if (thirty_ones.Contains(month)) { dayOfWeek += 3; }
                    //Handle Februaries
                    else if (month == 2) { dayOfWeek = (leapYear) ? dayOfWeek + 1 : dayOfWeek; }
                    startingSundays = (dayOfWeek % 7 == 0) ? startingSundays + 1 : startingSundays;
                }
            }

            stopwatch.Stop();
            Console.WriteLine($"Time elapsed (ms): {stopwatch.Elapsed.TotalMilliseconds}");
            Console.WriteLine($"Months starting with Sunday: {startingSundays}");
            Console.ReadLine();

It takes a little over 0.15 milliseconds to run on my machine.

I've avoided putting the answer in the solution, just in case someone solving the problem on Project Euler ignored the Spoiler Alert. But this method will provide the correct answer.