[nolan@nprescott.com] $  cat weblog archive feed

Calculating the Day of Week Using Zeller's Congruence

2020-03-25

I've been reading more about the J Programming Language and made a silly little toy. I can't for the life of me remember where I first read about Zeller's congruence, but it's a pretty good fit for a first stab at J.

It was perhaps inevitable that I'd try J at some point, following my forays into Klong previously. The only thing really holding me back, as is so often the case with new languages, is finding a suitable problem.

Zeller's congruence

The encyclopedia does a better job explaining it than I could:

These formulas are based on the observation that the day of the week progresses in a predictable manner based upon each subpart of that date. Each term within the formula is used to calculate the offset needed to obtain the correct day of the week.

h = ( q + floor 13(m+1)/5 + Y + floor Y/4 − floor Y/100 + floor Y/400 ) modulo 7

An Implementation

Be sure to see the most recent update at the bottom of the post

dayOfWeek=: monad define
    'day month year'=. y
    months=.'March';'April';'May';'June';'July';'August';'September';'October';'November';'December';'January';'February'
    mi=.(months~:<month) i.0
    ay=.year-mi{0 0 0 0 0 0 0 0 0 0 1 1
    di=.7|+/<. day , (13*(mi+4)%5) , ay , (ay%4) , (-ay%100) , (ay%400)
    >di{'Sunday';'Monday';'Tuesday';'Wednesday';'Thursday';'Friday';'Saturday'
)

It works like this:

   dayOfWeek 25;'March';2020
Wednesday

   dayOfWeek 4;'July';1776
Thursday

   dayOfWeek 16;'September';1810
Sunday

How It Works

The first bit of weirdness is the "verb" definition syntax:

dayOfWeek=: monad define
   NB. definition goes inside
)

Here, as in Klong, monad refers to a function of one argument. One oddity is my one argument is a compound structure that I'll later unpack. The definition ends with the closing parentheses. It is weird, you just get used to it I guess.

Also, =: are global definitions and =. are local, so dayOfWeek is a global here while the variables inside are local to it.

First I unpack the arguments into three separate variables, day, month and year (y is used to denote the right-hand-side of a verb invocation). This just results in dayOfWeek 4;'July';1776 binding day to 4, month to 'July', and year to 1776 within the body.

The next bit is a boxed array of strings, the months. They are in the order given by Zeller's congruence.

    months=.'March';'April';'May';'June';'July';'August';'September';'October';'November';'December';'January';'February'
┌─────┬─────┬───┬────┬────┬──────┬─────────┬───────┬────────┬────────┬───────┬────────┐
│March│April│May│June│July│August│September│October│November│December│January│February│
└─────┴─────┴───┴────┴────┴──────┴─────────┴───────┴────────┴────────┴───────┴────────┘

In order to find which month is requested I'm using the following as a lookup, assigning it to mi:

    mi=.(months~:<month) i.0

There are two things happening here, first is a boolean check (not equal ~:) to identify those months not matching. Because months is a boxed array, I have to box (<) the month value being searched, lest I compare a bare string to a boxed string!

   months~:<'June'
1 1 1 0 1 1 1 1 1 1 1 1

Because I really only want the month that does match, I want the index of the 0 in that array. That is exactly what i. 0 does.

   (months~:<'June') i.0
3

With the month in hand, it is time to calculate the year value. In most cases it is just the requested year, but in the case of January and February, it is calculated as the 13th and 14th month of the year prior:

