Project Euler 19: Find how many Sundays fell on the first of the month during the twentieth century.
Project Euler 19 Problem Description
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)?
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 (or Monday, Tuesday, etc.) which are (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.
The Python program below cycle through each day and counts Sundays on the first of the month. It would be nice to simply cycle through the months, but Python doesn’t make that easy.
The calendar completes a full cycle every 400 years, so if a year is specified with 16 digits, as is the case at the HackerRank.com site, simply modulus it by 400 and add 2400 (arbitrary choice) to get the year into a range that works with Python. So 2016 and 2416 will use the same calendar. If you don’t cross a div by 400 year boundary, then the calendar repeats every 28 years, so 2016 and 2044 will also share the same calendar.
Here’s a site for generating calendars for any year: Calendar home
Read more: Patterns in the Perpetual Calendar
Project Euler 19 SolutionRuns < 0.001 seconds in Python.
import datetime as dt delta = dt.timedelta(days=1) dow = 6 #Sunday day = 1 #date start_date = s = dt.datetime(1901, 1, 1) end_date = dt.datetime(2000, 12, 31) c = 0 while start_date <= end_date: if start_date.day==day and start_date.weekday()==dow: c+=1 start_date += delta print "Days on the 1st of the month between", s.strftime("%d-%b-%Y"), \ "\nand", end_date.strftime("%d-%b-%Y"), "inclusive:", cUse this link to get the Project Euler 19 Solution Python source.
AnswerSlowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
- The estimate int(1200/7) was spot on in this case.
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.