It's Friday! - Zeller's Congruence Revisited

Question

A couple of date-related questions have come up recently, and on both occasions I have been taken back to my 'early' days where one of my first forays in to programming involved implementing Zeller's Congruence.

Zeller's congruence is a neat calculation because it involves a mathematical approach to date manipulation, and the math relies on both modular and integral arithmetic, combined with a smart way of visualizing time progression.

$$ \begin{align} h =&\ \left(q + \left\lfloor \frac{13(m + 1)}{5} \right\rfloor + K + \left\lfloor \frac{K}{4} \right\rfloor + 5J + \left\lfloor \frac{J}{4} \right\rfloor \right) \mod7\\ where\\ h =&\ \text{the day of the week (0 is Saturday ... 6 is Friday)}\\ q =&\ \text{the day of the month}\\ m =&\ \text{the month (3 = March, 4 = April, ..., 13 = January, 14 = February)}\\ &\ \text{If Jan or Feb, then you have to adjust the year back by 1 year}\\ &\ \text{Jan 2001 is month 13 of year 2000}\\ K =&\ \text{the century count} \implies \left\lfloor\ \frac{\mathtt{adj.year}}{100}\right\rfloor\\ J =&\ \text{the adjusted year in the century} \implies (\ \mathtt{adj.year} \mod 100)\\ \end{align} $$

The two recent questions that have inspired me to go back and re-implement Zeller's Congruence are:

• Function for checking leap years
• Is it Friday yet?

As a secondary exercise, I tested the code using the new-in-Java8 time API.

---

Zeller's Congruence

Note: The code contains comments which go some way to explaining how the congruence works

