Match Editorial

Division 1 saw a feeding frenzy as most contestants completed a paint-by-numbers Level One problem and a mildly tricky Level Two with ample time to spare. In the early running, tomek and SnapDragon led the pack by slim margins. The tempo grew less hectic as coders plodded through a Level Three specification torn from the pages of a bureaucratic standard for week numbering. jpo and Smiley=) found, at length, that a Java utility class could be tweaked to satisfy the shifted calendar, but bladerunner pieced together an iterative solution that propelled him ahead of the usual suspects and onto the winner's podium. Hot on bladerunner's heels was tomek, whose rating converged closer yet with that of SnapDragon, the latter's elegant Level Three effort having succumbed to an initialization bug.

The stalwart coders of Division 2 did well on a Level Three problem cloned from the upper division's Level Two. Few stumbled on the Level One, and many contended happily with their Level Two calendar problem, a less than daunting affair leavened by the spirit of Elvis. Although bokbok blazed with a fury through the first two problems, it was carambola5 who eked out a win over a clutch of other seasoned competitors.

The Problems

Value	250
Submission Rate	199 / 207 (96.14%)
Success Rate	165 / 199 (82.91%)
High Score	bokbok for 248.34 points (2 mins 19 secs)
Average Score	218.72 (for 165 correct submissions)

Ready for some nifty arithmetic? Begin by noting that the inchworm's point of departure coincides with the first leaf on the branch. Subsequently, a meal ensues at every distance that is divisible by the inchworm's travel increment and by the leaves' growth interval. In other words, we are looking for common multiples of rest and leaf. In last week's match summary, schveiguy taught us that the lowest common multiple can be calculated by

    def lcm(rest, leaf):
        return rest / gcd(rest, leaf) * leaf

where the greatest common denominator gcd is given, for example, by the following recursive function.

    def gcd(rest, leaf):
        if (leaf == 0):
            return rest
        return gcd(leaf, rest%leaf)

Then we determine how many times the lowest common multiple fits into the branch length, adding 1 to account for the initial leaf, so that the total number of leaves eaten is calculated as follows.

    def eaten(branch, rest, leaf):
        return branch / lcm(rest, leaf) + 1

Those who are not so keen on factoring can forge ahead with a brute-force approach. Since the longest branch is only a million inches long, it won't take long to carry out a simulation. The following pseudocode shows how we can advance the inchworm's position by rest until she falls off the branch, all the while keeping track of how many distances are divisible by leaf.

    def eaten_sim(branch, rest, leaf):
        meals = 0
        pos = 0
        while (pos <= branch):
            if (pos%leaf == 0):
                meals = meals+1
            pos = pos+rest
        return meals

Value	500
Submission Rate	134 / 207 (64.73%)
Success Rate	85 / 134 (63.43%)
High Score	bokbok for 456.07 points (8 mins 59 secs)
Average Score	313.26 (for 85 correct submissions)

If two years start on the same day of the week, do they share a calendar? It depends. If one is a leap year and the other is not, then the weekdays fall out of sync at the end of February. But if both years start on the same day of the week, and neither is a leap year or both are leap years, then the weekdays march in lockstep from January 1 through December 31.

The funny thing is that if we want to find the nearest future year that shares a calendar with a given year, it isn't necessary to know what weekday the given year starts on. Let us say, for the sake of argument, that January 1 of this year is a Sunday. Now, what day of the week is January 1 of the next year? If this is not a leap year, then 365 days later, the weekday will have shifted by 365%7 = 1 day to Monday. But if it is a leap year, the weekday shifts by 366%7 = 2 days to Tuesday. We can apply the same reasoning year after year until we find one that begins on a Sunday and has the same leap-year status as the original year.

We reach the same result regardless of whether we begin by assuming that the given year starts on a Sunday or a Wednesday or anything else! Even the choice of January 1 is arbitrary. We might just as well proceed on the basis of, say, September 8.

We also use modulo arithmetic to identify leap years. In the following pseudocode, weekday is initially 0 to indicate that some fixed day in the initial year is a Monday.

    def elvis(year):
        weekday = 0
        leap = 0
        if ((year%400 == 0) or ((year%100 != 0) and (year%4 == 0))):
            leap = 1
        yy = year
        ww = weekday
        while (1):
            yy = yy+1
            ww = (ww+1)%7
            ll = 0
            if ((yy%400 == 0) or ((yy%100 != 0) and (yy%4 == 0))):
                ll = 1
            if ll:
                ww = (ww+1)%7
            if ((ll == leap) and (ww == weekday)):
                break
        return yy

By sheer coincidence, this pseudocode will run on a Python interpreter.

Value	1000
Submission Rate	56 / 207 (27.05%)
Success Rate	40 / 56 (71.43%)
High Score	jnwood for 882.85 points (10 mins 38 secs)
Average Score	582.77 (for 40 correct submissions)

Value	500
Submission Rate	127 / 150 (84.67%)
Success Rate	110 / 127 (86.61%)
High Score	bigg_nate for 471.95 points (7 mins 0 secs)
Average Score	337.50 (for 110 correct submissions)

An effective but brutal solution is to swap balls blindly, exploring the state space via memoized breadth-first search to discover the shortest path to a desired configuration.

A more genteel approach proceeds from the observation that productive swaps can be made independently of one another. Any swap that exchanges two improperly placed balls is just as helpful in restoring order as any other swap of two misplaced balls.

Suppose we want to form the first type of rack, where position 0 is occupied by a stripe. If the eight-ball is not at position 4, we begin by swapping it with whatever ball is usurping its rightful place. This pretender ball may again end up in an improper location, but the effort of swapping it later is equivalent to the effort it would have taken to swap it before moving the eight-ball.

