// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (24 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 19 Solution

Project Euler 19 Solution

Project Euler 19: Find how many Sundays fell on the first of the month during the twentieth century.


Project Euler 19 Problem Description

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

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

Analysis

Project Euler 19
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.

Using the Python datetime library

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

dD

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.
dowx

The Python datetime weekday numeric representation as: 0 for Monday, 1 for Tuesday, …, 6 as Sunday.
datex

The day of the month, 1-31, that must coincide with the weekday.
Y1, M1, D1

Year, month, day. The beginning of the inclusive date range.
Y2, M2, D2

Year, month, day. The end of the inclusive date range.
import datetime as dt
dD, c, dowx, datex = dt.timedelta(days=1), 0, 6, 1
Y1, M1, D1,   Y2, M2, D2 = 1901,1,1,   2000,12,31

We need two parameters before we start our search. Firstly, because HackerRank Project Euler 19 can specify a year with 17 digits we will need to determine the number of years in the range. Secondly, we must normalize the years (Y1 and Y2) to bring it within the acceptable year values of the datetime library.

dY = Y2-Y1 #number of years
Y1 = (Y1%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 and 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(Y1, M1, D1)
b = dt.datetime(Y1+dY, M2, D2)
while a <= b:
	if a.day==datex and a.weekday()==dowx: c+= 1; dD=dt.timedelta(days=7)
	a += dD
Project Euler 19
This program and method
solves all test cases for
Project Euler 19 on HackerRank

Afterthoughts

  • 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.

Project Euler 19 Solution last updated

Discussion

No comments yet.

Post a comment