Spotify Solution: Best Before

Just about any product found in a grocery store has a "best before" date printed on it. Unfortunately, the format for these dates can vary quite a bit: what is it supposed to mean that the bread you bought yesterday is "best before 12/11/10"? It could mean that the bread expires on November 10, 2012 (now that's a suspiciously durable bread and probably it is not healthy for you for other reasons!), or it could mean that the bread expired on December 11, 2010 (d'oh!), or a variety of other options. To be safe, the truly paranoid (or healthily skeptic, depending on who you ask) person would assume that it means "best before November 12, 2010", since that is the earliest possible date. On the other hand, seeing "31/5/2012" even the truly paranoid person knows that this must mean May 31, 2011 since that is the only possible real date using these three numbers.

Given a possibly ambiguous date "A/B/C", where A,B,C are integers between 0 and 2999, output the earliest possible legal date between Jan 1, 2000 and Dec 31, 2999 (inclusive) using them as day, month and year (but not necessarily in that order).

Recall that a year is a leap year (has 366 days) if the year is divisible by 4, unless it is divisible also by 100 but not by 400 (so 2000 is a leap year, 2100 is not a leap year, and 2012 is a leap year).

Input
The input file consists of a single line containing three integers separated by "/". There are no extra spaces around the "/". Years may be truncated to two digits and may in that case also omit the leading 0 (if there is one), so 2000 could be given as "2000", "00" or "0" (but not as an empty string). Months and days may be zero-padded. You may assume that the year, when given with four digits, is between 2000 and 2999. At most one of the integers has four digits, and the others have one or two digits.

Output
Output a single line giving the earliest legal date possible given the above constraints. The output should be formatted as year-month-day, where year has four digits, and month and day have two digits each (zero padding), for example "2011-07-15". If there is no legal date (subject to the above constraints) then output a single line with the original string followed by the words "is illegal".

Solution

This is a pretty nice task where you need to clean the input data and have to implement an algorithm to find the minimum date - and as a date, it has some constraints (not evenly distributed days per month, leap years, and in this case not indistingushable date formats). Searching the minimum date and workout out the different formats is \(O(3!)\subseteq O(1)\), so the algorithm is pretty fast. The JavaScript implementation looks as this:

function MinDate(date) {

    // Split string into an array
    date = date.split('/').map(d => +d.trim());

    // Number of days per month
    var days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];

    var stack = [];

    // Implements our unrolled loop
    function $(a, b, c) {

        // Bring the year into the right format
        var year = date[c] > 999 ? date[c] : date[c] + 2000;

        // Calculate if the current date is within a leap year
        var leap = date[a] == 29 && date[b] == 2 && (year % 400 == 0 || (year % 100 != 0 && year % 4 == 0));

        // Use boundaries to decide stack filling
        if (date[b] <= 12 && date[a] <= days[date[b] - 1] + leap) {
            stack.push((year * 100 + date[b]) * 100 + date[a]);
        }
    }

    // Stupid formatter
    function _(n) {
        return (n |= 0) < 10 ? "0" + n : n;
    }

    // Permutate all possebiities.
    $(0, 1, 2); $(0, 2, 1); $(1, 0, 2);
    $(1, 2, 0); $(2, 0, 1); $(2, 1, 0);

    this.getDate = function() {

        if (stack.length) {
            // The minimum stack element contains what we want
            var min = Math.min.apply(null, stack);
            return _(min / 10000) + "-" + _(min / 100 % 100) + "-" + _(min % 100);
        } else {
            // We're lazy, don't loop again, just print out the illegal state
            return "illegal";
        }
    };
}

console.log((new MinDate("02/4/67")).getDate()); //2067-02-04
console.log((new MinDate("31/9/73")).getDate()); // illegal
console.log((new MinDate(" 2012 / 31 / 5 ")).getDate());
console.log((new MinDate(" 73 / 31 / 9 ")).getDate());
console.log((new MinDate(" 2 / 4 / 67 ")).getDate());
console.log((new MinDate(" 11 / 10 / 12 ")).getDate());
console.log((new MinDate(" 29 / 2 / 11 ")).getDate());