2019/day15.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
  10 #define LIMIT 10000
  11 static int64_t orig[LIMIT];
  12 static int len;
  13 struct state {
  14   int id;
  15   int64_t a[LIMIT];
  16   int pc;
  17   int base;
  18   bool has_in;
  19   int64_t in;
  20   bool has_out;
  21   int64_t out;
  22   int steps;
  23 };
  24
  25 static int debug_level = -1;
  26 static void
  27 debug_raw(int level, const char *fmt, ...) {
  28   va_list ap;
  29   if (debug_level < 0)
  30     debug_level = atoi(getenv("DEBUG") ?: "0");
  31   if (debug_level >= level) {
  32     va_start(ap, fmt);
  33     vfprintf(stderr, fmt, ap);
  34     va_end(ap);
  35   }
  36 }
  37 #define debug(...) debug_raw(1, __VA_ARGS__)
  38
  39 static int __attribute__((noreturn))
  40 die(const char *fmt, ...)
  41 {
  42   va_list ap;
  43   va_start(ap, fmt);
  44   vprintf(fmt, ap);
  45   va_end(ap);
  46   putchar('\n');
  47   exit(1);
  48 }
  49
  50 static void
  51 dump(struct state *s) {
  52   if (debug_level < 2)
  53     return;
  54   debug(" state of id=%d: pc=%d base=%d in=%s%" PRId64 " out=%s%" PRId64
  55         " steps=%d\n", s->id, s->pc, s->base,
  56         s->has_in ? "" : "!", s->in, s->has_out ? "" : "!", s->out, s->steps);
  57   for (int i = 0; i < len; i++)
  58     debug_raw(3, "%" PRId64 ",", s->a[i]);
  59   debug_raw(3, "\n");
  60 }
  61
  62 static void __attribute__((noreturn))
  63 crash(struct state *s, const char *msg) {
  64   printf("invalid program id=%d, pc=%d: %s\n", s->id, s->pc, msg);
  65   exit(1);
  66 }
  67
  68 static int64_t
  69 get(struct state *s, int param) {
  70   int64_t op = s->a[s->pc];
  71   int scale = 10;
  72   int mode;
  73   int64_t value;
  74
  75   if (op > 99999 || op < 0)
  76     crash(s, "unexpected opcode");
  77   if (s->pc + param > LIMIT)
  78     crash(s, "memory too short for opcode");
  79   value = s->a[s->pc + param];
  80   while (param--)
  81     scale *= 10;
  82   mode = (op / scale) % 10;
  83   debug_raw(3, "get op=%d mode=%d value=%d\n", op, mode, value);
  84   switch (mode) {
  85   case 0:
  86     if (value > LIMIT || value < 0)
  87       crash(s, "in position mode, param beyond memory");
  88     return s->a[value];
  89   case 1:
  90     return value;
  91   case 2:
  92     value += s->base;
  93     if (value > LIMIT || value < 0)
  94       crash(s, "in relative mode, param beyond memory");
  95     return s->a[value];
  96   default:
  97     crash(s, "unexpected mode");
  98   }
  99 }
 100
 101 static void
 102 put(struct state *s, int param, int64_t value) {
 103   int64_t op = s->a[s->pc];
 104   int scale = 10;
 105   int mode;
 106   int64_t offset;
 107
 108   if (op > 99999 || op < 0)
 109     crash(s, "unexpected opcode");
 110   if (s->pc + param > LIMIT)
 111     crash(s, "memory too short for opcode");
 112   offset = s->a[s->pc + param];
 113   while (param--)
 114     scale *= 10;
 115   mode = (op / scale) % 10;
 116   debug_raw(3, "put op=%d mode=%d value=%d offset=%d\n", op, mode, value, offset);
 117   switch (mode) {
 118   case 0:
 119     if (offset > LIMIT || offset < 0)
 120       crash(s, "in position mode, param beyond memory");
 121     s->a[offset] = value;
 122     return;
 123   case 2:
 124     offset += s->base;
 125     if (offset > LIMIT || offset < 0)
 126       crash(s, "in relative mode, param beyond memory");
 127     s->a[offset] = value;
 128     return;
 129   default:
 130     crash(s, "unexpected mode");
 131   }
 132 }
 133
 134 static void
 135 init(struct state *s, int64_t in) {
 136   memset(s, 0, sizeof  *s);
 137   memcpy(s->a, orig, len * sizeof orig[0]);
 138   s->has_in = true;
 139   s->in = in;
 140   dump(s);
 141 }
 142
 143 /* Returns -1 for stalled on input, 0 for done, 1 for stalled on output */
 144 static int
 145 run(struct state *s) {
 146   int jump;
 147
 148   while (1) {
 149     debug_raw(2, "executing id=%d step=%d pc=%d base=%" PRId64 " %" PRId64
 150               ",%" PRId64 ",%" PRId64 ",%" PRId64 "\n", s->id,
 151               s->steps++, s->pc, s->base, s->a[s->pc], s->a[s->pc+1],
 152               s->a[s->pc+2], s->a[s->pc+3]);
 153     if (!(s->steps % 10000))
 154       debug(" steps=%d\n", s->steps);
 155     if (s->pc > LIMIT || s->pc < 0)
 156       crash(s, "program ran out of bounds");
 157     switch (s->a[s->pc] % 100) {
 158     case 1:
 159       put(s, 3, get(s, 1) + get(s, 2));
 160       jump = 4;
 161       break;
 162     case 2:
 163       put(s, 3, get(s, 1) * get(s, 2));
 164       jump = 4;
 165       break;
 166     case 3:
 167       if (!s->has_in) {
 168         debug_raw(2, "id=%d stalling for input\n", s->id);
 169         s->steps--;
 170         return -1;
 171       }
 172       put(s, 1, s->in);
 173       s->has_in = false;
 174       jump = 2;
 175       break;
 176     case 4:
 177       if (s->has_out) {
 178         debug_raw(2, "id=%d stalling for output\n", s->id);
 179         s->steps--;
 180         return 1;
 181       }
 182       s->has_out = true;
 183       s->out = get(s, 1);
 184       jump = 2;
 185       break;
 186     case 5:
 187       if (get(s, 1)) {
 188         s->pc = get(s, 2);
 189         jump = 0;
 190       } else
 191         jump = 3;
 192       break;
 193     case 6:
 194       if (!get(s, 1)) {
 195         s->pc = get(s, 2);
 196         jump = 0;
 197       } else
 198         jump = 3;
 199       break;
 200     case 7:
 201       put(s, 3, get(s, 1) < get(s, 2));
 202       jump = 4;
 203       break;
 204     case 8:
 205       put(s, 3, get(s, 1) == get(s, 2));
 206       jump = 4;
 207       break;
 208     case 9:
 209       s->base += get(s, 1);
 210       if (s->base < 0 || s->base > LIMIT)
 211         crash(s, "relative base out of bounds");
 212       jump = 2;
 213       break;
 214     case 99:
 215       debug_raw(2, "id=%d halting\n", s->id);
 216       return 0;
 217     default:
 218       crash(s, "unexpected opcode");
 219     }
 220     s->pc += jump;
 221     dump(s);
 222   }
 223 }
 224
 225 static struct state s;
 226
 227 #define GRID 50
 228 static int16_t grid[GRID][GRID]; /* -1 unvisited, -2 wall, else distance */
 229 static int minx, maxx, miny, maxy;
 230 enum dir { N = 1, S, W, E };
 231
 232 static void
 233 display(int x1, int y1) {
 234   int x, y;
 235
 236   if (!debug_level)
 237     return;
 238   for (y = miny; y <= maxy; y++) {
 239     for (x = minx; x <= maxx; x++) {
 240       if (x1 == x && y1 == y) {
 241         debug("D");
 242         continue;
 243       }
 244       switch (grid[y][x]) {
 245       case -2: debug("#"); break;
 246       case -1: debug(" "); break;
 247       case 0: debug("_"); break;
 248       default: debug("."); break;
 249       }
 250     }
 251     debug("\n");
 252   }
 253   debug("currently at %d,%d and %d steps away from origin\n",
 254         x1, y1, grid[y1][x1]);
 255 }
 256
 257 int
 258 main(int argc, char **argv) {
 259   int count = 0;
 260   enum dir last = E;
 261   int x, y, nextx, nexty;
 262   int visits = 0;
 263   int part1 = 0, part2 = 0;
 264
 265   debug("");
 266   if (argc > 1)
 267     if (!(stdin = freopen(argv[1], "r", stdin))) {
 268       perror("failure");
 269       exit(2);
 270     }
 271
 272   while (scanf("%" SCNd64 "%*[,\n]", &orig[len]) == 1)
 273     if (len++ > LIMIT - 3)
 274       die("recompile with larger LIMIT");
 275   printf("Read %u slots\n", len);
 276
 277   init(&s, E);
 278   s.has_in = false;
 279   memset(grid, -1, sizeof grid);
 280   minx = maxx = x = miny = maxy = y = GRID / 2;
 281   grid[y][x] = 0;
 282   while (visits < 5) {
 283     count++;
 284     switch (run(&s)) {
 285     case 0:
 286       die("unexpected exit");
 287     case -1:
 288       if (s.has_out)
 289         break;
 290       switch (last) {
 291       case N:
 292         if (grid[y][x - 1] > -2) { s.in = W; break; }
 293         if (grid[y - 1][x] > -2) { s.in = N; break; }
 294         if (grid[y][x + 1] > -2) { s.in = E; break; }
 295         if (grid[y + 1][x] > -2) { s.in = S; break; }
 296         die("no path possible from N");
 297       case E:
 298         if (grid[y - 1][x] > -2) { s.in = N; break; }
 299         if (grid[y][x + 1] > -2) { s.in = E; break; }
 300         if (grid[y + 1][x] > -2) { s.in = S; break; }
 301         if (grid[y][x - 1] > -2) { s.in = W; break; }
 302         die("no path possible from E");
 303       case S:
 304         if (grid[y][x + 1] > -2) { s.in = E; break; }
 305         if (grid[y + 1][x] > -2) { s.in = S; break; }
 306         if (grid[y][x - 1] > -2) { s.in = W; break; }
 307         if (grid[y - 1][x] > -2) { s.in = N; break; }
 308         die("no path possible from S");
 309       case W:
 310         if (grid[y + 1][x] > -2) { s.in = S; break; }
 311         if (grid[y][x - 1] > -2) { s.in = W; break; }
 312         if (grid[y - 1][x] > -2) { s.in = N; break; }
 313         if (grid[y][x + 1] > -2) { s.in = E; break; }
 314         die("no path possible from W");
 315       }
 316       s.has_in = true;
 317       display(x, y);
 318       continue;
 319     }
 320     switch (s.in) {
 321     case N: nextx = x; nexty = y - 1; break;
 322     case S: nextx = x; nexty = y + 1; break;
 323     case W: nextx = x - 1; nexty = y; break;
 324     case E: nextx = x + 1; nexty = y; break;
 325     default: die("invalid input");
 326     }
 327     debug("tried %c, got %" PRId64 "\n", " NSWE"[s.in], s.out);
 328     if (nextx < minx)
 329       minx = nextx;
 330     if (nextx > maxx)
 331       maxx = nextx;
 332     if (nexty < miny)
 333       miny = nexty;
 334     if (nexty > maxy)
 335       maxy = nexty;
 336     if (nextx < 0 || nextx >= GRID || nexty < 0 || nexty >= GRID)
 337       die("recompile with larger GRID");
 338     switch (s.out) {
 339     case 0:
 340       grid[nexty][nextx] = -2;
 341       break;
 342     case 1:
 343       if (grid[nexty][nextx] < 0)
 344         grid[nexty][nextx] = grid[y][x] + 1;
 345       if (grid[nexty][nextx] > part2)
 346         part2 = grid[nexty][nextx];
 347       last = s.in;
 348       x = nextx;
 349       y = nexty;
 350       break;
 351     case 2:
 352       display(nextx, nexty);
 353       if (!visits++) {
 354         printf("found it at %d,%d, distance %d\n", nextx, nexty,
 355                grid[y][x] + 1);
 356         part1 = grid[y][x] + 1;
 357         part2 = 0;
 358         memset(grid, -1, sizeof grid);
 359         grid[nexty][nextx] = 0;
 360       }
 361       last = s.in;
 362       x = nextx;
 363       y = nexty;
 364       break;
 365     default: die("unexpected output");
 366     }
 367     s.has_out = false;
 368   }
 369   printf("%d steps to start, %d minutes to fill\n", part1, part2);
 370   return 0;
 371 }