Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users

Dashboard
Notifications
Mark all as read
Code Reviews

Counting Sundays without Python date module

+3
−0

The problem

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

The solution

def is_century(year):
	return year % 100 == 0

def is_leap_year(year):
	if is_century(year):
		return year % 400 == 0 
	else:
		return year % 4 == 0

def get_day_count(year, month):
	if month == 2 and is_leap_year(year):
		return 29
	elif month == 2:
		return 28
	elif month in [4, 6, 9, 11]:
		return 30
	else:
		return 31

def solution(start_day, start_month, start_year, end_day, end_month, end_year):
	current_day, current_month, current_year = start_day, start_month, start_year
	days = 0
	sundays = 0
	
	while current_day != end_day or current_month != end_month or current_year != end_year:
		if days % 7 == 0 and current_day == 1:
			sundays += 1

		days += 1

		if current_day == get_day_count(current_year, current_month):
			current_day = 1
			if current_month == 12:
				current_month = 1
				current_year += 1
			else:
				current_month += 1
		else:
			current_day += 1
	
	return sundays

print(solution(1, 1, 1901, 31, 12, 2000))

I solved Project Euler Problem 19 with Python. My goal was to solve this without the date module, and handling the calendar part on my own.

As the problem states the start date is a Monday, I counted the next Mondays that fell on the first of the month using this condition: if days % 7 == 0 and current_day == 1:, being days the number of days I counted so far inside the loop.

What can be improved? Have I overcomplicated some part of the code?

Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

0 comment threads

1 answer

+5
−0

First of all, I've added a print in your code to show the dates:

if days % 7 == 0 and current_day == 1:
    print(f'{current_year}-{current_month:>02}-{current_day:>02}')
    sundays += 1

And in the first lines I've noticed that you're actually counting the Tuesdays:

1901-01-01
1901-10-01
1902-04-01
1902-07-01
1903-09-01
1903-12-01
... # all the dates are Tuesdays

It was a coincidence that the result was "correct" (171), but in programming we shouldn't rely on coincidences.


Calculating the day of month

I didn't use the given information (I didn't care about Jan 1st 1900 being a Monday). Instead, I cheated ported/adapted this Java code to Python, in order to get the day of week, given a day, month and year:

def isLeapYear(year): # no need to break in 2 functions
    return (year % 4 == 0) and (year % 100 != 0 or year % 400 == 0)

# number of days in a 400 year cycle
DAYS_PER_CYCLE = 146097

# The number of days from year zero to year 1970.
# There are five 400 year cycles from year zero to 2000.
# There are 7 leap years from 1970 to 2000.
DAYS_0000_TO_1970 = (DAYS_PER_CYCLE * 5) - (30 * 365 + 7)

def toEpochDay(day, month, year):
    total = 365 * year;
    if year >= 0:
        total += (year + 3) // 4 - (year + 99) // 100 + (year + 399) // 400
    else:
        total -= year // -4 - year // -100 + year // -400
    total += (367 * month - 362) // 12
    total += day - 1;
    if month > 2:
        total -= 1
        if not isLeapYear(year):
            total -= 1
    return total - DAYS_0000_TO_1970;

# it returns values from 0 (Monday) to 6 (Sunday)
def getDayOfWeek(day, month, year):
    return (toEpochDay(day, month, year) + 3) % 7

And, considering that the problem only wants to know about the first day of each month, there's no need to advance one day at a time. I can advance the whole month instead:

# considering that day of month is always 1
def count_sundays(start_month, start_year, end_month, end_year):
    current_month, current_year = start_month, start_year
    sundays = 0

    while current_month != end_month or current_year != end_year:
        if getDayOfWeek(1, current_month, current_year) == 6:
            sundays += 1

        # go to next month (considering that day is always 1)
        if current_month == 12:
            current_month = 1
            current_year += 1
        else:
            current_month += 1
    return sundays

print(count_sundays(1, 1901, 12, 2000)) # 171

If you want a more generic solution that accepts any day of month, you can still advance one month at a time. But if the day is, let's say, 31, we can skip months that don't have 31 days. Like this:

days_in_month = [None, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

def count_dow(start_day, start_month, start_year, end_day, end_month, end_year, dow):
    current_day, current_month, current_year = start_day, start_month, start_year
    count = 0

    while current_day != end_day or current_month != end_month or current_year != end_year:
        if getDayOfWeek(current_day, current_month, current_year) == dow:
            #print(f'{current_year}-{current_month:>02}-{current_day:>02}')
            count += 1

        # go to next month (skipping months that don't have current_day)
        while True:
            if current_month == 12:
                current_month = 1
                current_year += 1
            else:
                current_month += 1
            last_day = days_in_month[current_month]
            if current_month == 2 and isLeapYear(current_year):
                last_day = 29
            # this month has the current_day
            if current_day <= last_day:
                break

    return count

# last parameter is from 0 (Monday) to 6 (Sunday)
print(count_dow(1, 1, 1901, 1, 12, 2000, 6)) # 171

Testing

I've made a quick test, using the timeit module:

from timeit import timeit

# run 100 times each test
params = { 'number' : 100, 'globals': globals() }

# print the execution time in seconds

# considering day is always 1
print(timeit('count_sundays(1, 1901, 12, 2000)', **params))

# generic version (but still skipping one month at a time)
print(timeit('count_dow(1, 1, 1901, 1, 12, 2000, 6)', **params))

# your solution (without printing the dates, of course)
print(timeit('solution(1, 1, 1901, 31, 12, 2000)', **params))

Of course the execution time will vary according to many conditions (such as hardware, etc), in my machine I've got:

0.09944487499888055
0.09361006100152736
1.0343273129983572

Therefore, the solutions above were about 10 times faster.


Using the given information

Considering that 1900 isn't a leap year and Jan 1st 1900 is a Monday: 1900 has 365 days, and 365 % 7 is 1 (52 weeks plus one day, hence, the last day of 1900 is also a Monday, so Jan 1st 1901 is a Tuesday).

Would I be cheating if, knowing that the start date is a Tuesday, I'd start my count on the next Sunday (Jan 6th)? With this, I could just add 7 days, making the proper adjustments, and increment the count if the result is 1:

def count():
    current_day, current_month, current_year = 6, 1, 1901 # "cheating"
    end_day, end_month, end_year = 1, 12, 2000 # I'm lazy and not using parameters
    c = 0
    while True:
        last_day = days_in_month[current_month] # it's the same list as in the previous examples
        if current_month == 2 and isLeapYear(current_year): # isLeapYear is the same function defined above
            last_day = 29
        # add 7 days
        current_day += 7
        if current_day > last_day: # month changed
            current_day -= last_day
            if current_month == 12:
                current_month = 1
                current_year += 1
            else:
                current_month += 1
        if current_year > end_year:
            break
        if current_day == 1:
            c += 1
    return c

I didn't defined parameters in the function, but that can be easily adapted. It was just to show the algorithm, given that we know the first Sunday in the interval (assuming you needed to use all the given information).

Testing this with timeit, it was a little bit faster than the previous solutions.

If you didn't like the "cheat", you could start at Jan 1st and make a small loop, adding one day at a time, until it finds a Sunday (perhaps using the getDayOfWeek function). Then, I can start the algorithm above, iterating each 7 days.

Why does this post require moderator attention?
You might want to add some details to your flag.

1 comment thread

General comments (1 comment)

Sign up to answer this question »