Today was the onsite final of the Google Hash Code contest organized by Google Paris. The task was to route loons to optimize Internet delivery on target cells by adjusting the loons' altitude and taking advantage from winds: see the problem statement in English and French and the input file, which I will not summarize further here.

With Théotime Grohens, Marc Jeanmougin, and Auguste Olivry, I was part of the "ENS Ulm 1" team who got the first place. This post presents our strategy to solve the problem. It is comparatively simpler than the 2014 contest strategies used during the extended round. We also provide cleaned-up code for our approach; it is about 200 lines long, which is twice more than what I published for the selection round; however, unlike the selection round, this code would have sufficed to reach the first place of the contest (like we did), beating the second best score (698678 by the hackEns team).

Strategy

The basic idea of the strategy is to compute the route of the loons one after the other, considering the route of the other loons as fixed, and starting with the default routes of not moving the loons at all.

To route each loon, we use a dynamic programming approach, which computes the optimal route for this loon given the other routes. We maintain (in covered in the code below) which target cells are already covered at which time by the other loons (whose routes are fixed), to focus at each point in time on the target cells which are not covered. We optimize the total number of covered cells (summed over all time units) for the loon that we are routing: we call this the score. We use the following recursive definition to compute the optimal route:

• once the time is over, the score for a loon is 0 no matter its position
• at a time $0 \leq t < T$, the possible options for a loon at row $r$, column $c$, altitude $a$ are to adjust altitude by -1, 0, or 1 (within acceptable bounds), and the score is the sum of the following quantities:
  • the number of cells that we cover at time $t+1$ in the cell where the wind has taken us after our move, counting only those that are not otherwise covered
  • the score at time $t+1$ for the position where the wind has taken us after our move (or 0 if the loon was lost), which we compute recursively

To make this more palatable, we have precomputed overall, for each cell, the cell where the wind leads us (in dest). We also precompute which target cells are covered by a loon in each cell (in cov; and then in left at each iteration for speed). To implement the recursive definition and compute the optimal path (in function route), we then just need to compute a big table for our loon with each possible row, cell, altitude and time unit, filling it from the end of time to the beginning of time. We store in each cell of the table the optimal score (in best), computed according to the above, and the altitude adjustment (in dir) that achieves the best score.

Will this have a reasonable running time? The bounds of the input were the following: 300 rows, 75 columns, 9 altitudes (counting the ground), and 400 time units. We need two tables, each containing one int for each possibility (so 8 bytes total). The total is 648 MB, which just fits. On my workstation (with Intel Core i5-4570 @ 3.20GHz), this computation takes about one second per loon.

Doing this for all loons in sequence gives a score of 680953 with my implementation, which would have sufficed to reach the 7th place. To improve the solution further, we follow a very simple scheme. As we have computed the optimal route for each loon in isolation, once all routes have been computed, we just recompute the routes for each loon in sequence, given the previous routes. This cannot make the solution worse (the loon can always follow its previous route, which the dynamic programming approach cannot miss), and may improve it, if the loon can follow a better route given the new routes of the other loons. As just one additional tweak, to make this optimization more efficient, when two altitude adjustments are tied in the dynamic algorithm, we choose one of them at random rather than deterministically: this means that the dynamic algorithm still returns the optimal route for its loon, but it adds more opportunities to change the route and makes the iterative optimization more effective.

Code

The following C++ code is under 200 lines in total, and produces solutions with increasingly better score, in a file called "output". On my workstation, it takes a bit under 20 minutes to produce a solution with a score that would have sufficed to reach the first place in the contest.

#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

#define MAXR 77
#define MAXC 302
#define MAXL 2252
#define MAXA 11
#define MAXT 402
#define MAXB 54

int R, C, A, L, V, B, T, rs, cs;

struct Pt {
  int r, c;
  Pt(int r=0, int c=0) : r(r), c(c) {}
};

