Match Editorial

Greased lightning! NGBronson took charge of Division One last night and put on a speed-coding clinic for the kiddies, shading ZorbaTHut by a handful of points. (Please note that our Zorba is not related to Zorba the Greek, nor does he have the girth of Jabba the Hutt.) Another fiendishly clever gent, snewman, took the bronze. There was gnashing of teeth and rending of garments in Division Two, where coders faced a devious Level One problem. Osric flew high in his first TopCoder foray, besting another sharp newbie, jerky, by nearly 100 points. The ominously named but probably quite jolly Darkmaster placed third.

The Problems

Value	250
Submission Rate	228 / 272 (83.82%)
Success Rate	95 / 228 (41.67%)
High Score	hw_Tim for 236.34 points (6 mins 54 secs)
Average Score	176.63 (for 95 correct submissions)

We are asked to find the two height measurements closest to a target height from among a list of candidates. The simpler but perhaps less elegant way to accomplish this is to identify the closest height, discard it, and then search for the closest height in the reduced list.

In the pseudocode below, we begin by sorting the candidates in non-descending order. Now it's easy to break ties in favor of larger values: we process the list from smallest to greatest, always updating our best choice if the current candidate is at least as close to the target height as any earlier candidate. Also note that we measure how close some number a is to a number b by computing the absolute value of their difference, abs(a-b). Finally, we mustn't forget to sort the return values.

def skip(candidates, height):
  candidates.sort()
  ret = []
  best = 0
  for i in range(len(candidates)):
    if (abs(candidates[i]-height) <= abs(candidates[best]-height)):
      best = i
  ret.append(candidates[best])
  del(candidates[best])
  best = 0
  for i in range(len(candidates)):
    if (abs(candidates[i]-height) <= abs(candidates[best]-height)):
      best = i
  ret.append(candidates[best])
  ret.sort()
  return ret

The more concise approach is to run through the candidates only once, maintaining a list of the top two candidates at any given moment. If some candidate is closer to the target height than the currently top-ranked candidate, we insert this candidate at the head of the rankings and chop off the last element in the rankings. Otherwise, we compare the same candidate to the currently second-ranked height. If the candidate is better, we perform a similar insert-and-chop routine.

def skip2(candidates, height):
  k = 2
  candidates.sort()
  ret = [-1]*k
  for i in range(len(candidates)):
    for j in range(k):
      if (ret[j] == -1 or abs(candidates[i]-height) <= abs(ret[j]-height)):
        ret.insert(j, candidates[i])
        del(ret[k])
        break
  ret.sort()
  return ret

This code is readily adapted to the general problem of returning the top k candidates for any given k.

Value	500
Submission Rate	115 / 272 (42.28%)
Success Rate	49 / 115 (42.61%)
High Score	jerky for 473.25 points (6 mins 49 secs)
Average Score	302.72 (for 49 correct submissions)

Value	250
Submission Rate	148 / 175 (84.57%)
Success Rate	107 / 148 (72.30%)
High Score	SnapDragon for 244.52 points (4 mins 16 secs)
Average Score	192.28 (for 107 correct submissions)

We are given two 12-hour analog clocks, one of which is accurate whereas the other gains or loses some number of seconds per hour, and asked to find the number of hours that will elapse before the clocks agree. The immediate difficulty of carrying out calculations with analog clocks is that they're much too fussy, what with their three different hands. Why use three when one will do? After all, the minute hand is merely marking off the seconds in multiples of 60, while the hour hand deals with blocks of 3600.

We can streamline matters by keeping track of the time solely in terms of seconds. Imagine that we have a minimalist clock equipped with a single hand and a dial divided into 12*60*60=43200 seconds. If a conventional clock shows m minutes and s seconds past h o'clock, we can translate the time into pure seconds by computing 3600*(h-1)+60*m+s.

