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