Project Euler Probem 19: Counting Sundays

What is a date? Usually, we think of a formatted string, such as 1/12/2014; or possibly Sunday, 1/12/2014, if we want to include the corresponding weekday. It’s important to emphasize formatted string in the previous sentence, because there are–as your own preferences inform you–many different ways to represent a date. However, the mathematical content is fairly simple. A date consists of a year number y\in\mathbb{N}, a month number m\in\left\{1,\ldots,12\right\}, and a day number d\in D(y,m), where the set D depends on the month m and the year y. Think of leap years and months with varying number of days: April, June, September, and November have 30 days, while February has 28 or 29 days depending on whether it’s a leap year. Lastly, there is the weekday w(m,d,y)\in\left\{0,\ldots,6\right\}. Here, Sunday = 0, Monday = 1,…, and Saturday = 6.

A curious property of dates is the varying day of the week on which they fall. One year, you’re lucky and your birthday falls on a Friday or Saturday; the next year it falls on the dreaded Monday. The American reader will know that Thanksgiving is never the same date in consecutive years, as it by definition falls on the last Thursday of November. What’s going on mathematically? A bit of arithmetic modulo seven.

Ordinarily, there are 365 days occur between a fixed day of a fixed month in two consecutive years. As there are seven days in a week, the weekday becomes

\displaystyle i+365\pmod{7}=i+1\pmod{7},\indent\forall i\in\left\{0,\ldots,6\right\}

since 365\pmod{7}=1. Things change during a leap year, in which there are 366 days. For a date (m,d,y) before February 29, there has been no additional day in the year so far, hence the weekday shifts ordinarily by one. The weekday advances by two the next year: w(m,d,y+1)=i+2\pmod{7}. For a date (m,d,y) on or after February 29, there has been additional day in the year so far, hence the weekday shifts by two: w(m,d,y)=i+2\pmod{7}.

An interesting problem–problem 19 to be specific–that rests on this property came to my attention while browsing Project Euler. The statement of problem 19 has been reproduced below:

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

My first solution basically solves the problem by brute force; it’s not very elegant. It calculates the weekday of every date between 1/1/1901 and 12/31/2000, creates a new list of “first of the month”s falling on Sunday, and lastly calculates length of this list. As usual, I have implemented this solution in Python.

I have another solution that does far less work, which I will post later.

#Project Euler Problem 19

#We represent dates as a tuple.
#We assign each day of the week an integer.
#Sunday = 0, and Saturday = 6.

def next_day(dt_tuple):
    if ((dt_tuple[2] % 4 == 0) and (dt_tuple[2] % 100 != 0)) or (dt_tuple[2] % 400 == 0):
        leap_year = True
        feb_days = 29
    else:
        leap_year = False
        feb_days = 28
    month_days = {1 : 31,  #Create a dictionary storing the number of days in each month
                    2 : feb_days,
                    3 : 31,
                    4 : 30,
                    5 : 31,
                    6 : 30,
                    7 : 31,
                    8 : 31,
                    9 : 30,
                    10 : 31,
                    11 : 30,
                    12 : 31}
    if dt_tuple[1] == month_days[dt_tuple[0]]:  #If the day equals last day of month, go to first of next month
        if dt_tuple[0] < 12:
            return (dt_tuple[0]+1, 1, dt_tuple[2], (dt_tuple[3]+1) % 7)
        else:
            return (1, 1, dt_tuple[2]+1, (dt_tuple[3]+1) % 7)
    else:
        return (dt_tuple[0], dt_tuple[1]+1, dt_tuple[2], (dt_tuple[3]+1) % 7)

dates = []  #Initialize a list to store dates
dt_tuple = (1,1,1901,2) #Initialize a date tuple. 1/1/1900 was a Monday and 1900 is not a leap year

while (dt_tuple[2] < 2001):
    dates.append(dt_tuple)
    dt_tuple = next_day(dt_tuple)

matches = [i for i in dates if (i[1] == 1) and (i[3] == 0)]
print matches
print len(matches)
Advertisements
This entry was posted in cs.DS, Problem Solving, Progamming, Python. Bookmark the permalink.

2 Responses to Project Euler Probem 19: Counting Sundays

  1. v3gas says:

    Would you mind posting the other solution? I solved it using modulo 7 to keep track of the weekdays, and for-loops and if-statements to keep track of months and years. It’s in the link below.

    http://pastebin.com/wdKKtuC2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s