Today we will try to solve the following problem:

Given year, month and day tell what day of week it is (Sunday, Monday etc.).

INPUT: Three numbers `year`, `month` and `day` representing valid date. `year` must be `> 0`, months and days are numbered from 1. For example 3 January 2016 will be represented by `year = 2016`, `month = 1` and `day = 3`.

OUTPUT: A single number that represents day of week, we assume that `0` will represent Sunday, `1` Monday, `2` Tuesday, …, `6` Saturday.

We will start by solving simpler problem:

Assume that you know what day of week is 31th December of previous year. Given day and month in current year tell what day of week it is.

Formula to solve this problem is simple:

Only tricky part is that `number_of_days_since_year_start(month, day)` must take into account leap years.

Testing for leap years is easy:

Now we can write `number_of_days_since_year_start` function:

And finally we may implement `day_of_week` function:

Let’s test it:

Looks like it works, so now we may return to our original problem.

Let’s start with this Wikipedia article which tell us that 1 January 0001 is a Monday. But for us it will be more convenient to count days not from 1 January of given year but from 31 December of the previous year. It is interesting that there is no year 0000, year that precedes year 0001 or 1 AD is 1 BC (or in other words years are intervals not points). To sum up we start counting days from 31 December 1 BC.

We already have function that returns day of week if we know day of week of 31 December of the previous year. We can find out day of week of any date using formula:

Let’s start by implementing `number_of_days_in_years(year)` function that will return number of days since 31 December 1 BC up to 31 December of given `year`:

To count number of leap years I used inclusion-exclusion principle.

And finally we may implement our `day_of_week` routine:

Now we may test it but we must be careful here. Our routine returns day of week using Gregorian calendar that was introduced in 1582 AD (or later depending on country). If we want to test it in Java we should avoid using `GregorianCalendar` class since it will switch to Julian calendar mode for years before 1582 AD. More informations on this subject can be found in this Stackoverflow question. To avoid problems we will use `LocalDate` class that always uses Gregorian calendar:

Our curde testing function returns without throwing any exceptions, so we may rest assured that our function works.

#### Tomohiko Sakamoto algorithm

Before we end this post let’s challenge ourselves one more time. Here is Tomohiko Sakamoto algorithm for computing day of week:

With our newly gained knowledge about computing day of week let’s find out how it works!

The main idea behind the algorithm is to compute day of week from 31 December of the previous year for January and February (just as we do in our algorithm) and to compute day of week for all other months from 31 December of the current year. This greatly simplifies dealing with leap years. To compute day of week from year end we will do as follows: say we want to know day of week for 7 April 2016. We know that 31 December 2016 is Saturday. Next we must get day of week for last day of month that precedes April, in other words we must find out day of week for 31 March (that’s Thursday). Then we just add days and take rest modulo seven and we are done: 7 April is Thursday too. This is illustrated on image below: To compute day of week for last day of prev month we will use formula:

Notice that we are subtracting two values modulo seven to move backwards. Unfortunately in Java modulo can return negative values when used with negative numbers e.g.

To solve this problem we will use simple fact from modular arithmetic:

Now we will be guaranteed to get a number that represents valid day of week.

Full algorithm looks like this:

Now we can combine our forward and backward approaches to create one simple algorithm:

Before we end let’s try to use refactoring to simplify code further. Let’s start with statement:

Since this is the only place that use `y` we can refactor this code into:

Then we can inline `numberOfDaysInYears` function:

Next since `365*y % 7 == 1*y % 7` and `(a + b) % 7 == (a % 7 + b % 7) % 7` we can simplify further:

Finally because `31 % 7 == 3`, and combining all additions into single expression we get:

which is exactly Tomohiko Sakamoto algorithm.

Wow! This post turned out to be rather lengthy, if you are still with me thank you for your effort and hard work!