I have decided that I would like to determine the current day of the week. The problem is that I have very specific amnesia where I can only remember the day, month, year, but not the weekday. Luckily my long-term memory is unaffected and I know that the first day in in the common era was a Monday. My best chance is probably using some programming to figure this out. But I don’t have time to lookup the method call to get the weekday, so I will combine some straight-up math.
I decided to figure out the current weekday after seeing the programming challenge listed at programthis.net. Then I realized that there is more to it than what I had initially thought. First-off I had to know that the first day of the common era was a Monday — really I just had to know the weekday for any specific date, but it’s easiest to begin calculating from January 1st year zero.
This first thing to find out is the number of days that have passed from 0000-01-01 to the start of the current year. An approximation would be to multiple last year’s number by 365. Taking into account leap years is easy too; divide the current year by 4 and drop any fraction. Except leap years are not that simple.
Any year divisible by four and divisible by one hundred is not a leap year. If the last two digits of a number are divisible by four or are “00″ then the number is divisible by four (don’t you have your divisibility rules memorized?). So any year that can be divided by one hundred is automatically divisible by four as well. Divide the year by 100 and drop the fraction to get the number of years that are divisible by 4 and 100.
But again, leap years are not that simple. Any year that is divisible by 100 and 400 is a leap year. And again any year divisible by 400 is automatically divisible by 100 so we only need to check year numbers that are divisible by 400 by dividing the year by 400 and dropping the fraction.
It’s actually well laid out in code:
prev_year = y-1 # naive number of days before start of this given year days_before_year = prev_year*365 # add a naive calculation of leap days days_before_year += prev_year/4 # subtract leap days that were divisible by 100 days_before_year -= prev_year/100 # add back leap days that were divisible by 400 days_before_year += prev_year/400
The next step if getting the number of days between the start of the year and the current date. Much easier. The days of the current month are super easy — just todays day minus one. The other months are almost as easy, but requires a bit of prior knowledge. I need to know the number of days in each month to be able to add up all the previous months. Again with the leap years. It’s easy to determine if the current year is a leap year and the current month is after February.
month_days = [0,31,28,31,30,31,30,31,31,30,31,30,31]
# number of days that have passed this month
days_this_year = d-1
# number of days that have been in previous months
days_this_year += sum(month_days[:m])
# add a leap day for this year?
if m > 2 and (y%4==0 and not y%100==0 or y%400==0):
days_this_year += 1
Add those results together and it is the number of days that have passed since 0000-01-01 while taking into account leap days. The remainder of that number divided by 7 gives the number of days after Monday (recall 0000-01-01 was a Monday) for the current weekday.
weekdays = ['Mon','Tue','Wed','Thu','Fri','Sat','Sun'] days_after_monday = (days_before_year + days_this_year) % 7 weekday = weekdays[days_after_monday]
Add all that together and I can finally know the current weekday:
def day_of_week(y, m, d):
prev_year = y-1
# naive number of days before start of this given year
days_before_year = prev_year*365
# add a naive calculation of leap days
days_before_year += prev_year/4
# subtract leap days that were divisible by 100
days_before_year -= prev_year/100
# add back leap days that were divisible by 400
days_before_year += prev_year/400
month_days = [0,31,28,31,30,31,30,31,31,30,31,30,31]
# number of days that have passed this month
days_this_year = d-1
# number of days that have been in previous months
days_this_year += sum(month_days[:m])
# add a leap day for this year?
if m > 2 and (y%4==0 and not y%100==0 or y%400==0):
days_this_year += 1</pre>
weekdays = ['Mon','Tue','Wed','Thu','Fri','Sat','Sun']
days_after_monday = (days_before_year + days_this_year) % 7
weekday = weekdays[days_after_monday]</pre>
return weekday
# as a single expression
dow = lambda y,m,d: (['Mon','Tue','Wed','Thu','Fri','Sat','Sun']
[((y-1)*365 + (y-1)/4 - (y-1)/100 + (y-1)/400 +
sum([0,31,28,31,30,31,30,31,31,30,31,30,31][:m]) +
d-1 +
(1 if m>2 and
(y%4==0 and not y%100==0 or y%400==0)
else 0))
% 7])
if __name__ == '__main__':
from datetime import datetime
today = datetime.today()
print day_of_week(today.year, today.month, today.day)
print dow(today.year, today.month, today.day)
Also included is a lambda version if you don’t have time for all that formatting. Finally I will always know what day of the week it is.
Curious, I decided to check out how Python’s datetime module calculates the weekday. After downloading the Python source code I found the datetime module is written in c and is in modules/datetimemodule.c.
Here is the weekday function call; it returns an integer for the weekday and uses the same monday as above for reference:
/* Day of week, where Monday==0, ..., Sunday==6. 1/1/1 was a Monday. */
static int
weekday(int year, int month, int day)
{
return (ymd_to_ord(year, month, day) + 6) % 7;
}
What is ymd_to_ord? It returns the number of days before the date given. The code follows:
/* year, month, day -> ordinal, considering 01-Jan-0001 as day 1. */
static int
ymd_to_ord(int year, int month, int day)
{
return days_before_year(year) + days_before_month(year, month) + day;
}
Following the rabbit trail further shows the days_before_year function:
/* year -> number of days before January 1st of year. Remember that we
* start with year 1, so days_before_year(1) == 0.
*/
static int
days_before_year(int year)
{
int y = year - 1;
/* This is incorrect if year <= 0; we really want the floor
* here. But so long as MINYEAR is 1, the smallest year this
* can see is 0 (this can happen in some normalization endcases),
* so we'll just special-case that.
*/
assert (year >= 0);
if (y >= 0)
return y*365 + y/4 - y/100 + y/400;
else {
assert(y == -1);
return -366;
}
}
This more robust than my implementation, but I only wanted to know today’s weekday and today before the common era, so it’s cool.
The corresponding days_before month they have an array with pre-summed days before the current month:
static int _days_before_month[] = {
0, /* unused; this vector uses 1-based indexing */
0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334
};
/* year, month -> number of days in year preceeding first day of month */
static int
days_before_month(int year, int month)
{
int days;
assert(month >= 1);
assert(month <= 12);
days = _days_before_month[month];
if (month > 2 && is_leap(year))
++days;
return days;
}
Ugh, it calls a function to determine if it is a leap year:
/* year -> 1 if leap year, else 0. */
static int
is_leap(int year)
{
/* Cast year to unsigned. The result is the same either way, but
* C can generate faster code for unsigned mod than for signed
* mod (especially for % 4 -- a good compiler should just grab
* the last 2 bits when the LHS is unsigned).
*/
const unsigned int ayear = (unsigned int)year;
return ayear % 4 == 0 && (ayear % 100 != 0 || ayear % 400 == 0);
}
The Python stdlib implementation is just about exactly they same as what I came up with, except it is more robust. It will get angry if you try to give a year before the common era or a month that is invalid. I however believe that users are responsible adults and will not expect reasonable results if they want the weekday for month 18 of year -204.