Having done this to the true clock as well as the skewed clock, we can take the two minimalist clocks and superimpose one on the other, as it were, so that we are looking at a single minimalist clock with two second hands traveling at different rates. Which one is faster? Well, if the skewed clock is gaining a positive number of seconds per hour, then the hand corresponding to the skewed time is the faster of the two. But if the skewed clock gains a negative number of seconds per hour, so that it is actually losing time, then the faster hand corresponds to the true time.

The question now is this: how long will it take the fast hand to catch up with the slow one? Consider the lead, in seconds, that the slow one currently enjoys over the fast one. After an hour, the fast hand will have traveled the same distance as the slow hand plus a fixed number of seconds, so that the lead is reduced by that number. As another hour passes, the lead is reduced by the same fixed number. Thus, the number of hours that must elapse before the lead becomes zero is the number of times that the hourly gain fits into the lead! Another way to put it is that we divide the size of the lead by the size of the hourly gain.

We must pay attention when calculating the size of the lead, since the fast hand may be nominally before or behind the slow hand according to the analog clock. If the span of seconds from the fast hand to the slow hand works out to a negative number, we normalize it by adding a full clock's worth of seconds, or 12*60*60.

def clock(true_time, skew_time, gain):
  true_secs = 3600*(float(true_time[0:2])-1) + 60*float(true_time[3:5]) + float(true_time[6:8])
  skew_secs = 3600*(float(skew_time[0:2])-1) + 60*float(skew_time[3:5]) + float(skew_time[6:8])
  lead = true_secs - skew_secs
  if (gain < 0):
    lead = skew_secs - true_secs
  if (lead < 0):
    lead += 12*60*60
  return abs(lead/gain)

We could have performed an algebraic reduction to arrive at the conclusion that we need abs(lead/gain), but it's wise to expend no more brain cells than necessary.

Value	1000
Submission Rate	24 / 272 (8.82%)
Success Rate	18 / 24 (75.00%)
High Score	tox for 779.00 points (16 mins 7 secs)
Average Score	581.88 (for 18 correct submissions)

A four-by-four-by-four lattice is filled with 64 black and white cubes, and we are asked to count the number of orthogonal and diagonal lines (of length four) that are formed by cubes of a given color. Masochists will want to embark on a case-by-case analysis, analyzing the possible pairs of endpoints and classifying these by type: corner to corner, side to side, and edge to edge. The pain-free approach is to let your for-loops do the walking.

First, we shall use nested loops to enumerate the various directions in which a line may stretch. Since each consecutive pair of cubes within a line must be neighbors, let's look at all possible neighbors of a given cube. From a cube with coordinates (i, j, k) in the lattice, we may reach a neighboring cube by stepping no more than one unit away in each of the three dimensions. In each dimension, then, we make a step of -1, 0, or 1. If we let the dimensional increments di, dj, and dk iterate over these three values in a triply nested loop, not forgetting to exclude the case where all three increments are zero, we end up generating all 3*3*3-1=26 non-zero direction vectors.

We can use a further triply nested loop to generate all 4*4*4=64 locations within the lattice, striking out in each of the 26 possible directions to see whether we can form a line of four cubes. If, in the course of stepping in some direction, we run out of cubes of the desired color or leave the confines of the lattice altogether, we just cease stepping in that direction and move to the next location.

def cubism(lattice, color):
ct = 0
  for di in range(-1, 2):
    for dj in range(-1, 2):
      for dk in range(-1, 2):
        if (di == 0 and dj == 0 and dk == 0):
          continue
        for i in range(4):
          for j in range(4):
            for k in range(4):
              ii = i
              jj = j
              kk = k
              for n in range(4):
                if (ii < 0 or ii == 4 or jj < 0 or jj == 4 or kk < 0 or kk == 4):
                  break
                if (lattice[ii][4*jj+kk] != color[0].upper()):
                  break
                if (n == 3):
                  ct += 1
                ii += di
                jj += dj
                kk += dk
  return ct/2

It is important to note that since we are generating all possible locations and all possible directions, each line will be counted in two directions. We discover not only the line from A to B, but from B to A. The remedy is to divide the total count by two.

