Problem 19: Counting Sundays is another one of the type where one doesn’t need a mathematical insight and just implement a complicated logic.

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

Using Pythons amazing standard library, this problem is very easy to solve. Just start, iterate through all the days and then check how many sundays there are that fall onto the first of a month. Done.

def solution_date_class() -> int:
    start = datetime.date(1901, 1, 1)
    end = datetime.date(2000, 12, 31)
    cur = start
    num_sundays = 0
    while cur <= end:
        if cur.weekday() == 6 and cur.day == 1:
            num_sundays += 1
        cur += datetime.timedelta(days=1)
    return num_sundays

We get 171 within 20.206 ms.

Okay, but is using the standard library cheating here? I think that in any production setting you should use as much tested code as you can do, write the least amount yourself unless the dependencies bring their own problems. The standard library is safe, though. For learning it might be sensible to do things manually.

We need a function to increment a date to the next date. There we need to take all the leap year rules into account.

Date = Tuple[int, int, int]


def increment_day(date: Date) -> Date:
    year, month, day = date
    day += 1
    if (
        day > 31
        or (day > 30 and month in [4, 6, 9, 11])
        or (
            day > 29
            and month == 2
            and year % 4 == 0
            and (year % 100 != 0 or year % 400 == 0)
        )
        or (
            day > 28
            and month == 2
            and (year % 4 != 0 or (year % 100 == 0 and year % 400 != 0))
        )
    ):
        day = 1
        month += 1
    if month > 12:
        month = 1
        year += 1
    return year, month, day

And then we can iterate through the dates using that and track the weekday along with them.

def solution_manual() -> int:
    start = (1901, 1, 1)
    end = (2000, 12, 31)
    cur_date = start
    cur_weekday = 1
    num_sundays = 0
    while cur_date <= end:
        if cur_weekday == 6 and cur_date[2] == 1:
            num_sundays += 1
        cur_date = increment_day(cur_date)
        cur_weekday = (cur_weekday + 1) % 7
    return num_sundays

This is actually a bit faster, it just takes 7.8 ms.

Either way, this was more about implementing the detailed logic with the leap years, nothing more.