// global variables: auto-initalized, can be larger than what fits in stack
vector<int> cov[MAXR][MAXC]; // which targets are covered by a loon at (r, c)
Pt dest[MAXA][MAXR][MAXC]; // where a loon at (a, r, c) flies; (-1, -1) = out
Pt target[MAXL]; // position of target cells
bool covered[MAXT][MAXL]; // at time t, is target cell l covered yet?
// dynamic programming: best score at (t, a, r, c) and best direction
int best[MAXT][MAXA][MAXR][MAXC], dir[MAXT][MAXA][MAXR][MAXC];
int left[MAXT][MAXR][MAXC]; // how many new cells covered at (r, c) at time t
// solution: at time t, altitude adjustment for loon b 
int solution[MAXT][MAXB];

// given by problem statement
int columndist(int c1, int c2) { return min(abs(c1 - c2), C - abs(c1 - c2)); }
// does a loon at (r, c) cover target cell l?
int iscovered(int l, int r, int c) {
  int u = target[l].r, v = target[l].c;
  return ((r - u) * (r - u) + columndist(c, v) * columndist(c, v) <= V*V);
}

// return next move for loon b at time t when at position (a, r, c)...
// ... using the results of dynamic programming
int decide_dyn(int b, int t, int a, int r, int c) { return dir[t][a][r][c]; }
// ... using the computed solution
int decide_sol(int b, int t, int a, int r, int c) { return solution[t][b]; }

int simulate(int b, int (*decide)(int, int, int, int, int)) {
  // compute the run of loon b using decision function decide
  // return the score improvement
  int score = 0;
  int r = rs, c = cs, a = 0;
  for (int t = 0; t < T; t++) {
    int bestda = (*decide)(b, t, a, r, c);
    // store the move
    solution[t][b] = bestda;
    // apply it
    a += bestda;
    Pt next = dest[a][r][c];
    r = next.r;
    c = next.c;
    if (r < 0)
      break; // loon exited
    if (a > 0) {
      // update covered target cells
      for (unsigned int i = 0; i < cov[r][c].size(); i++) {
        int l = cov[r][c][i];
        // score improved if target cell not already covered
        score += covered[t+1][l] ? 0 : 1;
        covered[t+1][l] = true;
      }
    }
  }
  return score;
}

void route(int b) {
  // route loon b given the already covered targets (in covered)

  // save a factor A: pre-count the uncovered targets for each cell
  for (int t = 0; t <= T; t++)
    for (int r = 0; r < R; r++)
      for (int c = 0; c < C; c++) {
        int score = 0;
        for (unsigned int i = 0; i < cov[r][c].size(); i++) {
          int l = cov[r][c][i];
          score += covered[t][l] ? 0 : 1;
        }
        left[t][r][c] = score;
      }

  // dynamic programming, t == T is a sentinel value
  for (int t = T-1; t >= 0; t--)
    for (int a = 0; a <= A; a++)
      for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++) {
          int bestda = 0, bestv = 0; // best altitude adjustment, best value
          for (int da = -1; da <= 1; da++) {
            if (a <= 1 && da == -1)
              continue; // can't go down when on ground, or back on ground
            if (a + da > A)
              continue; // can't go above max altitude
            // pretend we moved b by da at time t
            Pt next = dest[a + da][r][c];
            if (next.r < 0)
              break; // loon exited, so score remains 0
            // score if going at these new coordinates, computed dynamically
            int rscore = best[t+1][a+da][next.r][next.c];
            // if above ground, score increased by number of covered targets
            if ((a + da) > 0)
              rscore += left[t+1][next.r][next.c];
            // break ties at random
            if (rscore > bestv || (rscore == bestv && (rand() % 2))) {
              // da is the best altitude adjustment
              bestv = rscore;
              bestda = da;
            }
          }
          // store best altitude adjustment, best value
          best[t][a][r][c] = bestv;
          dir[t][a][r][c] = bestda;
        }
}

