2019/day11.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 void
  40 dump(struct state *s) {
  41   if (debug_level < 2)
  42     return;
  43   debug(" state of id=%d: pc=%d base=%d in=%s%" PRId64 " out=%s%" PRId64
  44         " steps=%d\n", s->id, s->pc, s->base,
  45         s->has_in ? "" : "!", s->in, s->has_out ? "" : "!", s->out, s->steps);
  46   for (int i = 0; i < len; i++)
  47     debug_raw(3, "%" PRId64 ",", s->a[i]);
  48   debug_raw(3, "\n");
  49 }
  50
  51 static void __attribute__((noreturn))
  52 crash(struct state *s, const char *msg) {
  53   printf("invalid program id=%d, pc=%d: %s\n", s->id, s->pc, msg);
  54   exit(1);
  55 }
  56
  57 static int64_t
  58 get(struct state *s, int param) {
  59   int64_t op = s->a[s->pc];
  60   int scale = 10;
  61   int mode;
  62   int64_t value;
  63
  64   if (op > 99999 || op < 0)
  65     crash(s, "unexpected opcode");
  66   if (s->pc + param > LIMIT)
  67     crash(s, "memory too short for opcode");
  68   value = s->a[s->pc + param];
  69   while (param--)
  70     scale *= 10;
  71   mode = (op / scale) % 10;
  72   debug_raw(3, "get op=%d mode=%d value=%d\n", op, mode, value);
  73   switch (mode) {
  74   case 0:
  75     if (value > LIMIT || value < 0)
  76       crash(s, "in position mode, param beyond memory");
  77     return s->a[value];
  78   case 1:
  79     return value;
  80   case 2:
  81     value += s->base;
  82     if (value > LIMIT || value < 0)
  83       crash(s, "in relative mode, param beyond memory");
  84     return s->a[value];
  85   default:
  86     crash(s, "unexpected mode");
  87   }
  88 }
  89
  90 static void
  91 put(struct state *s, int param, int64_t value) {
  92   int64_t op = s->a[s->pc];
  93   int scale = 10;
  94   int mode;
  95   int64_t offset;
  96
  97   if (op > 99999 || op < 0)
  98     crash(s, "unexpected opcode");
  99   if (s->pc + param > LIMIT)
 100     crash(s, "memory too short for opcode");
 101   offset = s->a[s->pc + param];
 102   while (param--)
 103     scale *= 10;
 104   mode = (op / scale) % 10;
 105   debug_raw(3, "put op=%d mode=%d value=%d offset=%d\n", op, mode, value, offset);
 106   switch (mode) {
 107   case 0:
 108     if (offset > LIMIT || offset < 0)
 109       crash(s, "in position mode, param beyond memory");
 110     s->a[offset] = value;
 111     return;
 112   case 2:
 113     offset += s->base;
 114     if (offset > LIMIT || offset < 0)
 115       crash(s, "in relative mode, param beyond memory");
 116     s->a[offset] = value;
 117     return;
 118   default:
 119     crash(s, "unexpected mode");
 120   }
 121 }
 122
 123 static void
 124 init(struct state *s, int64_t in) {
 125   memset(s, 0, sizeof  *s);
 126   memcpy(s->a, orig, len * sizeof orig[0]);
 127   s->has_in = true;
 128   s->in = in;
 129   dump(s);
 130 }
 131
 132 static int
 133 run(struct state *s) {
 134   int jump;
 135
 136   while (1) {
 137     debug_raw(2, "executing id=%d step=%d pc=%d base=%" PRId64 " %" PRId64
 138               ",%" PRId64 ",%" PRId64 ",%" PRId64 "\n", s->id,
 139               s->steps++, s->pc, s->base, s->a[s->pc], s->a[s->pc+1],
 140               s->a[s->pc+2], s->a[s->pc+3]);
 141     if (!(s->steps % 10000))
 142       debug(" steps=%d\n", s->steps);
 143     if (s->pc > LIMIT || s->pc < 0)
 144       crash(s, "program ran out of bounds");
 145     switch (s->a[s->pc] % 100) {
 146     case 1:
 147       put(s, 3, get(s, 1) + get(s, 2));
 148       jump = 4;
 149       break;
 150     case 2:
 151       put(s, 3, get(s, 1) * get(s, 2));
 152       jump = 4;
 153       break;
 154     case 3:
 155       if (!s->has_in) {
 156         debug_raw(2, "id=%d stalling for input\n", s->id);
 157         s->steps--;
 158         return -1;
 159       }
 160       put(s, 1, s->in);
 161       s->has_in = false;
 162       jump = 2;
 163       break;
 164     case 4:
 165       if (s->has_out) {
 166         debug_raw(2, "id=%d stalling for output\n", s->id);
 167         s->steps--;
 168         return -1;
 169       }
 170       s->has_out = true;
 171       s->out = get(s, 1);
 172       jump = 2;
 173       break;
 174     case 5:
 175       if (get(s, 1)) {
 176         s->pc = get(s, 2);
 177         jump = 0;
 178       } else
 179         jump = 3;
 180       break;
 181     case 6:
 182       if (!get(s, 1)) {
 183         s->pc = get(s, 2);
 184         jump = 0;
 185       } else
 186         jump = 3;
 187       break;
 188     case 7:
 189       put(s, 3, get(s, 1) < get(s, 2));
 190       jump = 4;
 191       break;
 192     case 8:
 193       put(s, 3, get(s, 1) == get(s, 2));
 194       jump = 4;
 195       break;
 196     case 9:
 197       s->base += get(s, 1);
 198       if (s->base < 0 || s->base > LIMIT)
 199         crash(s, "relative base out of bounds");
 200       jump = 2;
 201       break;
 202     case 99:
 203       debug_raw(2, "id=%d halting\n", s->id);
 204       return 0;
 205     default:
 206       crash(s, "unexpected opcode");
 207     }
 208     s->pc += jump;
 209     dump(s);
 210   }
 211 }
 212
 213 #define GRID 100
 214 static uint8_t grid[GRID][GRID];
 215 enum dir { U, R, D, L };
 216
 217 static struct state s;
 218
 219 static void
 220 display(int pairs, int minx, int maxx, int miny, int maxy) {
 221   int i, j;
 222   fprintf(stderr, " pair %d\n", pairs);
 223   for (j = miny - 3; j < maxy + 3; j++) {
 224     for (i = minx - 3; i < maxx + 3; i++)
 225       putc(" #-"[grid[j][i]], stderr);
 226     putc('\n', stderr);
 227   }
 228 }
 229
 230 int
 231 main(int argc, char **argv) {
 232   int i;
 233   int pairs = 0, count = 0;
 234   int x, y, minx, maxx, miny, maxy;
 235   enum dir dir = U;
 236
 237   debug("");
 238   if (argc > 1)
 239     if (!(stdin = freopen(argv[1], "r", stdin))) {
 240       perror("failure");
 241       exit(2);
 242     }
 243
 244   while (scanf("%" SCNd64 "%*[,\n]", &orig[len]) == 1)
 245     if (len++ > LIMIT - 3) {
 246       printf("recompile with larger LIMIT\n");
 247       exit(2);
 248     }
 249   printf("Read %u slots\n", len);
 250
 251   for (i = 0; i < 2; i++) {
 252     init(&s, i);
 253     memset(grid, 2, sizeof grid);
 254     dir = U;
 255     x = GRID / 2;
 256     y = GRID / 2;
 257     minx = maxx = x;
 258     miny = maxy = y;
 259     while (1) {
 260       if (debug_level)
 261         display(pairs, minx, maxx, miny, maxy);
 262       pairs++;
 263       if (!s.has_in)
 264         crash(&s, "no input prepped");
 265       debug("pair %d, supplying %d\n", pairs, s.in);
 266       if (run(&s) == 0)
 267         crash(&s, "unexpected completion");
 268       if (s.has_in)
 269         crash(&s, "input not consumed");
 270       if (!s.has_out)
 271         crash(&s, "missing expected output");
 272       if (s.out & ~1)
 273         crash(&s, "unexpected output");
 274       debug("painting %d,%d as %d at pc=%d\n", x, y, s.out, s.pc);
 275       if (grid[y][x] == 2)
 276         count++;
 277       grid[y][x] = s.out;
 278       s.has_out = false;
 279       if (run(&s) == 0)
 280         break;
 281       if (!s.has_out)
 282         crash(&s, "missing expected output");
 283       if (s.out & ~1)
 284         crash(&s, "unexpected output");
 285       if (s.out)
 286         dir++;
 287       else
 288         dir--;
 289       dir %= 4;
 290       switch (dir) {
 291       case U: y--; if (y < miny) miny = y; break;
 292       case R: x++; if (x > maxx) maxx = x; break;
 293       case D: y++; if (y > maxy) maxy = y; break;
 294       case L: x--; if (x < minx) minx = x; break;
 295       }
 296       debug("moving %d to %d,%d facing %c\n", s.out, x, y, "URDL"[dir]);
 297       if (minx < 0 || maxx >= GRID || miny < 0 || maxy >= GRID)
 298         crash(&s, "recompile with larger grid");
 299       s.has_out = false;
 300       s.has_in = true;
 301       s.in = grid[y][x] == 1;
 302     }
 303     display(pairs, minx, maxx, miny, maxy);
 304     printf("%d-%d %d-%d\n", minx, maxx, miny, maxy);
 305     printf("program completed: %d pairs parsed, %d painted\n", pairs, count);
 306   }
 307   return 0;
 308 }