Once the eight-ball is in place, we need merely swap misplaced stripes with misplaced solids. Since there are 14 stripes and solids altogether, at most 14/2 = 7 swaps are made at this stage. If it requires k swaps such that k >= 4, we see that we were working toward the wrong configuration, since the other kind of rack, where stripes are exactly exchanged for solids, would have required 7-k < 4 swaps.

So we decide to make k or 7-k swaps, whichever is less, and add 1 if the eight-ball was out of place. In sum, no more than 4 swaps are required to rack any triangle.

Value	250
Submission Rate	149 / 150 (99.33%)
Success Rate	148 / 149 (99.33%)
High Score	tomek for 246.47 points (3 mins 24 secs)
Average Score	211.76 (for 148 correct submissions)

The most clearheaded way to interpret the opponent's history is that you win each time he makes the move you expect him to make. There's no need to figure out what move you should make in response. (For the first two moves, it's enough to know that you're expecting the opponent to play Scissors.)

If you insist on calculating the ideal move at every turn, find the character immediately following that of the opponent's move in the string "PSR", where R wraps around to P.

That's all, folks. No wonder the submission success rate was better than 99%.

Value	1000
Submission Rate	40 / 150 (26.67%)
Success Rate	20 / 40 (50.00%)
High Score	bladerunner for 742.24 points (18 mins 6 secs)
Average Score	568.67 (for 20 correct submissions)

The concept of the calendar week forms a small part of ISO 8601, a standard for representing terrestrial dates and times. Sharp-eyed readers will have noted that ISO is not a strict abbreviation of "International Organization for Standardization", in the same way that UTC matches neither the English "Universal Coordinated Time" nor the French "Temps Universel Coordonne". Such is the ISO.

When calculating ISO week numbers by hand, the chief difficulty is that although most years have 52 calendar weeks, some have 53. It helps to observe that such a "long year" can only be one that begins or ends on a Thursday, since a leap year has 366=52*7+2 days and a non-leap year has 365=52*7+1. Consider that in a non-leap year, if January 1 is a Thursday, then exactly 52 weeks later comes another Thursday, hence the start of a 53rd week.

Under the Gregorian calendar, ISO week numbers can be calculated by closed-form functions such as the following.

    def week(y, m, d):
        a = (14-m)/12
        y = y+4800-a
        m = m+12*a-3
        j = d + (153*m+2)/5 + 365*y + y/4 - y/100 + y/400 - 32045
        d4 = ((((j+31741-(j % 7)) % 146097) % 36524) % 1461)
        L = d4/1460
        d1 = ((d4 - L) % 365) + L
        return d1/7 + 1

If, as in our problem statement, the calendar is shifted by three days, it's not obvious how such a magic formula can be adapted to meet the new circumstances, nor how a ready-made class such as java.util.GregorianCalendar can be employed. The motive for the three-day shift was precisely to throw a wrench into the works.

As it was, two coders managed to harness GregorianCalendar by a simple expedient. They set the minimal number of days in a week to four, as required by ISO, but set the first day of the week to Friday, three days ahead of the standard Monday. It is also possible to use GregorianCalendar less directly, relying on it to calculate a weekday-independent value, such as the day of the year, from which the ISO week number may be calculated with relative ease.

The elementary solution is to start from a known calendar week and proceed by first principles to deduce the ISO numbers of surrounding weeks. A slightly more sophisticated approach is to manually calculate an ISO week number in the sufficiently far past, so that one need only iterate forward to the target. Let us, however, consider iteration in both directions.

We learn from a test case that December 26, 1642 is the first day of ISO week 52 under the new regime. If the desired date is no earlier than this, we can creep forward a day at a time, updating the year, month, day, week number, and weekday as though they were wheels turning over in an odometer. Weekdays are indexed from 1 to 7 in the pseudocode below. We use a two-dimensional array to look up the days in a month according to leap-year status. Notice, furthermore, that the week number rolls over to 1 only on a Monday that falls between December 29 and January 4, inclusive.

    months = [[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31],
              [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]]

    def week_forward(year, month, day):
        y = 1642; m = 12; d = 26; wd = 1; wn = 52; leap = 0
        while (1):
            if ((y == year) and (m == month) and (d == day)):
                return wn
            d = d+1 if (d > months[leap][m-1]):
                d = 1
                m = m+1
                if (m > 12):
                    m = 1
                    y = y+1
                    leap = 0
                    if ((y%400 == 0) or ((y%100 != 0) and (y%4 == 0))):
                        leap = 1
            wd = wd+1
            if (wd > 7):
                wd = 1
                wn = wn+1
                if (((m == 12) and (d >= 29)) or ((m == 1) and (d <= 4))):
                    wn = 1

When creeping backward to a point earlier than the reference date, the year-month-day odometer rolls backward. The most delicate question is again that of updating the week number. It follows from the earlier inference about long years that an ISO week 53 can end only on January 3, or, in leap years, on January 2.

    def week_backward(year, month, day):
        y = 1642; m = 12; d = 26; wd = 1; wn = 52; leap = 0
        while (1):
            if ((y == year) and (m == month) and (d == day)):
                return wn
            d = d-1
            if (d < 1):
                m = m-1
                if (m < 1):
                    m = 12
                    y = y-1
                    leap = 0
                    if ((y%400 == 0) or ((y%100 != 0) and (y%4 == 0))):
                        leap = 1
                d = months[leap][m-1]
            wd = wd-1
            if (wd < 1):
                wd = 7
                wn = wn-1
                if (wn < 1):
                    wn = 52
                    if ((d == 3) or ((d == 2) and ((y%4 == 1) and ((y%400 == 1) or (y%100 != 1))))):
                        wn = 53

Even those who don't relish the intricacies of the ISO specification might appreciate the underlying simplicity of our superficially quirky calendar.