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)?
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:
||A counter to tally matches.|
||The day of the month, 1-31, that must coincide with the weekday.|
||Year, month, day. The start of the inclusive date range.|
||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 (
yE) to bring it within the acceptable year values of the
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
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 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
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.