2019/day20.c

   1 #define _GNU_SOURCE 1
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include <stdarg.h>
   6 #include <stdbool.h>
   7 #include <stdint.h>
   8 #include <inttypes.h>
   9 #include <ctype.h>
  10 #include <limits.h>
  11 #include <unistd.h>
  12
  13 static int debug_level = -1;
  14 static void
  15 debug_init(void) {
  16   if (debug_level < 0)
  17     debug_level = atoi(getenv("DEBUG") ?: "0");
  18 }
  19
  20 static void __attribute__((format(printf, 2, 3)))
  21 debug_raw(int level, const char *fmt, ...) {
  22   va_list ap;
  23   if (debug_level < 0)
  24     debug_level = atoi(getenv("DEBUG") ?: "0");
  25   if (debug_level >= level) {
  26     va_start(ap, fmt);
  27     vfprintf(stderr, fmt, ap);
  28     va_end(ap);
  29   }
  30 }
  31 #define debug(...) debug_raw(1, __VA_ARGS__)
  32
  33 static int __attribute__((noreturn)) __attribute__((format(printf, 1, 2)))
  34 die(const char *fmt, ...)
  35 {
  36   va_list ap;
  37   va_start(ap, fmt);
  38   vprintf(fmt, ap);
  39   va_end(ap);
  40   putchar('\n');
  41   exit(1);
  42 }
  43
  44 #define MAX 133
  45 #define PORTALS 60
  46 enum dir { U, R, D, L };
  47 struct grid_elt {
  48   char tile;
  49   uint8_t idx;
  50   short distance;
  51 };
  52 typedef struct grid_elt grid_row[MAX + 1];
  53 typedef grid_row grid_full[MAX];
  54 static grid_full grids[PORTALS];
  55 static int maxx, maxy;
  56 static int oleft, oright, otop, obottom; /* inclusive corner coords */
  57 static int ileft, iright, itop, ibottom;
  58 static int thick, scans;
  59 union pt {
  60   int i;
  61   struct {
  62     uint8_t x, y, z;
  63     uint8_t d; /* enum dir */
  64   };
  65 };
  66 static struct portal {
  67   char id[3];
  68   union pt p1, p2;
  69 } portals[PORTALS];
  70 static int nportals;
  71 static uint8_t aa = -1, zz = -1;
  72
  73 static union pt (*next)(union pt p, enum dir d);
  74
  75 static union pt next_flat(union pt p, enum dir d) {
  76   int8_t idx = grids[p.z][p.y][p.x].idx;
  77
  78   p.d = d;
  79   if (idx >= 0 && portals[idx].p1.i == p.i) {
  80     p = portals[idx].p2;
  81     p.d ^= 2;
  82     debug("traveling through portal %s\n", portals[idx].id);
  83     return p;
  84   }
  85   if (idx >= 0 && portals[idx].p2.i == p.i) {
  86     p = portals[idx].p1;
  87     p.d ^= 2;
  88     debug("traveling through portal %s\n", portals[idx].id);
  89     return p;
  90   }
  91   switch (p.d) {
  92   case U: p.y--; break;
  93   case R: p.x++; break;
  94   case D: p.y++; break;
  95   case L: p.x--; break;
  96   }
  97   return p;
  98 }
  99
 100 static union pt next_recursive(union pt p, enum dir d) {
 101   int8_t idx = grids[p.z][p.y][p.x].idx;
 102   int z = p.z;
 103
 104   p.d = d;
 105   if (idx >= 0 && portals[idx].p1.x == p.x && portals[idx].p1.y == p.y &&
 106       portals[idx].p1.d == p.d) {
 107     if (idx == aa || idx == zz) {
 108       if (!z)
 109         die("unexpected end-point visit");
 110       debug("outer portal %s blocked at inner level %d\n", portals[idx].id, z);
 111       p.x = p.y = 2;
 112     } else if (!z) {
 113       debug("outer portal %s blocked at outer level\n", portals[idx].id);
 114       p.x = p.y = 2;
 115     } else {
 116       debug("traveling from level %d into outer portal %s\n", z,
 117             portals[idx].id);
 118       p = portals[idx].p2;
 119       p.d ^= 2;
 120       p.z = z - 1;
 121     }
 122     return p;
 123   }
 124   if (idx >= 0 && portals[idx].p2.x == p.x && portals[idx].p2.y == p.y &&
 125       portals[idx].p2.d == p.d) {
 126     p = portals[idx].p1;
 127     p.d ^= 2;
 128     if (p.z == nportals - 1) {
 129       debug("too much recursion into inner portal %s\n", portals[idx].id);
 130       p.x = p.y = 2;
 131     } else {
 132       debug("traveling from level %d into inner portal %s\n", z,
 133             portals[idx].id);
 134       p.z = z + 1;
 135     }
 136     return p;
 137   }
 138   switch (p.d) {
 139   case U: p.y--; break;
 140   case R: p.x++; break;
 141   case D: p.y++; break;
 142   case L: p.x--; break;
 143   }
 144   return p;
 145 }
 146
 147 static int
 148 minu(unsigned int a, unsigned b) {
 149   return a < b ? a : b;
 150 }
 151
 152 static void
 153 dump(int l) {
 154   int x, y;
 155   grid_row *g;
 156
 157   if (debug_level < 2)
 158     return;
 159   if (l >= nportals)
 160     die("too much recursion");
 161   g = grids[l];
 162   debug("\n *** level %d grid:\n", l);
 163   for (y = 0; y < maxy; y++) {
 164     for (x = 0; x <= maxx; x++)
 165       debug(" %c", g[y][x].tile);
 166     for (x = 0; x < maxx; x++) {
 167       if (isatty(fileno(stderr)))
 168         switch (g[y][x].distance / 100U) {
 169         case 0: break;
 170         case 1: debug("\x1b[32m"); break;
 171         case 2: debug("\x1b[33m"); break;
 172         case 3: debug("\x1b[34m"); break;
 173         default: debug("\x1b[35m"); break;
 174         }
 175       debug("%2d", g[y][x].distance % 100);
 176       if (isatty(fileno(stderr)))
 177         debug("\x1b[0m");
 178     }
 179     debug("\n\n");
 180   }
 181 }
 182
 183 static int deepest;
 184 static short
 185 scan_one(union pt p, short d, int depth) {
 186   int r = -1;
 187
 188   if (depth > deepest)
 189     deepest = depth;
 190   if (grids[p.z][p.y][p.x].tile != '.')
 191     return -1;
 192   scans++;
 193   if ((unsigned) grids[p.z][p.y][p.x].distance < d)
 194     return -1;
 195   grids[p.z][p.y][p.x].distance = d;
 196   if (!p.z && grids[p.z][p.y][p.x].idx == zz) {
 197     debug("found ZZ at distance %d\n", d);
 198     return d;
 199   }
 200   if (d++ == SHRT_MAX)
 201     die("recompile with 32-bit distance");
 202   if (p.d != D)
 203     r = minu(r, scan_one(next(p, U), d, depth + 1));
 204   if (p.d != L)
 205     r = minu(r, scan_one(next(p, R), d, depth + 1));
 206   if (p.d != U)
 207     r = minu(r, scan_one(next(p, D), d, depth + 1));
 208   if (p.d != R)
 209     r = minu(r, scan_one(next(p, L), d, depth + 1));
 210   return r;
 211 }
 212
 213 static void
 214 portal(int x, int y, enum dir d, bool outer) {
 215   char id[3] = "";
 216   int i;
 217
 218   switch (d) {
 219   case U:
 220     id[0] = grids[0][y - 2][x].tile;
 221     id[1] = grids[0][y - 1][x].tile;
 222     break;
 223   case R:
 224     id[0] = grids[0][y][x + 1].tile;
 225     id[1] = grids[0][y][x + 2].tile;
 226     break;
 227   case D:
 228     id[0] = grids[0][y + 1][x].tile;
 229     id[1] = grids[0][y + 2][x].tile;
 230     break;
 231   case L:
 232     id[0] = grids[0][y][x - 2].tile;
 233     id[1] = grids[0][y][x - 1].tile;
 234     break;
 235   }
 236   debug("labeling %s portal %s at %d,%d %c\n", outer ? "outer" : "inner",
 237         id, x, y, "URDL"[d]);
 238   for (i = 0; i < nportals; i++)
 239     if (!strcmp(portals[i].id, id))
 240       break;
 241   grids[0][y][x].idx = i;
 242   if (i == nportals) {
 243     if (++nportals == PORTALS)
 244       die("recompile with larger PORTALS");
 245     if (!outer)
 246       die("portal %s has no outer counterpart", id);
 247     memcpy(portals[i].id, id, 3);
 248     portals[i].p1.x = x;
 249     portals[i].p1.y = y;
 250     portals[i].p1.d = d;
 251     if (!strcmp("AA", id)) {
 252       aa = i;
 253       portals[i].p2.x = x - (d == L) + (d == R);
 254       portals[i].p2.y = y - (d == U) + (d == D);
 255       portals[i].p2.d = d ^ 2;
 256     } else if (!strcmp("ZZ", id))
 257       zz = i;
 258   } else {
 259     if (outer || portals[i].p2.x || i == aa || i == zz)
 260       die("portal %s seen too many times", id);
 261     portals[i].p2.x = x;
 262     portals[i].p2.y = y;
 263     portals[i].p2.d = d;
 264   }
 265 }
 266
 267 static bool
 268 in_maze(int x, int y) {
 269   char c = grids[0][y][x].tile;
 270
 271   return c == '.' || c == '#';
 272 }
 273
 274 static int
 275 find_portals(void) {
 276   int count = 0, i, j;
 277
 278   j = maxy / 2;
 279   while (in_maze(thick + 2, j))
 280     thick++;
 281   if (thick * 2 + 9 > maxx)
 282     die("can't find hole");
 283   oleft = 2;
 284   oright = maxx - 3;
 285   otop = 2;
 286   obottom = maxy - 3;
 287   ileft = oleft + thick - 1;
 288   iright = oright - thick + 1;
 289   itop = otop + thick - 1;
 290   ibottom = obottom - thick + 1;
 291
 292   for (i = 0; i < maxx; i++)
 293     if (in_maze(i, 0) || in_maze(i, 1) ||
 294         in_maze(i, obottom + 1) || in_maze(i, obottom + 2))
 295     die("upper/lower rows incorrect");
 296   for (j = otop; j <= obottom; j++)
 297     if (in_maze(0, j) || in_maze(1, j) ||
 298         in_maze(oright + 1, j) || in_maze(oright + 2, j))
 299       die("left/right columns incorrect");
 300   if (grids[0][otop][oleft].tile != '#' ||
 301       grids[0][otop][oright].tile != '#' ||
 302       grids[0][obottom][oleft].tile != '#' ||
 303       grids[0][obottom][oright].tile != '#')
 304     die("corners incorrect");
 305   for (j = itop + 1; j < ibottom; j++)
 306     for (i = ileft + 1; i < iright; i++)
 307       if (in_maze(i, j))
 308         die("hole incorrect");
 309
 310   for (j = otop, i = oleft + 1; i < oright; i++)
 311     if (grids[0][j][i].tile == '.')
 312       portal(i, j, U, true);
 313   for (i = oright, j = otop + 1; j < obottom; j++)
 314     if (grids[0][j][i].tile == '.')
 315       portal(i, j, R, true);
 316   for (j = obottom, i = oleft + 1; i < oright; i++)
 317     if (grids[0][j][i].tile == '.')
 318       portal(i, j, D, true);
 319   for (i = oleft, j = otop + 1; j < obottom; j++)
 320     if (grids[0][j][i].tile == '.')
 321       portal(i, j, L, true);
 322
 323   for (j = itop, i = ileft + 1; i < iright; i++)
 324     if (grids[0][j][i].tile == '.')
 325       portal(i, j, D, false);
 326   for (i = iright, j = itop + 1; j < ibottom; j++)
 327     if (grids[0][j][i].tile == '.')
 328       portal(i, j, L, false);
 329   for (j = ibottom, i = ileft + 1; i < iright; i++)
 330     if (grids[0][j][i].tile == '.')
 331       portal(i, j, U, false);
 332   for (i = ileft, j = itop + 1; j < ibottom; j++)
 333     if (grids[0][j][i].tile == '.')
 334       portal(i, j, R, false);
 335
 336   if (aa > PORTALS || zz > PORTALS)
 337     die("can't find aa/zz");
 338   for (i = 0; i < nportals; i++) {
 339     if (i == aa || i == zz)
 340       continue;
 341     if (!portals[i].p2.x)
 342       die("no matching inner portal for %s", portals[i].id);
 343   }
 344   return count;
 345 }
 346
 347 int
 348 main(int argc, char **argv) {
 349   int ch, i;
 350   int x = 0, y = 0;
 351   int best;
 352
 353   debug_init();
 354   if (argc > 1 && strcmp(argv[1], "-"))
 355     if (!(stdin = freopen(argv[1], "r", stdin))) {
 356       perror("failure");
 357       exit(2);
 358     }
 359
 360   memset(grids[0], -1, sizeof grids[0]);
 361   while ((ch = getchar()) != EOF) {
 362     grids[0][y][x].tile = ch;
 363     if (ch == '\n') {
 364       if (y && x != maxx)
 365         die("uneven line lengths");
 366       x = 0;
 367       maxy = ++y;
 368       continue;
 369     }
 370     if (y >= MAX)
 371       die("recompile with larger MAX y");
 372     x++;
 373     if (!y) {
 374       if (x >= MAX + 1)
 375         die("recompile with larger MAX x");
 376       maxx = x;
 377     } else if (x > maxx) {
 378       die("uneven line length");
 379     }
 380   }
 381   if (maxx < 11 || maxy < 11)
 382     die("grid is too small");
 383
 384   dump(0);
 385   find_portals();
 386   for (i = 1; i < nportals; i++)
 387     memcpy(grids[i], grids[0], sizeof grids[0]);
 388   next = next_flat;
 389
 390   printf("maze loaded. thickness:%d portals:%d AA:%d,%d ZZ:%d,%d\n",
 391          thick, nportals, portals[aa].p1.x, portals[aa].p1.y,
 392          portals[zz].p1.x, portals[zz].p1.y);
 393   best = scan_one(next(portals[aa].p2, portals[aa].p2.d), 0, 0);
 394   dump(0);
 395   printf("best flat path in %d steps, with %d scans and call depth %d\n",
 396          best, scans, deepest);
 397
 398   memcpy(grids[0], grids[1], sizeof grids[0]);
 399   next = next_recursive;
 400   scans = 0;
 401   best = scan_one(next(portals[aa].p2, portals[aa].p2.d), 0, 0);
 402   for (i = 0; i < nportals; i++)
 403     dump(i);
 404   if (best >= 0)
 405     printf("best recursive path in %d steps, with %d scans and call depth %d\n",
 406            best, scans, deepest);
 407   else
 408     printf("no recursive path found after %d scans and call depth %d\n",
 409            scans, deepest);
 410
 411   return 0;
 412 }