Project Euler Problem #19:

Problem #19 is similar to Problem #17 in that it is very painful to implement unless you use an external library in whatever programming language you work in. The question reads:

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

Just by reading the facts this problem gives you, it should be clear that implementing it would be a pain in the neck. The amount of casework involving the different number of days in each month and the existence of leap years would be a massive pain to deal with. Luckily, Python has a library called datetime that is built specifically to ease this pain. Using the datetime library, we get the following solution:

Solution #1: Library Approach

The datetime library comes with two key object types for this sort of problem. The datetime object represents a specific instance in time whereas the timedelta object represents a span of time that can pass between any two datetimes. You could think of the datetime object as a definite point in space and the timedelta object as a vector. The datetime object has many attributes associated with it that make it perfect for this problem. It can recall the day of the week at any date in history, and it can return the day of the month. The timedelta object is useful for iterating through large spans of time which will be helpful for calculating the number of Sundays with this property.

My solution involved incrementing the start date until it was on a Sunday and then incrementing the start date a week at a time and counting the number of times it fell on the start of the month. I believed this would be simpler to implement than iterating through all of the months of each year and counting the number of Sundays. This resulted in the following implementation in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Library Approach to Project Euler Problem #19
 '''

 import datetime
 import time

 def projectEulerProblemNineteen(m1, d1, y1, m2, d2, y2):
     start = datetime.datetime(y1, m1, d1)
     end = datetime.datetime(y2, m2, d2)
     day = datetime.timedelta(days = 1)
     week = datetime.timedelta(days = 7)

     while(start.weekday()!=6 and start<=end):
         start+=day

     total = 0
     while(start<=end):
         if start.day==1:
             total+=1
         start+=week

     return total

 start = time.time()
 print projectEulerProblemNineteen(1, 1, 1901, 12, 31, 2000)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 171
 --- 0.000821828842163 seconds ---

 for input of start date = January 1, 1901, end date = December 31, 2000 
 '''

 

As shown above, Python libraries can save a lot of hassle when you need to solve a common problem that is difficult to implement.

Thanks for reading! See you tomorrow.