Project Euler Problem 19 Solution

Project Euler Problem 19 Solution

Counting Sundays

by {BetaProjects} | Project Euler & HackerRank

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

Solution

Dog cartoon about datesThe 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:

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 for 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 them within the acceptable yearly 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 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 datetime library. dateutil is an extension to the standard Python package that offers more capability, but was unused for this exercise.

HackerRank version

HackerRank logo

Solves all test cases for Hackerrank Project Euler Problem 19

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)

Last Word