2019/day18.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 <search.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 81
  45 struct grid {
  46   char tile;
  47   short distance;
  48 } grid[MAX][MAX + 1];
  49 static int maxx, maxy;
  50 struct progress {
  51   short distance;
  52   uint64_t seen; /* bitmap: 0-25 keys, 32-57 doors */
  53 };
  54 struct pt {
  55   char id;
  56   uint8_t x;
  57   uint8_t y;
  58   uint8_t q;
  59   struct progress to_keys[26];
  60 };
  61 static struct pt cursor[4];
  62 static struct pt keys[26];
  63 static struct pt doors[26];
  64 static int k; /* number of keys */
  65
  66 enum dir { NONE = -1, U, R, D, L };
  67
  68 static int deepest;
  69
  70 static struct pt *
  71 key(char c) {
  72   if (c < 'a' || c > 'z')
  73     die("invalid key '%c'", c);
  74   return &keys[c - 'a'];
  75 }
  76
  77 static uint64_t key_mask(char c) {
  78   if (c < 'a' || c > 'z')
  79     die("invalid key '%c'", c);
  80   return 1 << (c - 'a');
  81 }
  82
  83 static struct pt *
  84 door(char c) {
  85   if (c < 'A' || c > 'Z')
  86     die("invalid door '%c'", c);
  87   return &doors[c - 'A'];
  88 }
  89
  90 static uint64_t door_mask(char c) {
  91   if (c < 'A' || c > 'Z')
  92     die("invalid key '%c'", c);
  93   return 1ULL << (32 + (c - 'A'));
  94 }
  95
  96 static int
  97 minu(unsigned int a, unsigned b) {
  98   return a < b ? a : b;
  99 }
 100
 101 static void
 102 dump_grid(void) {
 103   int x, y;
 104
 105   if (!debug_level)
 106     return;
 107   for (y = 0; y < maxy; y++) {
 108     for (x = 0; x <= maxx; x++)
 109       debug(" %c", grid[y][x].tile);
 110     for (x = 0; x < maxx; x++)
 111       debug("%2d", grid[y][x].distance);
 112     debug("\n\n");
 113   }
 114 }
 115
 116 static const char *
 117 mask_to_str(uint64_t mask) {
 118   static char buf[26 * 2 + 1];
 119   int i;
 120   char *p = buf;
 121   for (i = 0; i < 26; i++)
 122     if (mask & (1 << i))
 123       *p++ = 'a' + i;
 124   for (i = 0; i < 26; i++)
 125     if (mask & (1ULL << (32 + i)))
 126       *p++ = 'A' + i;
 127   *p = '\0';
 128   return buf;
 129 }
 130
 131 static void
 132 dump_point(struct pt *p, int k) {
 133   int i;
 134
 135   debug("point %c at %d,%d quadrant %d:\n", p->id, p->x, p->y, p->q);
 136   for (i = 0; i < k; i++)
 137     if (p->to_keys[i].distance == -1)
 138       debug( "to key %c: impossible, reached by other bot\n", 'a' + i);
 139     else
 140       debug(" to key %c: %d steps, encounter '%s'\n", 'a' + i,
 141             p->to_keys[i].distance, mask_to_str(p->to_keys[i].seen));
 142 }
 143
 144 static short
 145 scan_one(int x, int y, enum dir from, short d, uint64_t seen,
 146          struct progress *prog, int q) {
 147   int t;
 148   int r = -1;
 149
 150   if (d > deepest)
 151     deepest = d;
 152   if (grid[y][x].tile == '#')
 153     return -1;
 154   if ((unsigned) grid[y][x].distance < d)
 155     return -1;
 156   grid[y][x].distance = d;
 157   t = grid[y][x].tile;
 158   if (isupper(t))
 159     seen |= door_mask(t);
 160   else if (islower(t)) {
 161     seen |= key_mask(t);
 162     prog[t - 'a'].distance = d;
 163     prog[t - 'a'].seen = seen;
 164     key(t)->q = q;
 165     if (!(seen >> 32))
 166       r = d;
 167   }
 168   d++;
 169   if (from != D)
 170     r = minu(r, scan_one(x, y - 1, U, d, seen, prog, q));
 171   if (from != L)
 172     r = minu(r, scan_one(x + 1, y, R, d, seen, prog, q));
 173   if (from != U)
 174     r = minu(r, scan_one(x, y + 1, D, d, seen, prog, q));
 175   if (from != R)
 176     r = minu(r, scan_one(x - 1, y, L, d, seen, prog, q));
 177   return r;
 178 }
 179
 180 static int
 181 scan_from(struct pt *p, int k, int q) {
 182   int i, j, r;
 183
 184   debug("scanning from %d,%d (%c)\n", p->x, p->y, p->id);
 185   for (j = 0; j < maxy; j++)
 186     for (i = 0; i < maxx; i++)
 187       grid[j][i].distance = -1;
 188   r = scan_one(p->x, p->y, NONE, 0, 0, p->to_keys, q);
 189   dump_point(p, k);
 190   return r;
 191 }
 192
 193 /* https://en.wikipedia.org/wiki/A*_search_algorithm */
 194 #define MAXWORK 10000
 195 #define MAXNODE (128 * 1024)
 196 #define QUAD(n) (((n) >> 28) & 3)
 197 #define FROM_Q(n, q) (((n) >> (32 + (q) * 8)) & 0x1f)
 198 #define FROM(n) FROM_Q(n, QUAD(n))
 199 #define KEYS(n) ((n) & ((1 << 26) - 1))
 200 static struct node {
 201   long long n; /* combination of QUAD, FROM and KEYS */
 202   long long parent; /* which node we were on previously */
 203   short g; /* cheapest known path from start to here */
 204   short f; /* estimate based on g + h(n) */
 205 } nodes[MAXNODE];
 206 static int nnodes;
 207 static void *root; /* tree of nodes visited */
 208
 209 static struct work {
 210   long long node; /* node needing another visit */
 211   short next; /* index of next pending, sorted by decreasing f, -1 if none */
 212   short prev; /* index of prev node, -1 if none */
 213   short f; /* estimated distance */
 214 } pending[MAXWORK];
 215 static short head = -1; /* head of pending, -1 if empty */
 216 static short unused; /* first unused index of pending */
 217 static short avail = -1; /* head of free list for reuse of slots in pending */
 218
 219 static bool
 220 drop(long long node) {
 221   int i = head;
 222   while (i != -1) {
 223     if (pending[i].node == node) {
 224       if (i == head) {
 225         head = pending[i].next;
 226       } else {
 227         pending[pending[i].prev].next = pending[i].next;
 228         if (pending[i].next != -1)
 229           pending[pending[i].next].prev = pending[i].prev;
 230       }
 231       pending[i].next = avail;
 232       avail = i;
 233       return true;
 234     }
 235     i = pending[i].next;
 236   }
 237   return false;
 238 }
 239
 240 static void
 241 add(long long node, int f) {
 242   int next;
 243   int i;
 244
 245   if (avail != -1) {
 246     next = avail;
 247     avail = pending[next].next;
 248   } else {
 249     next = unused;
 250     if (++unused == MAXWORK)
 251       die("recompile with larger MAXWORK");
 252   }
 253   pending[next].node = node;
 254   pending[next].f = f;
 255   if (head == -1 || f < pending[head].f) {
 256     pending[next].next = head;
 257     pending[next].prev = -1;
 258     head = next;
 259   } else {
 260     i = head;
 261     while (pending[i].next != -1 && f >= pending[pending[i].next].f)
 262       i = pending[i].next;
 263     pending[next].next = pending[i].next;
 264     pending[next].prev = i;
 265     pending[i].next = next;
 266   }
 267   if (pending[next].next != -1)
 268     pending[pending[next].next].prev = next;
 269 }
 270
 271 static int
 272 compare(const void *pa, const void *pb) {
 273   const struct node *a = pa, *b = pb;
 274
 275   return (b->n > a->n) - (b->n < a->n);
 276 }
 277
 278 static struct node *
 279 lookup(long long node) {
 280   struct node *n = &nodes[nnodes];
 281   void *p;
 282
 283   n->n = node;
 284   p = tsearch(n, &root, compare);
 285   if (!p)
 286     die("out of memory");
 287   if (*(struct node **)p == n && ++nnodes == MAXNODE)
 288     die("recompile with larger MAXNODE");
 289   return *(struct node **)p;
 290 }
 291
 292 static void
 293 path(long long node, int q) {
 294   struct node *n;
 295
 296   if (!KEYS(node))
 297     return;
 298   n = lookup(node);
 299   if (n->parent == -1) {
 300     puts("<uncomputed...>");
 301     return;
 302   }
 303   path(n->parent, q);
 304   if (node == -1)
 305       putchar('\n');
 306   else if (QUAD(n->n) == q)
 307     putchar(FROM_Q(n->n, q) + 'a');
 308   else
 309     putchar(' ');
 310 }
 311
 312 static int
 313 h(long long n, int bots) {
 314   int q, r = 0;
 315
 316   for (q = 0; q < bots; q++) {
 317     int from = FROM_Q(n, q);
 318     struct pt *p = from == 0x1f ? &cursor[q] : &keys[from];
 319     int i, b = 0;
 320
 321     for (i = 0; i < k; i++)
 322       if (!(n & (1 << i)) && p->q == q && p->to_keys[i].distance > b)
 323         b = p->to_keys[i].distance;
 324     r += b;
 325   }
 326   return r;
 327 }
 328
 329 static void
 330 nop(void *ignored) {
 331 }
 332
 333 static const char *
 334 from_str(long long n, int bots) {
 335   static char buf[5] = "";
 336   int i;
 337
 338   for (i = 0; i < bots; i++)
 339     buf[i] = FROM_Q(n, i) == 0x1f ? '@' : FROM_Q(n, i) + 'a';
 340   buf[i] = '\0';
 341   return buf;
 342 }
 343
 344 static int
 345 astar(int bots) {
 346   struct node *n;
 347   int i, q, count = 0;
 348   long long next = 0;
 349
 350   tdestroy(root, nop);
 351   root = NULL;
 352   memset(nodes, -1, sizeof nodes);
 353   nnodes = 0;
 354   for (q = 0; q < bots; q++)
 355     next |= 0x1fLL << (32 + q * 8);
 356   n = lookup(next);
 357   n->g = 0;
 358   n->f = h(next, bots);
 359   add(next, n->f);
 360   while (head != -1) {
 361     long long current = pending[head].node;
 362     struct pt *p;
 363     unsigned tentative;
 364     struct node *n2;
 365
 366     n = lookup(current);
 367     count++;
 368     if (KEYS(n->n) == (1 << k) - 1) {
 369       printf("search done with %d iterations, %d nodes, %d depth\n",
 370             count, nnodes, unused);
 371       n2 = lookup(-1);
 372       n2->parent = current;
 373       n2->g = n->g;
 374       return n->g;
 375     }
 376     debug("considering %07llx at %s from quad %lld\n", KEYS(n->n),
 377           from_str(n->n, bots), QUAD(n->n));
 378     drop(current);
 379     for (i = 0; i < k; i++) {
 380       if (current & (1 << i))
 381         continue; /* already have key */
 382       q = keys[i].q;
 383       p = FROM_Q(n->n, q) == 0x1f ? &cursor[q] : &keys[FROM_Q(n->n, q)];
 384       if (((p->to_keys[i].seen >> 32) | (int)p->to_keys[i].seen)
 385           & ~(KEYS(n->n) | (1 << i)))
 386         continue; /* still blocked by door, or will reach another key first */
 387       tentative = n->g + p->to_keys[i].distance;
 388       next = current | (1 << i);
 389       next &= ~((0x1fLL << (32 + q * 8)) | (3 << 28));
 390       next |= ((0LL + i) << (32 + q * 8)) | (q << 28);
 391       n2 = lookup(next);
 392       if (tentative < n2->g) {
 393         n2->parent = current;
 394         n2->g = tentative;
 395         n2->f = tentative + h(next, bots);
 396         drop(next);
 397         add(next, n2->f);
 398         debug("need to visit %07llx through %s quad %d, steps %d + %d = %d\n",
 399               KEYS(n2->n), from_str(next, bots), q, n2->g, n2->f-n2->g, n2->f);
 400       }
 401     }
 402   }
 403   die("no path found");
 404 }
 405
 406 int
 407 main(int argc, char **argv) {
 408   int ch, i;
 409   int x = 0, y = 0;
 410   struct pt *p;
 411   int d = 0;
 412   int best, count;
 413
 414   debug_init();
 415   if (argc > 1 && strcmp(argv[1], "-"))
 416     if (!(stdin = freopen(argv[1], "r", stdin))) {
 417       perror("failure");
 418       exit(2);
 419     }
 420
 421   while ((ch = getchar()) != EOF) {
 422     grid[y][x].tile = ch;
 423     if (ch == '\n') {
 424       if (y && x != maxx)
 425         die("uneven line lengths");
 426       x = 0;
 427       maxy = ++y;
 428       continue;
 429     }
 430     if (y >= MAX)
 431       die("recompile with larger MAX y");
 432     p = NULL;
 433     if (ch == '@') {
 434       p = &cursor[0];
 435     } else if (ch >= 'a' && ch <= 'z') {
 436       p = key(ch);
 437       k++;
 438     } else if (ch >= 'A' && ch <= 'Z') {
 439       p = door(ch);
 440       d++;
 441     } else if (ch != '.' && ch != '#')
 442       die("unexpected character %c", ch);
 443     if (p) {
 444       p->id = ch;
 445       if (p->x)
 446         die("duplicate character %c", ch);
 447       p->x = x;
 448       p->y = y;
 449     }
 450     x++;
 451     if (!y) {
 452       if (ch != '#')
 453         die("expected wall in row 0");
 454       if (x >= MAX + 1)
 455         die("recompile with larger MAX x");
 456       maxx = x;
 457     } else if (x > maxx) {
 458       die("uneven line length");
 459     }
 460   }
 461   count = 0;
 462   for (i = 0; i < k; i++)
 463     if (!keys[i].x)
 464       die("nonconsecutive keys");
 465     else if (doors[i].x)
 466       count++;
 467   if (d != count || d > k)
 468     die("mismatched doors");
 469   if (!cursor[0].x)
 470     die ("missing cursor");
 471   printf("Operating on %dx%d grid from %d,%d, with %d keys, %d doors\n",
 472          maxx, maxy, cursor[0].x, cursor[0].y, k, d);
 473
 474   for (i = 0; i < k; i++)
 475     if (doors[i].x)
 476       scan_from(door(i + 'A'), k, 0);
 477   for (i = 0; i < k; i++)
 478     scan_from(key(i + 'a'), k, 0);
 479   best = scan_from(&cursor[0], k, 0);
 480   printf("current closest key %d steps away\n", best);
 481   printf("all paths explored, furthest distance %d\n", deepest);
 482   if (deepest * k > SHRT_MAX)
 483     die("recompile with 32-bit distance");
 484   dump_grid();
 485   best = astar(1);
 486   printf("best path requires %d steps, using path ", best);
 487   path(-1, 0);
 488
 489   x = cursor[0].x;
 490   y = cursor[0].y;
 491   if (grid[y - 1][x - 1].tile != '.' || grid[y - 1][x].tile != '.' ||
 492       grid[y - 1][x + 1].tile != '.' || grid[y][x - 1].tile != '.' ||
 493       grid[y][x + 1].tile != '.' || grid[y + 1][x - 1].tile != '.' ||
 494       grid[y + 1][x].tile != '.' || grid[y + 1][x + 1].tile != '.')
 495     die("grid not suitable for part 2");
 496   grid[y - 1][x].tile = '#';
 497   grid[y][x - 1].tile = '#';
 498   grid[y + 1][x].tile = '#';
 499   grid[y][x + 1].tile = '#';
 500   dump_grid();
 501   best = 0;
 502   for (i = 0; i < k; i++) {
 503     memset(key(i + 'a')->to_keys, -1, sizeof p->to_keys);
 504     scan_from(key(i + 'a'), k, 0);
 505   }
 506   cursor[0].x--;
 507   cursor[0].y--;
 508   cursor[1] = cursor[0];
 509   cursor[1].x += 2;
 510   cursor[2] = cursor[0];
 511   cursor[2].x += 2;
 512   cursor[2].y += 2;
 513   cursor[3] = cursor[0];
 514   cursor[3].y += 2;
 515   for (i = 0; i < 4; i++) {
 516     memset(cursor[i].to_keys, -1, sizeof cursor[i].to_keys);
 517     cursor[i].q = i;
 518     scan_from(&cursor[i], k, i);
 519   }
 520   head = -1;
 521   unused = 0;
 522   avail = -1;
 523   memset(pending, -1, sizeof pending);
 524   best += astar(4);
 525   printf("using 4 bots requires %d steps, with path:\n", best);
 526   for (i = 0; i < 4; i++)
 527     path(-1, i);
 528   return 0;
 529 }