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