// Used for a quick validation of days in a month.
// Note filler at MONTHDAYS[0] because months are 1-based.
private static final int[] MONTHDAYS =
        { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

private static final boolean isLeap(final int year) {
    return (year % 4) == 0 && (year % 100 != 0 || year % 400 == 0);
}

/**
 * Calculate the day of the week (1=Monday, 7=Sunday) for the supplied
 * (valid) date.
 * @param year The year to calculate (year 1 or more recent)
 * @param month The month (1 through 12 for January through December) 
 * @param day The Day-in-month (1 through 28/29/30/31 depending on the month) 
 * @return The day of the week (1 represents Monday, 7 represents Sunday).
 * @throws IllegalArgumentException if the input values are not a valid date
 */
public static final int computeDayOfWeek(final int year, final int month, final int day)
        throws IllegalArgumentException {

    // easy checks for valid dates.
    if (year < 1 || month < 1 || month > 12 || day < 1 || day > MONTHDAYS[month]) {
        throw new IllegalArgumentException(String.format(
                "%04d-%02d-%02d is not a valid date", year, month, day));
    }
    // leap year validation
    if (day == 29 && month == 2 && !isLeap(year)) {
        throw new IllegalArgumentException(
                String.format(
                        "%04d-%02d-%02d is not a valid date (Feb 29 but not a leap year)",
                        year, month, day));
    }

    // Forumla is here: https://en.wikipedia.org/wiki/Zeller%27s_congruence
    // Using the wikipedia's variable names:

    // h = (q + floor((13*(m+1)/5)) + K + floor(K/4) + floor(J/4) + 5J)

    // translate variable names in to algorithm components.

    // q is the day of month.
    final int q = day;
    // m is the month, but Jan and Feb need to be month 13 and 14
    // respectively
    final int m = month + (month < 3 ? 12 : 0);
    // if the month is jan, or feb, then year is of the previous year.
    final int calcyear = year - (month < 3 ? 1 : 0);
    // K is the year-in-century
    final int K = calcyear % 100;
    // J is the century number
    final int J = calcyear / 100;

    /*
    Algorithm works by following a concept of adding days in to a
    sequence, and performing modular arithmetic. The fundamental concept 
    is that if you know one specific date's day-of-week,  then all you
    need to do is calculate how many days you are in front of, or behind
    that day.

    If you know the days, you can perform a %7 on that, and get the day
    difference.

    If you choose your algorithm to start on a specific day and call it
    0, then the difference from the %7 is simply the day. As it happens,
    to make things work well, starting with Saturday as day 0 is right.
    */

    // how many days (possibly %7) are we offset at this point in time?
    int offset = 0;

    /*

    Now, how to calculate the days between. Well, there are 36524 days in
    a century, unless the century is divisible by 4, in which case there is
    an extra day. so, the days between epoch and now is the number of
    centuries * days-in-century + number-of-4-centuries.

    But, because we only need extra days, we can do these things %7. So,
    since 36524%7 is 5, we need to add 5 days for each century since epoch.
    Additionally, we need to add another day for each of those special
    leap years that are divisible by 400
     */

    // 5 days per century plus the number of 400 years too.
    offset += J * 5 + J / 4;

    // now, inside a century, there's leap years....
    // a normal year has 365 days, which is 52 weeks and 1 day.
    // so, each year since the start, is 1 more day of offset. And, each
    // leap year adds another...
    offset += K + K / 4;

    /*
    So, that gives us the right number of offset days to get us to the
    current year.
    Now, if we start our logical year on March 1st, we don't need to
    worry about the odd day at the end of february. Also, the number of
    days in a month, starting from March, is:

    Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec,Jan,Feb
    31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 31, 28/29

    Notice how Aug and Jan are at positions 5 and 10?

    Also, a 30-day month adds 2 days of offset, and a 31-day month adds 3
    days of offset.  So, for each 30 day month we add 2 days, and for each
    31 day month we add 3.

    This formula can be hard-coded as (13 * (m + 1))/5

     */
    offset += (13 * (m + 1)) / 5;

    // Now all we need to do is add the days in our current month, to get
    // the final offset:
    offset += q;

    // Then, the actual day of week is the zero-day + offset % 7
    int h = offset % 7;

    // Now adjust the 0-6 based Saturday-Friday to a 1-7 based Monday-Sunday
    return ((h + 5) % 7) + 1;
}

---

Test Code

I used the Time API to test the code. Obviously, the time API's LocalDateTime class is able to give you the weekday for a given date. The above code is completely reinventing the wheel... I used that LocalDateTime to validate the results:

/*
 * method for testing only.
 */
private static final void check(LocalDateTime then, boolean print) {
    // do an us vs. them comparison
    int us = computeDayOfWeek(
            then.get(ChronoField.YEAR),
            then.get(ChronoField.MONTH_OF_YEAR),
            then.get(ChronoField.DAY_OF_MONTH));

    int them = then.get(ChronoField.DAY_OF_WEEK);

    if (us != them || print) {
        System.out.printf("%14s %14s is %s%n",
                then.toString(), DayOfWeek.of(them), DayOfWeek.of(us));
    }

    if (us != them) {
        throw new IllegalStateException(String.format(
                "Unable to correlate our calculation %d to the system %d",
                us, them));
    }
}

public static void main(String[] args) {

    LocalDateTime now = LocalDateTime.now().truncatedTo(ChronoUnit.DAYS);
    LocalDateTime past = LocalDateTime.of(1, 1, 1, 0, 0);

    LocalDateTime then = past;
    // test every day since 1 Jan, 0001 through to today
    while (then.isBefore(now)) {
        check(then, false);
        then = then.plusDays(1);
    }
    check(now, true);

    then = LocalDateTime.of(2, 1, 1, 0, 0);
    // recheck, and print the first year's dates.
    while (then.isAfter(past)) {
        then = then.minusDays(1);
        check(then, true);
    }

    LocalDateTime future = now.plusYears(1);
    then = now;
    // check, and print the next year's dates.
    while (then.isBefore(future)) {
        check(then, true);
        then = then.plusDays(1);
    }
}

Answer 1

final int q = day;
final int m = month + (month < 3 ? 12 : 0);
final int calcyear = year - (month < 3 ? 1 : 0);
final int K = calcyear % 100;
final int J = calcyear / 100;

int offset = 0;
offset += J * 5 + J / 4;
offset += K + K / 4;
offset += (13 * (m + 1)) / 5;

offset += q;

int h = offset % 7;

return ((h + 5) % 7) + 1;

That's the code without any comments. I'm going to try to optimize it, although you'll have to do your own performance testing.

A couple things come to mind already:

final int m = month + (month < 3 ? 12 : 0);
final int calcyear = year - (month < 3 ? 1 : 0);

Assign the month < 3 to isJanOrFeb instead.

final boolean isJanOrFeb = month < 3;
final int m = month + (isJanOrFeb ? 12 : 0);
final int calcyear = year - (isJanOrFeb ? 1 : 0);

---

Don't do unnecessary assignment...

int offset = 0;
offset += J * 5 + J / 4;

It's a waste.

int offset = J * 5 + J / 4;

---

There's only 1 usage of m...

offset += (13 * (m + 1)) / 5; 

And since it's final only one set too

final int m = month + (month < 3 ? 12 : 0);

So maybe combine the + 1?

final int m = month + (isJanOrFeb ? 13 : 1);
offset += (13 * m) / 5;

---

This bit of code can be collapsed easily...

int h = offset % 7;

return ((h + 5) % 7) + 1;

To this

int h = (offset + 5) % 7;

return h + 1;

But then again, one wonders why you don't declare h as final... or whether you need it at all.

return ((offset + 5) % 7) + 1;

All I did was remove the h line and replace h with offset.

---

Final code:

final int q = day;
final boolean isJanOrFeb = month < 3;
final int m = month + (isJanOrFeb ? 12 : 0) + 1;
final int calcyear = year - (isJanOrFeb ? 1 : 0);
final int K = calcyear % 100;
final int J = calcyear / 100;

int offset = q;
offset += (13 * m) / 5;
offset += K + (K / 4);
offset += (J * 5) + (J / 4);

return ((offset + 5) % 7) + 1;

I moved the statements around so it looks more like the original function.

Answer 2

Since the method is only concerned up to days and the day of the week, I think you can opt for the "simpler" LocalDate type for your testing.

DayOfWeek also has a static from() method that works directly on TemporalAccessor types, of which LocalDate inherits. Therefore, you can replace:

DayOfWeek.of(then.get(ChronoField.DAY_OF_WEEK))

With just:

DayOfWeek.from(then)

On the topic of testing, you probably have good reasons for just using public static void main, but for the sake of any beginners who may have stumbled upon this question while they are learning about unit testing, may I suggest something in that vein instead?

Sample implementation (I'm using TestNG and Hamcrest matchers below):

private static final LocalDate now = LocalDate.now();
private static final LocalDate past = LocalDate.of(1, 1, 1);
private static final LocalDate future = now.plusYears(1);

private static final void check(final LocalDate then, boolean print) {
    DayOfWeek actual = DayOfWeek.of(computeDayOfWeek(then.get(ChronoField.YEAR),
            then.get(ChronoField.MONTH_OF_YEAR), then.get(ChronoField.DAY_OF_MONTH)));
    DayOfWeek expected = DayOfWeek.from(then);
    if (print) {
        System.out.printf("%14s %14s is %s%n", then.toString(), expected, actual);
    }
    assertThat(then.toString() + " is on " + expected, actual, equalTo(expected));
}

@Test
public void testPast() {
    LocalDate then = past;
    // test every day since 1 Jan, 0001 through to today
    while (then.isBefore(now)) {
        check(then, false);
        then = then.plusDays(1);
    }
}

@Test
public void testToday() {
    check(now, true);
}

@Test
public void testFirstYear() {
    LocalDate then = past.plusYears(1);
    while (then.isAfter(past)) {
        then = then.minusDays(1);
        check(then, true);
    }
}

@Test
public void testFuture() {
    LocalDate then = now;
    while (then.isBefore(future)) {
        check(then, true);
        then = then.plusDays(1);
    }
}

P.S.: I usually prefer using TestNG's DataProvider annotations for parameterized testing, but I figured that telling TestNG to iterate through all the dates since 1st January 1 AD may be too much... hence the manual looping in each test method here.

P.P.S.: One very minor point, if I were you I will also consider putting the two validation if statements in their own validation method.