Look Before You Leap Year
Michael Morehouse Originally published at yawpitchroll.com on ă»8 min read
Leap Years are Stupid
Actually, leap years are absurd, and consequently extremely stupid. From the day some longdead forbear of astronomers^{1} and astrologers^{2} peered up at both the Sun and Moon in the same sky, put two and two together, and realized that they were in the same place as the last time it was this bloody cold^{3}, weâve been stuck with them, whether we realized it or not. In a sad quest to pretend that an ellipse^{4} is, nevertheless, a circle, we doomed ourselves to forever having to maybe offset our mental clocks when looking sufficiently far forward or back in time, lest history and reality drift dangerously out of sync.
In the modern West the leap year is usually attributed to Julius Caesar, who so succesfully promoted the concept that it only took the Romans fifty years after his death^{5} to reliably incorporate it into what history now tries to forget as the Julian calendar. Unfortunately Caesar and his scholars â being pretty poor programmers â had made a wee bit of a rounding error, and so in 1582 Pope Gregory XIII was forced to âcorrectâ the situation^{6} by shifting the average year from 365.25 to 365.2425 days. And so was born the Gregorian calendar we all know and use today^{7}. This approximation was good enough for the Church, and so history has been positively littered with February 29th every so often ever since.
I feel contempt for the leap year. So why am I writing about it?
Itâs an Ideal Programming Exercise
It turns out that determining if a particular Gregorian calendar year^{8} is, or is not, a leap year is a problem with some unusual properties that make it an excellent test of a programmerâs mastery of some of the most fundamental tools they have available to them. That, in turn, means that itâs not only a very good challenge for the budding programmer, but it could â and Iâd argue should â also be used as an impressively diagnostic question to ask a candidate in a technical interview.
In every programming language that Iâve yet encountered there exists a short, simple, and performanceoptimal solution for this problem. Indeed in most cases the optimum implementation is a single line long^{9}, but most who attempt it will end up with something quite far from elegant on the first try. And, unlike most problems with such an ideal answer, if solved inelegantly itâs also almost certainly solved inefficiently.
The beauty of the exercise is that the pathway to the ideal solution can easily be discovered just by employing the sort of straightforward reasoning that is the bread and butter of professional programming. It encourages you to think through your solution by first understanding what youâre trying to solve.
Why does all this matter?
From the masochist to the sadist: "Hurt me."
From the sadist to the masochist: "No."Clive Barker, for one
Well maybe youâve just joined Exercism. Or perhaps youâre just looking for a good code kata. Or youâve been assigned to a team working with calendars. Maybe youâre simply a masochist. Or worse, perhaps your interviewer is a sadist.
One way or another, letâs assume youâve just been assigned the task of implementing a function is_leap
that takes an integer argument year and returns a Boolean result.
Luckily Thereâs an Algorithm for That
Every year that is exactly divisible by 4 is a leap year, except for years that are exactly divisible by 100, but these centurial years are leap years if they are exactly divisible by 400.
United States Naval Observatory
Unusually for a programming problem the basic algorithm will most likely be presented to you up front, and you need merely implement it. The algorithm is very old, and has been stated in more or less precise ways over the centuries, so it helps to transcribe it into pseudocode:
IF the year is a multiple of 4 THEN
IF the year is a multiple of 100 THEN
IF the year is a multiple of 400 THEN
RETURN True
RETURN False
RETURN True
RETURN False
Notice the chevronlike > shape that results from the multiple layers of nesting? It turns out thatâs fairly typical of a firstpass mental model of the algorithm, at least in a language where indentation is meaningful. Itâs not the most elegant form â weâll get to that â but it conveys some important properties about our algorithm:
Itâs simple : You have one argument, you perform (up to) three tests on it using a basic math operation, and itâs the same operation for all three tests. The most complicated thing you need to know to solve it is how your language performs the modulo operation. Once youâve got that, comparison with zero, simple conditions, and how to return a Booleanequivalent value in your language of choice youâre golden. After five minutes of wellfocussed instruction a novice to any highlevel language should be able to bash out a general solution that mimics the above pseudocode.
Itâs progressive : After each successive test you either know the answer or you know what to ask next. Most algorithms â indeed most nontrivial problems â arenât nearly so cut and dried. There is no need for complicated branching, or your languageâs version of
else_if
, you need merely proceed forward until the moment you are certain you know the answer.Itâs robust : There are no bugs, no weird or exceptional edge cases; every possible (integer) input maps directly to a single, unwavering output. Additionally there are no side effects, no state to mutateâŠ you donât even need to carry forward the results of each modulo test. Itâs as pure as a function can get, and so constrained that you can know from glancing at it if it will always return the correct answer.
Know Thine Enemy and Thine Self
Understanding the algorithm is great, but understanding the problem itâs addressing is better, and the insights gained above tell us nothing about the domain weâre working with. Weâve treated the various modulo tests as black boxes, but really theyâre specialized filters that apply to specific, progressively smaller, subsets of the overall domain of Gregorian years.
So what can we glean from looking a little more closely at those tests?
 The answer is usually no : From the very first test we know that 3 out of every 4 years wonât be a leap year. By looking at the rest we can see that an additional 3 out of every 4 centuries wonât be eitherâŠ returning False by default will correctly answer >75% of all possible questions without any additional effort.
 They rapidly cull the herd : Just 1 in every 4 years is even a potential leap year, just 1 year in every 100 is a century, and just 1 year in 400 is a century thatâs also a leap yearâŠ we learn a lot fast about our year.
 They have a natural order : Each test is a special case of the previous one, and from the above we know that each applies to a progressively smaller number of cases. Sure, if we test division by 400 first we solve the problem very quickly in an extremely small number of cases, but if it doesnât give us the answer it also doesnât give us any useful knowledge about the question being asked. Proceed in the natural order, however, and each step refines the last.
