2019/day21.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 static int64_t
 236 try(const char *in, int iter) {
 237   const char *p = in;
 238
 239   debug(" input for iter %d will be:\n%s", iter, in);
 240   init(&s, 0);
 241   s.has_in = false;
 242   while (run(&s) && *p) {
 243     if (s.has_out) {
 244       if (isascii(s.out))
 245         debug("read '%c'\n", (char)s.out);
 246       else
 247         die("unexpected output %" PRId64, s.out);
 248       s.has_out = false;
 249       continue;
 250     }
 251     if (s.has_in)
 252       die("expecting input to be consumed");
 253     s.in = *p++;
 254     s.has_in = true;
 255   }
 256   if (*p)
 257     die("unconsumed input: %s", p);
 258   debug(" output stream:\n");
 259   while (s.has_out && isascii(s.out)) {
 260     debug("%c", (char) s.out);
 261     s.has_out = false;
 262     if (run(&s) == -1)
 263       die("no input to provide");
 264   }
 265   if (!s.has_out)
 266     die("expecting output");
 267   return s.out;
 268 }
 269
 270 int
 271 main(int argc, char **argv) {
 272   int64_t r;
 273
 274   debug_init();
 275   if (argc > 1 && strcmp("-", argv[1]))
 276     if (!(stdin = freopen(argv[1], "r", stdin))) {
 277       perror("failure");
 278       exit(2);
 279     }
 280
 281   while (scanf("%" SCNd64 "%*[,\n]", &orig[len]) == 1)
 282     if (len++ > LIMIT - 3)
 283       die("recompile with larger LIMIT");
 284   printf("Read %u slots\n", len);
 285
 286   r = try("NOT C J\nAND D J\nNOT A T\nOR T J\nWALK\n", 0);
 287   if (isascii(r))
 288     die("failed execution");
 289   printf("walking detected %" PRId64 " damage\n", r);
 290
 291   r = try("NOT F J\nOR E J\nOR H J\nAND D J\nNOT C T\nAND T J\n"
 292           "NOT D T\nOR B T\nOR E T\nNOT T T\nOR T J\n"
 293           "NOT A T\nOR T J\nRUN\n", 1);
 294   if (isascii(r))
 295     die("failed execution");
 296   printf("running detected %" PRId64 " damage\n", r);
 297   return 0;
 298 }