2019/day17.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 <limits.h>
  10 #include <ctype.h>
  11
  12 #define LIMIT 10000
  13 static int64_t orig[LIMIT];
  14 static int len;
  15 struct state {
  16   int id;
  17   int64_t a[LIMIT];
  18   int pc;
  19   int base;
  20   bool has_in;
  21   int64_t in;
  22   bool has_out;
  23   int64_t out;
  24   int steps;
  25 };
  26
  27 static int debug_level = -1;
  28 static void
  29 debug_init(void) {
  30   if (debug_level < 0)
  31     debug_level = atoi(getenv("DEBUG") ?: "0");
  32 }
  33
  34 static void __attribute__((format(printf, 2, 3)))
  35 debug_raw(int level, const char *fmt, ...) {
  36   va_list ap;
  37   if (debug_level >= level) {
  38     va_start(ap, fmt);
  39     vfprintf(stderr, fmt, ap);
  40     va_end(ap);
  41   }
  42 }
  43 #define debug(...) debug_raw(1, __VA_ARGS__)
  44
  45 static int __attribute__((noreturn)) __attribute__((format(printf, 1, 2)))
  46 die(const char *fmt, ...)
  47 {
  48   va_list ap;
  49   va_start(ap, fmt);
  50   vprintf(fmt, ap);
  51   va_end(ap);
  52   putchar('\n');
  53   exit(1);
  54 }
  55
  56 static void
  57 dump(struct state *s) {
  58   if (debug_level < 2)
  59     return;
  60   debug(" state of id=%d: pc=%d base=%d in=%s%" PRId64 " out=%s%" PRId64
  61         " steps=%d\n", s->id, s->pc, s->base,
  62         s->has_in ? "" : "!", s->in, s->has_out ? "" : "!", s->out, s->steps);
  63   for (int i = 0; i < len; i++)
  64     debug_raw(3, "%" PRId64 ",", s->a[i]);
  65   debug_raw(3, "\n");
  66 }
  67
  68 static void __attribute__((noreturn))
  69 crash(struct state *s, const char *msg) {
  70   printf("invalid program id=%d, pc=%d: %s\n", s->id, s->pc, msg);
  71   exit(1);
  72 }
  73
  74 static int64_t
  75 get(struct state *s, int param) {
  76   int64_t op = s->a[s->pc];
  77   int scale = 10;
  78   int mode;
  79   int64_t value;
  80
  81   if (op > 99999 || op < 0)
  82     crash(s, "unexpected opcode");
  83   if (s->pc + param > LIMIT)
  84     crash(s, "memory too short for opcode");
  85   value = s->a[s->pc + param];
  86   while (param--)
  87     scale *= 10;
  88   mode = (op / scale) % 10;
  89   debug_raw(3, "get op=%" PRId64 " mode=%d value=%" PRId64 "\n",
  90             op, mode, value);
  91   switch (mode) {
  92   case 0:
  93     if (value > LIMIT || value < 0)
  94       crash(s, "in position mode, param beyond memory");
  95     return s->a[value];
  96   case 1:
  97     return value;
  98   case 2:
  99     value += s->base;
 100     if (value > LIMIT || value < 0)
 101       crash(s, "in relative mode, param beyond memory");
 102     return s->a[value];
 103   default:
 104     crash(s, "unexpected mode");
 105   }
 106 }
 107
 108 static void
 109 put(struct state *s, int param, int64_t value) {
 110   int64_t op = s->a[s->pc];
 111   int scale = 10;
 112   int mode;
 113   int64_t offset;
 114
 115   if (op > 99999 || op < 0)
 116     crash(s, "unexpected opcode");
 117   if (s->pc + param > LIMIT)
 118     crash(s, "memory too short for opcode");
 119   offset = s->a[s->pc + param];
 120   while (param--)
 121     scale *= 10;
 122   mode = (op / scale) % 10;
 123   debug_raw(3, "put op=%" PRId64 " mode=%d value=%" PRId64 " offset=%" PRId64
 124             "\n", op, mode, value, offset);
 125   switch (mode) {
 126   case 0:
 127     if (offset > LIMIT || offset < 0)
 128       crash(s, "in position mode, param beyond memory");
 129     s->a[offset] = value;
 130     return;
 131   case 2:
 132     offset += s->base;
 133     if (offset > LIMIT || offset < 0)
 134       crash(s, "in relative mode, param beyond memory");
 135     s->a[offset] = value;
 136     return;
 137   default:
 138     crash(s, "unexpected mode");
 139   }
 140 }
 141
 142 static void
 143 init(struct state *s, int64_t in) {
 144   memset(s, 0, sizeof  *s);
 145   memcpy(s->a, orig, len * sizeof orig[0]);
 146   s->has_in = true;
 147   s->in = in;
 148   dump(s);
 149 }
 150
 151 /* Returns -1 for stalled on input, 0 for done, 1 for stalled on output */
 152 static int
 153 run(struct state *s) {
 154   int jump;
 155
 156   while (1) {
 157     debug_raw(2, "executing id=%d step=%d pc=%d base=%d %" PRId64
 158               ",%" PRId64 ",%" PRId64 ",%" PRId64 "\n", s->id,
 159               s->steps++, s->pc, s->base, s->a[s->pc], s->a[s->pc+1],
 160               s->a[s->pc+2], s->a[s->pc+3]);
 161     if (!(s->steps % 10000))
 162       debug(" steps=%d\n", s->steps);
 163     if (s->pc > LIMIT || s->pc < 0)
 164       crash(s, "program ran out of bounds");
 165     switch (s->a[s->pc] % 100) {
 166     case 1:
 167       put(s, 3, get(s, 1) + get(s, 2));
 168       jump = 4;
 169       break;
 170     case 2:
 171       put(s, 3, get(s, 1) * get(s, 2));
 172       jump = 4;
 173       break;
 174     case 3:
 175       if (!s->has_in) {
 176         debug_raw(2, "id=%d stalling for input\n", s->id);
 177         s->steps--;
 178         return -1;
 179       }
 180       put(s, 1, s->in);
 181       s->has_in = false;
 182       jump = 2;
 183       break;
 184     case 4:
 185       if (s->has_out) {
 186         debug_raw(2, "id=%d stalling for output\n", s->id);
 187         s->steps--;
 188         return 1;
 189       }
 190       s->has_out = true;
 191       s->out = get(s, 1);
 192       jump = 2;
 193       break;
 194     case 5:
 195       if (get(s, 1)) {
 196         s->pc = get(s, 2);
 197         jump = 0;
 198       } else
 199         jump = 3;
 200       break;
 201     case 6:
 202       if (!get(s, 1)) {
 203         s->pc = get(s, 2);
 204         jump = 0;
 205       } else
 206         jump = 3;
 207       break;
 208     case 7:
 209       put(s, 3, get(s, 1) < get(s, 2));
 210       jump = 4;
 211       break;
 212     case 8:
 213       put(s, 3, get(s, 1) == get(s, 2));
 214       jump = 4;
 215       break;
 216     case 9:
 217       s->base += get(s, 1);
 218       if (s->base < 0 || s->base > LIMIT)
 219         crash(s, "relative base out of bounds");
 220       jump = 2;
 221       break;
 222     case 99:
 223       debug_raw(2, "id=%d halting\n", s->id);
 224       return 0;
 225     default:
 226       crash(s, "unexpected opcode");
 227     }
 228     s->pc += jump;
 229     dump(s);
 230   }
 231 }
 232
 233 static struct state s;
 234
 235 #define GRID 80
 236 static char grid[GRID][GRID];
 237 static int maxx, maxy;
 238
 239 static void
 240 display(void) {
 241   int x, y;
 242
 243   if (!debug_level)
 244     return;
 245   for (y = 0; y <= maxy; y++)
 246     for (x = 0; x <= maxx; x++)
 247       debug("%c", grid[y][x]);
 248 }
 249
 250 enum dir { U = '^', R = '>', D = 'v', L = '<', NONE = 0 };
 251
 252 static enum dir
 253 next(int x, int y, enum dir d) {
 254   switch (d) {
 255   case U:
 256     if (x && grid[y][x - 1] == '#')
 257       return L;
 258     if (x < maxx && grid[y][x + 1] == '#')
 259       return R;
 260   case R:
 261     if (y && grid[y - 1][x] == '#')
 262       return U;
 263     if (y < maxy && grid[y + 1][x] == '#')
 264       return D;
 265     break;
 266   case D:
 267     if (x && grid[y][x - 1] == '#')
 268       return L;
 269     if (x < maxx && grid[y][x + 1] == '#')
 270       return R;
 271     break;
 272   case L:
 273     if (y && grid[y - 1][x] == '#')
 274       return U;
 275     if (y < maxy && grid[y + 1][x] == '#')
 276       return D;
 277     break;
 278   case NONE:
 279     die("unexpected case");
 280   }
 281   return NONE;
 282 }
 283
 284 static int
 285 walk(int *x, int *y, enum dir d) {
 286   int count = 0;
 287   switch (d) {
 288   case U:
 289     while (*y && grid[*y - 1][*x] == '#') {
 290       count++;
 291       --*y;
 292     }
 293     break;
 294   case R:
 295     while (*x < maxx && grid[*y][*x + 1] == '#') {
 296       count++;
 297       ++*x;
 298     }
 299     break;
 300   case D:
 301     while (*y < maxy && grid[*y + 1][*x] == '#') {
 302       count++;
 303       ++*y;
 304     }
 305     break;
 306   case L:
 307     while (*x && grid[*y][*x - 1] == '#') {
 308       count++;
 309       --*x;
 310     }
 311     break;
 312   case NONE:
 313     die("unexpected case");
 314   }
 315   return count;
 316 }
 317
 318 int
 319 main(int argc, char **argv) {
 320   int count = 0;
 321   int x = 0, y = 0, i, j, dir = NONE;
 322   int part1 = 0;
 323   char *p;
 324
 325   debug_init();
 326   if (argc > 1 && strcmp("-", argv[1]))
 327     if (!(stdin = freopen(argv[1], "r", stdin))) {
 328       perror("failure");
 329       exit(2);
 330     }
 331
 332   while (scanf("%" SCNd64 "%*[,\n]", &orig[len]) == 1)
 333     if (len++ > LIMIT - 3)
 334       die("recompile with larger LIMIT");
 335   printf("Read %u slots\n", len);
 336
 337   init(&s, 0);
 338   s.has_in = false;
 339   while (run(&s)) {
 340     count++;
 341     if (!s.has_out)
 342       die("expecting output");
 343     grid[y][x] = s.out;
 344     if (s.out == '\n') {
 345       maxy = ++y;
 346       x = 0;
 347     } else {
 348       if (s.out != '.' && s.out != '#') {
 349         i = x;
 350         j = y;
 351         dir = s.out;
 352       }
 353       if (x > 1 && y > 0 && s.out == '#' && grid[y][x - 1] == '#' &&
 354           grid[y][x - 2] == '#' && grid[y - 1][x - 1] == '#')
 355         part1 += (x - 1) * y;
 356       if (++x > maxx)
 357         maxx = x;
 358     }
 359     if (x >= GRID || y >= GRID)
 360       die("recompile with larger GRID");
 361     s.has_out = false;
 362   }
 363   display();
 364   printf("%d outputs, start at %d,%d, checksum %d\n", count, i, j, part1);
 365   if (dir == NONE)
 366     die("could not find start location");
 367
 368   /* Compute the path */
 369 #define MAXFN 21
 370   char scratch[MAXFN * MAXFN] = "";
 371   char a[MAXFN], b[MAXFN], c[MAXFN], m[MAXFN];
 372   char *pa, *pb, *pc, *pm;
 373   int nextdir = next(i, j, dir);
 374   bool done = false;
 375   int paira, pairb, pairc;
 376
 377   p = scratch;
 378   while (nextdir != NONE) {
 379     count = 0;
 380     if ((dir == U && nextdir == R) || (dir == R && nextdir == D) ||
 381         (dir == D && nextdir == L) || (dir == L && nextdir == U))
 382       p += sprintf(p, "R,");
 383     else
 384       p += sprintf(p, "L,");
 385     dir = nextdir;
 386     p += sprintf(p, "%d,", walk(&i, &j, dir));
 387     nextdir = next(i, j, dir);
 388   }
 389   printf("computed %s\n", scratch);
 390   /* Brute force compression: assumes that each function contains 1-5 pairs */
 391   for (paira = 1; !done && paira <= 5; paira++) {
 392     p = scratch;
 393     memset(m, 0, sizeof m);
 394     pm = m;
 395     i = 0;
 396     pa = a;
 397     do {
 398       if ((*pa++ = *p++) == ',')
 399         i++;
 400     } while (i < paira * 2);
 401     *pa = '\0';
 402     if (pa - a >= MAXFN)
 403       continue;
 404     *pm++ = 'A';
 405     *pm++ = ',';
 406     for (pairb = 1; !done && pairb <= 5; pairb++) {
 407       p = scratch;
 408       pm = m;
 409       while (!strncmp(p, a, pa - a)) {
 410         p += pa - a;
 411         *pm++ = 'A';
 412         *pm++ = ',';
 413       }
 414       i = 0;
 415       pb = b;
 416       do {
 417         if ((*pb++ = *p++) == ',')
 418           i++;
 419       } while (i < pairb * 2);
 420       *pb = '\0';
 421       if (pb - b >= MAXFN)
 422         continue;
 423       *pm++ = 'B';
 424       *pm++ = ',';
 425       for (pairc = 1; !done && pairc <= 5; pairc++) {
 426         p = scratch;
 427         pm = m;
 428         while (!strncmp(p, a, pa - a) ||
 429                !strncmp(p, b, pb - b)) {
 430           if (!strncmp(p, a, pa - a)) {
 431             p += pa - a;
 432             *pm++ = 'A';
 433           } else {
 434             p += pb - b;
 435             *pm++ = 'B';
 436           }
 437           *pm++ = ',';
 438         }
 439         i = 0;
 440         pc = c;
 441         do {
 442           if ((*pc++ = *p++) == ',')
 443             i++;
 444         } while (i < pairc * 2);
 445         *pc = '\0';
 446         if (pc - c >= MAXFN)
 447           continue;
 448         *pm++ = 'C';
 449         *pm++ = ',';
 450         debug("trying A=%s B=%s C=%s ...", a, b, c);
 451         while (*p) {
 452           if (!strncmp(p, a, pa - a)) {
 453             p += pa - a;
 454             *pm++ = 'A';
 455             *pm++ = ',';
 456           } else if (!strncmp(p, b, pb - b)) {
 457             p += pb - b;
 458             *pm++ = 'B';
 459             *pm++ = ',';
 460           } else if (!strncmp(p, c, pc - c)) {
 461             p += pc - c;
 462             *pm++ = 'C';
 463             *pm++ = ',';
 464           } else if (*p) {
 465             break;
 466           }
 467         }
 468         if (*p)
 469           debug("nope\n");
 470         else {
 471           debug("success\n");
 472           done = true;
 473         }
 474       }
 475     }
 476   }
 477   if (!done)
 478     die("unable to compress");
 479   debug("compressed: %s\n", m);
 480   p = stpcpy(scratch, m);
 481   p[-1] = '\n';
 482   p = stpcpy(p, a);
 483   p[-1] = '\n';
 484   p = stpcpy(p, b);
 485   p[-1] = '\n';
 486   p = stpcpy(p, c);
 487   p[-1] = '\n';
 488   *p++ = argc > 2 ? argv[2][0] : 'n';
 489   *p++ = '\n';
 490   *p++ = '\0';
 491   printf("input will be:\n%s", scratch);
 492
 493   /* And finally use the input */
 494   init(&s, 0);
 495   s.a[0] = 2;
 496   s.has_in = false;
 497   p = scratch;
 498   while (run(&s) && *p) {
 499     if (s.has_out) {
 500       if (isascii(s.out))
 501         debug("read '%c'\n", (char)s.out);
 502       else
 503         die("unexpected output %" PRId64, s.out);
 504       s.has_out = false;
 505       continue;
 506     }
 507     if (s.has_in)
 508       die("expecting input to be consumed");
 509     s.in = *p++;
 510     s.has_in = true;
 511   }
 512   if (*p)
 513     die("unconsumed input: %s", p);
 514   printf("begin output stream\n");
 515   while (s.has_out && isascii(s.out)) {
 516     putchar(s.out);
 517     s.has_out = false;
 518     if (run(&s) == -1)
 519       die("no input to provide");
 520   }
 521   if (!s.has_out)
 522     die("expecting output");
 523   printf("collected %" PRId64 " dust\n", s.out);
 524   return 0;
 525 }