Value	500
Submission Rate	78 / 175 (44.57%)
Success Rate	58 / 78 (74.36%)
High Score	Larry for 426.85 points (12 mins 11 secs)
Average Score	295.09 (for 58 correct submissions)

In the game of Fifteen, two players take turns covering one of the nine numerals from 1 through 9. The dealer always moves first. His opponent, the patron, wins only if he can cover three numerals that sum to 15 before the dealer does the same. Given the move history of a game in progress, the dealer having moved most recently, we are asked to decide the optimal outcome for the patron.

This little game is no more complicated than tic-tac-toe. (In some parts of the British Commonwealth, read "noughts and crosses".) Indeed, Fifteen is just tic-tac-toe in disguise. To see why this is true, construct a three-by-three magic square in which every row, column, and diagonal sums to 15. One such magic square is the following.

        2 7 6
        9 5 1
        4 3 8

Playing tic-tac-toe on this grid, with the proviso that stalemates are decided in favor of the player who moves first, is equivalent to Fifteen. Since tic-tac-toe is such a simple game, and since we are only dealing with move histories of length 1, 3, 5, and 7, it is tempting to solve the problem with case-by-case analysis. Anyone who has played a dozen rounds of tic-tac-toe can tell that the dealer is able to win from any opening move, so the result for a move history of length 1 is always "LOSE". It is also evident that when the move history has length 7, the patron is making his last move, so he can win only by immediately making 15. The remaining cases are not multitudinous, but enumerating them does allow considerable latitude for error in the matter of array indexing.

The safer course is to write a recursive solution: the state space is so small that we can carry out a depth-first search without fear of timing out. We shall work from the perspective of the player who has moved most recently. We begin by examining all combinations of three numerals drawn from that player's contribution to the move history. There are few such combinations, and at any rate they can be generated with a triply nested loop. Observe that only the moves at positions 0, 2, 4, and 6 of the move history can contribute to the dealer's sum, while positions 1, 3, 5, and 7 belong to the patron.

If there is at least one winning sum, the player in question has won. Otherwise, we iterate over each numeral still available for play, recursively computing the outcome of using it as the opposing player's next move. If the opposing player wins with at least one of these moves, we must lose the game. But if the opposing player loses in every case, then we will win, and the most recent move is to be considered a winning move.

def wins(moves, pi):
  poss = [[0, 2, 4, 6], [1, 3, 5, 7]]
  if (pi == 0 and len(moves) == 9):
    return 1
  for i in poss[pi]:
    for j in poss[pi]:
      for k in poss[pi]:
        if (i == j or j == k or k == i):
          continue
        if (i >= len(moves) or j >= len(moves) or k >= len(moves)):
          continue
        if (moves[i]+moves[j]+moves[k] == 15):
          return 1
  for m in range(1, 10):
    if (m not in moves and wins(moves+[m], not pi)):
      return 0
  return 1

def fifteen(moves):
  for m in range(1, 10):
    if (m not in moves and wins(moves+[m], 1)):
      return 'WIN '+str(m)
  return 'LOSE'

The one special case is when the move history has length 9, which implies that the dealer has won.

Value	1000
Submission Rate	17 / 175 (9.71%)
Success Rate	15 / 17 (88.24%)
High Score	NGBronson for 780.43 points (16 mins 2 secs)
Average Score	581.88 (for 15 correct submissions)

Ah, those slippery amoebae. We are given an array of Strings describing a rectangular petri dish in which Culture X is cultivated. Every character is either 'X', indicating a portion of an amoeba, or '.' to signify emptiness. Amoebae are what in graph theory we would call components, and what in this case look like clumps of edgewise connected 'X' characters. Given a second dish of the same dimensions but not necessarily the same content, and knowing that amoebae are identical under rotation, reflection, and translation, our job is to calculate the size of the symmetric difference between the two collections of amoebae.