Taking the first of these to heart we can rewrite our pseudocode so that we need only ever consider the paths to a True answer:
IF the year is a multiple of 4 THEN
IF the year is NOT a multiple of 100 THEN
RETURN True
IF the year is a multiple of 400 THEN
RETURN True
RETURN False
But this is interesting. Glancing at the above we can now see that there are exactly two criteria that result in a year being a leap year, and that those criteria are exclusive. So for any given year the answer is True if either of the following is True:
 the year is a multiple of 4, but not of 100
 the year is a multiple of 4, 100, and 400
The Path of the Righteous
From either of the above the path to the ideal form can pretty neatly unroll in front of you. Especially if we introduce some abstraction and call our three tests a , b , and c.
For instance, if we progressively introduce Boolean logic operations to our pseudocode:
IF a THEN
IF NOT b OR c THEN
RETURN True
RETURN False
âŠ becomesâŠ
IF a AND (IF NOT b OR c) THEN
RETURN True
RETURN False
âŠ which, in a language that allows you to return an expressions becomes:
RETURN a AND (NOT b OR c)
Oooh, thatâs pretty concise.
Or We Could Go The Other Way
And if weâd started from the criteria we derived alone?
IF a AND NOT b THEN
RETURN True
IF a AND b AND c THEN
RETURN True
RETURN False
âŠ can be combined with another Boolean logic operator as:
IF (a AND NOT b) OR (a AND b AND c) THEN
RETURN True
RETURN False
âŠ which allows us to extract the common operation:
IF a AND ((NOT b) OR (b AND c)) THEN
RETURN True
RETURN False
âŠ but thereâs no reason to perform the same Boolean test twice, so:
IF a AND (NOT b OR c) THEN
RETURN True
RETURN False
âŠ and since weâre returning expressions brings us right back to:
RETURN a AND (NOT b OR c)
All Roads Lead Here
And here lies the ultimate, optimal form. In a language that has shortcircuiting Boolean operations this is also the most performant form, because neither side of the or
will be evaluated for the vast majority of cases. Thankfully most languages either do shortcircuit Boolean operations, or they tend to provide an alternate shortcircuiting operator like and_also
and or_else
, so if youâre not sure yours does youâll need to do a bit of research.
Speaking of research, you might be tempted to remove those parentheses, which certainly does look nicer. But therein lies the final lesson is_leap
can teach you; your ability to elide those parentheses depends entirely on the evaluation strategy and operator precedence rules for your language. If your language evaluates left to right and binds or
at the same or lower precedence as and
, then no, you cannot remove those significant parentheses. At least not without paying the price of checking division by 400 for a year that doesnât even divide by 4.
Which, like leap years, would be stupid.

Those who look up at the night sky and find it full of stuff.Â â©

Those who look up at the night sky and find it full of nonsense.Â â©

Theyâve never actually occupied the same absolute positions twice, of course, and never will, but neither angular momentum or orbital mechanics were yet available to our prototypical yutz.Â â©

Actually something closer to an ellipse being frantically sketched over and over on an imaginary two dimensional plane being pulled away from the artist in four dimensional spacetime.Â â©

Caesarâs assassination, which famously happened on March 15th, 44 BCE, rather threw off the adoption of leap years. Things got a bit wonky until 8 CE and, since no one in this period could be relied on to write anything down consistently, we know exactly when he died, just not when in our calendar.Â â©

Gregory XIII may have been liturgically infallible, but the fact that weâve since had to introduce leap seconds tends to imply he wasnât mathematically infallible as well.Â â©

Unless you use the Hindu, Islamic, or Buddhist calendars, are Thai or Chinese, subscribe to the Juche ideology of North Korea, or measure everything in Unix time.Â â©

Specifically, for the truly pedantic, the proleptic Gregorian calendar with astronomical year numbering and a year zero. Which is fine for the purposes of an exercise. To accurately reflect leap years actually observed by humans youâd need at minimum a quite convoluted lookup table before the 9th century CE, and probably a time machine.Â â©

Your mileage may vary; in Perl it may even be less, but no one will know because of the braces. If youâre writing in 8086 Assembly Language then, honestly, why are you even reading this?Â â©
Thank you. I really enjoyed reading this article and my leap of faith has been rewarded by doing so.
Thanks! Thatâs really good to hear!