Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Counting Sundays without Python datetime module
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 datetime 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?
1 answer
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.
0 comment threads