Select Page

Project Euler 19 Problem Statement

You are given the following information, but you may prefer to do some research for yourself.

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

The problem provides two dates, let’s call them a and b, where a≤b chronologically, and we are challenged to find the number of Sundays that occur on the first of the month within the date range, inclusively. This particular exercise has the date range fixed at 1/1/1901 and 12/31/2000.

Our solution was extended to allow any date range, any weekday and any day of the month and calculate the number of times that weekday lands on that day of the month.

Analytic method to estimate the count

There are 1200 months (therefore, 1200 firsts of the month) in 100 years (1/1/1901 – 12/31/2000). One in every 7 days is a Sunday which is (roughly) uniformly distributed over the date range. An estimate of 1200/7 Sundays should be close to the answer. As the date range widens this estimate becomes less precise because of leap years.

Using the Python datetime library

The Python program below leverages the datetime library and starts by initializing some parameters:

delta A timedelta of one day. By adding this to a date object the date is incremented by 1 day.
c A counter to tally matches.
targetDOW The Python datetime weekday numeric representation as: 0 for Monday, 1 for Tuesday, …, 6 as Sunday.
targetDate The day of the month, 1-31, that must coincide with the weekday.
yS, mS, dS Year, month, day. The start of the inclusive date range.
yE, mE, dE Year, month, day. The end of the inclusive date range.
import datetime as dt
delta, c, targetDOW, targetDate = dt.timedelta(days=1), 0, 6, 1
yS, mS, dS,   yE, mE, dE = 1901,1,1,   2000,12,31

Firstly, we will need to determine the number of years in the range. Secondly, we must normalize the years (yS and yE) to bring it within the acceptable year values of the datetime library.

yearDelta = yE-yS #number of years
yS = (yS%400) + 400 #normalized and non-zero

The perpetual calendar

The calendar completes a full cycle every 400 years, so 2016 and 2416 will use the same calendar. If you don’t cross a century, such as 1900 then the calendar repeats every 28 years, so 1916 and 1944 will share the same calendar. However, 1886 and 1914, although 28 years apart, will not because they cross the century 1900 which is not a leap year.

An exception to this rule is when a century is evenly divisible by 400, such as the year 2000, then you can safely add 28 years across those centuries to get identical calendars. For example, 1986 and 2014 are 28 years apart, cross a century, but still share the same calendar.

To find the number of Sundays on the 1st of the month within the inclusive date range we cycle through the years, day-by-day, until we find our first match. Then we continue our search week-by-week counting matches in our date range; this optimizes the search. If you wondered why we didn’t just cycle by months, then you have yet to realize the limits of the datetime library. dateutil is an extension to the standard Python package that offers more capability, but was unused for this exercise.

a = dt.datetime(yS, mS, dS)
b = dt.datetime(ys+yearDelta, mE, dE)
while a <= b:
    if a.day==targetDate and a.weekday()==targetDOW: 
        c+= 1
        delta = dt.timedelta(days=7)
    a += delta

HackerRank version

HackerRank keeps to the parameters of this problem with the exception of allowing 17-digit years. Normalizing, as mentioned above, makes this a non-issue. They also, restrict the range to 1000 years.

Python 2.7 Source

Last Word

Here’s a site for generating calendars for any year: Calendar home

Read more: Patterns in the Perpetual Calendar

Also, some think that using date or calendar libraries is taking unfair advantage when solving these kind of problems. Nothing could be further from the truth. You need to leverage well vetted software in order to speed development time and reduce errors. Using established extensions and packages is simply good practice.