Project Euler 19

Counting Sundays

You are given the following information:

  • 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

GitHub – The source code for the final solution is available at GitHub.  Instructions for how to run the project locally are shown in the README.md document.

First, let’s design an algorithm that will return the weekday on any given date past Monday January 1st 1900. After that we can just tweak our algorithm to count the number of Sundays that fell on the first of the month during the twentieth century.

The algorithm will take a day, month, and year and then return the weekday that occurred on that date.

Counting through the days

The method that will return the weekday would look something like this:

Here is the pseudocode for the algorithm that will count through the days.

 

Calculating the number of days in each month

Here is the pseudocode for the algorithm that will calculate the number of days in each month.

 

Counting the Sundays

In order to count the Sundays we just need to keep track of when it is Sunday on the first of the month. Also, there is no need to cycle through all of the days of a month. Instead we can just skip to the first day of each successive month.

The new algorithm will look like this:

Instead of returning the final weekday we will return the number of Sundays at the end of the algorithm.

Time to count the Sundays

Since we know that 1 Jan 1900 was a Monday, we can base our algorithm on that start date to begin counting through the days. In order to find the number of Sundays that fell on the first of the month during the twentieth century, we can take the number of Sundays our algorithm returns for (31 Dec 2000) and subtract the number of Sundays our algorithm returns for (1 Jan 1901).

If our method is called countSundays then our final result will look like this:

Our numSundays variable now holds the number of Sundays that fell on the first of the month during the twentieth century.

Special Cases and Error Conditions

At the start of the main algorithm it is a good idea to make sure that the input is valid. We should check to make sure that we are given a valid date and also that the date is after (1 Jan 1900) since our algorithm is designed for forward traversal only at the moment.

Solution in Java

GitHub – The source code for the final solution is available at GitHub.  Instructions for how to run the project locally are shown in the README.md document.

Here is the Main class that will implement the pseudocode.

 

Unit Testing

The following MainTest class will run unit tests to verify the functionality of the Main class.