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)?
https://projecteuler.net/problem=19
Ugh, dates and times. They are the bane of any programmer. This video by Computerphile is an excellent explanation of why they are a massive headache to work with. Whenever it comes to dates and times, it’s strongly recommended to rely on established libraries. No point in re-inventing the wheel of time with something so critical.
But that’s no fun! Finding the day of a date is a common problem and it was solved by John Horton Conway, an esteemed mathematician. He invented the Doomsday algorithm. That sounds pretty ominous. He noticed that certain dates of any year always fall on the same day. These dates are known as Doomsdays. If the day of a doomsday is known, it’s simple to count backwards or forwards to the date in question.
Here’s a step-by-step breakdown and implementation of the doomsday algorithm adapted from this link.
Step 1: Memorizing weekdays as numbers
weekdays_as_number = {'Sunday': 0, 'Monday': 1,
'Tuesday': 2, 'Wednesday': 3,
'Thursday': 4, 'Friday': 5,
'Saturday': 6}
Thank goodness that computers have much better memories than us.
Step 2: Memorizing the anchor days
Doomsdays are calculated relative to these anchor days which varies century by century. Calendars repeat every 400 years, so only four anchor days need to be memorized. For the 1800s, it’s Friday. For the 1900s, it’s Wednesday. For the 2000s, it’s Tuesday. For the 2100s, it’s Sunday. Anchor days of centuries outside this range are calculated by repeating this pattern forwards or backwards. For example, the 1400s would be figured out by working backwards. 1700s – Sunday. 1600s – Tuesday. 1500s – Wednesday. 1400s – Friday!
In computerese, modular arithmetic is needed to figure out this pattern. The first two digits of a year is calculated then 2 is subtracted from it. This number modulo 4 results in a number that is used to look up the anchor day.
def get_anchor_day_of_century(n):
"""Finds the year n's century's anchor day"""
first_two_digits = n // 100
lookup_number = (first_two_digits - 2) % 4
return {0: 'Friday', 1: 'Wednesday', 2: 'Tuesday', 3: 'Sunday'}[lookup_number]
Step 3: Calculating the doomsday of any given year
First, take the last two digits of the year and call it n. Find the number of times 12 can go fully into n. Call the result a.
a = n // 12
Second, find the remainder of the previous division. Call this b.
b = n % 12
Third, find the number of times 4 can go fully into b. Call this c.
c = b // 4
Fourth, represent the century’s anchor day as a number. Call this d.
d = weekdays_as_number[get_anchor_day_of_century(year)]
Fifth, add ’em up. Call this e.
e = a + b + c + d
Finally, find the remainder of e divided by 7. This number corresponds to a day – the doomsday of the year.
doomsday_number = e % 7
Step 4: Move from the doomsday to the date in question
There are a bunch of doomsdates where they all share the same day – the doomsday. Some of these include the last day of February, March 7, April 4, May 9, June 6, July 11, August 8, September 5, October 10, November 7, and December 12. The doomsdate for January is the 3rd if it is a non-leap year, the 4th if it is a leap year. Two dictionaries for both types of years are needed. Some logic is also needed for determining if a given year is a leap year.
doomsdates_common = {1:3, 2:28, 3:7, 4:4, 5:9, 6:6, 7:11, 8:8, 9:5, 10:10, 11:7, 12:12}
doomsdates_leap = {1:4, 2:29, 3:7, 4:4, 5:9, 6:6, 7:11, 8:8, 9:5, 10:10, 11:7, 12:12}
def is_leap_year(year):
if year % 4 == 0:
if year % 100 == 0:
if year % 400 == 0:
return True
else:
return False
else:
return True
else:
return False
def difference_between_date_and_doomsdate(month, day, year):
if is_leap_year(year):
doomsdate = doomsdates_leap[month]
else:
doomsdate = doomsdates_common[month]
return doomsdate - day
Now all of these functions and dictionaries can be put together to define day_of_date.
def day_of_date(month, day, year):
last_two_digits_of_year = int(str(year)[-2:])
a = last_two_digits_of_year // 12
b = last_two_digits_of_year % 12
c = b // 4
d = weekdays_as_number[get_anchor_day_of_century(year)]
doomsday_number = (a + b + c + d) % 7
day_number = (doomsday_number - difference_between_date_and_doomsdate(month, day, year)) % 7
return {v:k for k,v in weekdays_as_number.items()}[day_number]
Now all that remains is to iterate every month from January 1, 1901 to December 1, 2000 and count when these dates fall on a Sunday.
sundays = 0 for year in range(1901, 2001): for month in range(1, 13): if day_of_date(month, 1, year) == 'Sunday': sundays += 1 print(sundays)
The answer is 171. Pretty cool! Thanks, Dr. Conway. Now I’d be remiss if I didn’t show the “batteries-included” Pythonic solution. datetime is much more robust than this implementation that breaks if the year is something crazy.
import datetime
sundays = 0
for year in range(1901, 2001):
for month in range(1, 13):
day = datetime.date(year, month, 1)
if day.weekday() == 6: # datetime's week begins on Monday which is numbered as 0
sundays += 1
print(sundays)