ay=.year-mi{0 0 0 0 0 0 0 0 0 0 1 1

Here I'm "taking" ({) the index mi from a new array (the string of 1's and 0's) corresponding to the offset I have to subtract. For this case, there's no offset 10 months out of the year and for 2 months I need to subtract 1 from the year.

   3 { 10 9 8 7
7

   10 - 3 { 10 9 8 7
3

Next is the hairiest bit:

di=.7|+/<. day , (13*(mi+4)%5) , ay , (ay%4) , (-ay%100) , (ay%400)

This isn't actually too bad, most of the ugliness is inherent to the algorithm (you can't blame it all on J). % is used for division, so you can sort of squint and see the leap year math there at the end (4, 100, 400). Important to note is that , is used to build lists, like so:

   3 , 4 , 5 , 6
3 4 5 6

<. is "floor" and returns the integer part of a number (or numbers):

   <. 7.66666666666
7

   <. 3.5 , 4.5 , (9%2)
3 4 4

+/ is "sum"

   +/ 3 , 4 , 5 , 6
18

| is modulo:

   7|49
0

   7|16
2

Finally, with an index into the days of the week at hand, we just have to pick it out:

>di{'Sunday';'Monday';'Tuesday';'Wednesday';'Thursday';'Friday';'Saturday'

The only new bit here is > which "opens" the boxed value to be a plain old string again. The boxed array of the days of the week is indexed ({) with our value and we return.

   2{'Foo';'Bar';'Baz';'Qux'
┌───┐
│Baz│
└───┘

   >2{'Foo';'Bar';'Baz';'Qux'
Baz

Bugs?

Days returned prior to the mid-1700's are not correct. I think this is a historical artifact from the slow adoption of the Gregorian calendar that culminated in a few wild adjustments to the month of September 1752:

To align the calendar in use in England to that on the continent, the Gregorian calendar was adopted, and the calendar was advanced by 11 days: Wednesday 2 September 1752 was followed by Thursday 14 September 1752. The year 1752 was a leap year so that it consisted of 355 days (366 days less 11 omitted).

Or, if you prefer the Unix cal command:

$ cal september 1752
   September 1752
Su Mo Tu We Th Fr Sa
       1  2 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

Thoughts

J is a fun language, albeit a little obtuse. I haven't yet made up my mind about it for any kind of general use but I think I'll enjoy these sorts of small toys for a while yet. Getting started isn't too bad with the help of a few resources provided for free:

Of the two, I think Easy J is a better start. I've not yet finished the J Primer but would instead recommend Learning J for a full-length book introduction.

Addendum

I've been reading bits of Eugene McDonnell's At Play With J and have discovered that symbols exist in J. A slight modification to my verb might make use of these instead of boxed strings for the month lookup.

dayOfWeek=: monad define
    'day month year'=. y
    months=. s: ' March April May June July August September October November December January February'
    mi=. months i. s: <month
    ay=. year-mi{0 0 0 0 0 0 0 0 0 0 1 1
    di=. 7|+/<. day , (13*(mi+4)%5) , ay , (ay%4) , (-ay%100) , (ay%400)
    >di{'Sunday';'Monday';'Tuesday';'Wednesday';'Thursday';'Friday';'Saturday'
)

The symbol verb (s:) turns a delimited string into an array of symbols:

   s: ' foo bar baz'
`foo `bar `baz

Symbols may be indexed directly with the index-of verb (i.), which isn't so different from the first version, we can just skip a few steps this way.

   (s: ' foo bar baz') i. s:<'bar'
1

One Final Note

I swear this is the last update. J apparently has support for rationals so instead of repeatedly referencing the same year value in the leap year calculation you could use a real array multiplication and reference it once:

   (year%1) , (year%4) , (-year%100) , (year%400)

is the same as:

   year % 1 4 _100 400

is the same as multiplying by the reciprocal:

   1 1r4 _1r100 1r400 * year

If you line things up like that, you can take advantage of the right to left evaluation process and omit another temporary variable entirely — I think I'm getting the hang of this code golf thing! In the same way, some parentheses can be cleaned up in calculating (13 * (mi + 4) % 5) by condensing to a single fractional multiplier (13r5 * mi + 4)

It also dawned on me that the year offset mask was a silly idea when the test is really just "is greater than 9?" since booleans are 0 and 1 in J.

dayOfWeek=: monad define
   'day month year'=. y
   months=. s: ' March April May June July August September October November December January February'
   mi=. months i. s: <month
   di=. 7|+/<. day , (13r5 * mi+4) , 1 1r4 _1r100 1r400 * year-mi>9
   >di{'Sunday';'Monday';'Tuesday';'Wednesday';'Thursday';'Friday';'Saturday'
)