This is a long task, but not an unpleasant one if we go about it methodically. It is best to begin with a floodfill that accomplishes two things. On the one hand, it identifies the groups of squares that constitute individual amoebae, marking each with a unique ID number. On the other, it records the locations of the upper-leftmost and bottom-rightmost squares of each amoeba so that we can enclose it in a bounding box.

Let's look at some actual Java code that does this. (I tend to think in C++, so the code is written in a style that should make for easy translation.) We declare a pair of two-dimensional character arrays to store the contents of each petri dish. We also have a pair of two-dimensional integer arrays to store amoeba IDs, and another pair for the corresponding bounding boxes. Finally, we declare variables to conveniently store the dimensions of the petri dishes, and a two-element linear array to store the number of amoebae in each dish.

  char[][][] dishes = new char[2][50][50];
  int marked[][][] = new int[2][50][50];
  int boxes[][][] = new int[2][2500][4];
  int xlen, ylen, anum[] = new int[2];

Before invoking the floodfill, we convert the input String arrays to character arrays, and initialize the ID of every square to a sentinel value. Then we iterate over all squares in each dish. If a given square is 'X', we preemptively set the bounding box of the next amoeba under construction to exactly this square, and then call the floodfill function, passing it the index of the petri dish and the coordinates of the current square. This functions bails out immediately if the coordinates are invalid or if the square has already been assigned an amoeba ID number. Otherwise, the square is assigned the ID of the newest amoeba, and we update the bounding-box coordinates as necessary. Finally, we step over to each of the four neighboring grid locations and call the function recursively.

  void markit(int n, int m, int r, int c) {
    if (r < 0 || r >= xlen || c < 0 || c >= ylen)
      return;
    if (marked[n][r][c] >= 0 || dishes[n][r][c] != 'X')
      return;
    marked[n][r][c] = m;
    boxes[n][m][0] = r < boxes[n][m][0] ? r : boxes[n][m][0];
    boxes[n][m][1] = c > boxes[n][m][1] ? c : boxes[n][m][1];
    boxes[n][m][2] = r > boxes[n][m][2] ? r : boxes[n][m][2];
    boxes[n][m][3] = c > boxes[n][m][3] ? c : boxes[n][m][3];
    markit(n, m, r-1, c);
    markit(n, m, r+1, c);
    markit(n, m, r, c-1);
    markit(n, m, r, c+1);
  }

  public int cultureX(String[] known, String[] candidate) {
    int i, j, n, m, t, t0, t1, r0, c0, r1, c1, rr, cc, diff, c;
    char sigs[][] = new char[8][3000];
    String sig, nsig;
    String[][] canons;
    xlen = known.length;
    ylen = known[0].length();
    anum[0] = anum[1] = 0;
    for (i = 0; i < xlen; i++)
      for (j = 0; j < ylen; j++) {
        marked[0][i][j] = marked[1][i][j] = -1;
        dishes[0][i][j] = known[i].charAt(j);
        dishes[1][i][j] = candidate[i].charAt(j);
      }
    for (n = 0; n < 2; n++)
      for (i = 0; i < xlen; i++)
        for (j = 0; j < ylen; j++)
          if (marked[n][i][j] < 0 && dishes[n][i][j] == 'X') {
            boxes[n][anum[n]][0] = boxes[n][anum[n]][2] = i;
            boxes[n][anum[n]][1] = boxes[n][anum[n]][3] = j;
            markit(n, anum[n], i, j);
            anum[n]++;
          }

So the floodfill is done, and we've got ID numbers and bounding boxes for every amoeba. At this point, we could perform a pairwise comparison of amoebae from each dish under every geometric operation. This would take time in the order of anum[0]*anum[1] (liberally assuming constant time to scan amoebae), which is eminently feasible, considering that a 50-by-50 dish contains about 1000 small amoebae or 100 largish ones. Nonetheless, we prefer to construct a concise linear-time solution (again assuming constant cost per amoeba) that would run in reasonable time on much larger data sets.

The idea is to map all geometric variants of a given amoeba shape to a single string representation. We can then sort these canonical strings, and merge the two lists derived from the two dishes in order to find their intersection and hence the symmetric difference. To make the canonical string for a given amoeba, we shall scan its bounding box, appending '.' to the string each time we come across a square that does not have the appropriate ID, and 'X' for each constituent square. We also append an 'n' at the end of each line, so that the canonical string encodes the dimensions of the bounding box.

We actually scan the bounding box in eight different ways. If the bounding box encloses rr rows and cc columns, we shall scan four rr-by-cc boxes and four virtual cc-by-rr boxes. This distinction is necessary because half the rotations, namely those of 90 and 270 degrees, have the effect of reversing the dimensions of the amoeba. For each rotation, we scan the amoeba as well as its mirror image. We do the same for rotations of 0 and 180 degrees, which do not alter the amoeba dimensions. Note that the amoebae need only be reflected in one axis, since the transformations that can be achieved with rotation and horizontal reflection are exactly those that can be achieved with rotation and vertical reflection. Once we have made all eight renderings, we choose the lexicographically least as the canonical string. In this way, all variations of an amoeba shape are reduced to the same thing.

    canons = new String[2][anum[0] > anum[1] ? anum[0] : anum[1]];
    for (n = 0; n < 2; n++)
      for (m = 0; m < anum[n]; m++) {
        r0 = boxes[n][m][0];
        c0 = boxes[n][m][1];
        r1 = boxes[n][m][2];
        c1 = boxes[n][m][3];
        rr = r1-r0+1;
        cc = c1-c0+1;
        t = 0;
        for (i = 0; i < rr; i++) {
          for (j = 0; j < cc; j++) {
            sigs[0][t] = marked[n][r0+i][c0+j] == m ? 'X' : '.';
            sigs[1][t] = marked[n][r1-i][c0+j] == m ? 'X' : '.';
            sigs[2][t] = marked[n][r1-i][c1-j] == m ? 'X' : '.';
            sigs[3][t] = marked[n][r0+i][c1-j] == m ? 'X' : '.';
            t++;
          }
          sigs[0][t] = sigs[1][t] = sigs[2][t] = sigs[3][t] = 'n';
          t++;
        }
        t0 = t;
        t = 0;
        for (i = 0; i < cc; i++) {
          for (j = 0; j < rr; j++) {
            sigs[4][t] = marked[n][r1-j][c0+i] == m ? 'X' : '.';
            sigs[5][t] = marked[n][r1-j][c1-i] == m ? 'X' : '.';
            sigs[6][t] = marked[n][r0+j][c1-i] == m ? 'X' : '.';
            sigs[7][t] = marked[n][r0+j][c0+i] == m ? 'X' : '.';
            t++;
          }
          sigs[4][t] = sigs[5][t] = sigs[6][t] = sigs[7][t] = 'n';
          t++;
        }
        t1 = t;
        sig = new String(sigs[0], 0, t0);
        for (i = 1; i < 8; i++)
          if ((nsig = new String(sigs[i], 0, i < 4 ? t0 : t1)).compareTo(sig) < 0)
            sig = nsig;
        canons[n][m] = sig;
      }

The final step is to sort the two lists of canonical strings and merge them. We step through the lists using a pair of indices. If the current amoebae in each list are identical, we increment both indices. If they're different, we increment the one pointing to the lesser amoeba, and also increment the magnitude of the symmetric difference.

    for (n = 0; n < 2; n++)
      Arrays.sort(canons[n], 0, anum[n]);
    diff = 0;
    i = j = 0;
    while (i < anum[0] && j < anum[1]) {
      if ((c = canons[0][i].compareTo(canons[1][j])) == 0) {
        i++;
        j++;
      }
      else {
        diff++;
        if (c < 0)
          i++;
        else
          j++;
      }
    }
    diff += (anum[0]-i)+(anum[1]-j);
    return diff;
  }

Once we have exhausted at least one of the lists, the magnitude of the symmetric difference is augmented by the number of amoebae left in the other.