Project Euler Problem 19 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. 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 is 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 and is (roughly) uniformly distributed over the date range. An estimate of 1200÷7 Sundays will be close to an 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 them within the acceptable yearly 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 how many Sundays fall 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.
HackerRank keeps to the parameters of this problem with the exception of allowing 17–digit years (because knowing the day of the week the sun explodes is strangely comforting). Normalizing, as mentioned above, makes this a non–issue. The date range is restricted to 1000 years.
Python Source Code
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 yearDelta = yE-yS # number of years yS = (yS%400) + 400 # normalized and non-zero 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 print (["Mon","Tue","Wed","Thu","Fri","Sat","Sun"][targetDOW],"on day", targetDate, "of the month:", c)
- The estimate int(1200÷7) was spot on in this case.
- 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.