void print_sol() {
  FILE *f = fopen("output", "w");
  for (int t = 0; t < T; t++) {
    for (int b = 0; b < B; b++)
      fprintf(f, "%d ", solution[t][b]);
    fprintf(f, "\n");
  }
  fclose(f);
}

int main(int argc, char **argv) {
  srand(42); // make it deterministic
  scanf("%d%d%d", &R, &C, &A);
  scanf("%d%d%d%d", &L, &V, &B, &T);
  scanf("%d%d", &rs, &cs);
  for (int l = 0; l < L; l++) {
    int r, c;
    scanf("%d%d", &r, &c);
    target[l] = Pt(r, c);
  }
  for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++) {
    }
  for (int a = 0; a <= A; a++)
    for (int r = 0; r < R; r++)
      for (int c = 0; c < C; c++)
        if (!a) {
          // wind at altitude 0 does not move loons
          dest[a][r][c] = Pt(r, c);
        } else {
          int dr, dc;
          scanf("%d%d", &dr, &dc);
          // populate dest with the coordinates where the wind takes the loon
          int destr, destc;
          destr = r + dr;
          destc = (c + dc + C) % C;
          if (destr < 0 || destr >= R)
            destr = destc = -1; // loon goes out
          dest[a][r][c] = Pt(destr, destc);
        }

  // compute for each cell the list of targets covered by a loon at this cell
  for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++)
      for (int l = 0; l < L; l++)
        if (iscovered(l, r, c))
          cov[r][c].push_back(l);

  int orig_score = 0;
  // iteratively compute a route for each loon given other routes
  while (true) {
    for (int br = 0; br < B; br++) {
      // route br given the routes of the other loons
      // first, forget about which cells are covered
      for (int t = 0; t <= T; t++)
        for (int l = 0; l < L; l++)
          covered[t][l] = false;
      // then, simulate the other loons (default routes are 0 ... 0)
      int score = 0;
      for (int b = 0; b < B; b++)
        if (b != br)
          score += simulate(b, &decide_sol);
      // now, compute the route of br with dynamic programming
      route(br);
      score += simulate(br, &decide_dyn);
      fprintf(stderr, "route %d\n", br);
      if (score > orig_score) {
        fprintf(stderr, "score was %d is %d\n", orig_score, score);
        orig_score = score;
        print_sol();
      }
    }
  }

  return 0;
}

Extensions

The above code gets stuck fairly quickly. After reaching 698684 in about 17 minutes on my machine, it painfully and progressively goes up to 698734 in about 30 more minutes, and then stalls and does not seem to improve further (I left it running for about 30 additional minutes). Of course, this may vary given your choice of RNG seed (I hardcoded one in the code for reproducibility), and indeed for some unlucky seeds (one out of 5 that I tested) it seems that the code fails to reach a winning score. In any case, our final score of 700913 was achieved with a slightly more elaborate approach. If anyone is brave enough to want to have a look at our actual code, it is here.

We used the following additional improvement: whenever iterating over loons no longer makes progress, start trying to reroute two loons (or more than two) instead of just one. When doing this, unlike when rerouting only one loon, the solution score may decrease, so the code must rollback to the previous solution if the solution got worse. (If the score is still the same but the solution is different, however, it is good to keep the change, so that further optimizations with just one loon can be more effective.) We alternated in parallel optimization attempts with a single loon and attempts with two or three loons that did not make things worse. To be precise, we also tweaked solutions twice, by moving as many as 4 loons, at the expense of a slight drop in quality, to escape local optima and reach better solutions.

All of this was very hacky and we did not have a clean way to run many explorations in parallel on multiple machines, passing improved solutions to other running instances as they were found, some being more adventurous and others more conservative, and hopefully following what is known about metaheuristics. I trust that such approaches will be explored to unimaginable depths during the extended online contest. ;) I don't know if a more clever approach could yield substantial score improvements (rather than incremental ones); this may also turn up during the extended contest.

In any case, we had lots of fun during the contest, and we are very grateful to the organizers for making it happen. :)