2019/day25.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 static struct state s;
  56
  57 static void
  58 dump(struct state *s) {
  59   if (debug_level < 2)
  60     return;
  61   debug(" state of id=%d: pc=%d base=%d in=%s%" PRId64 " out=%s%" PRId64
  62         " steps=%d\n", s->id, s->pc, s->base,
  63         s->has_in ? "" : "!", s->in, s->has_out ? "" : "!", s->out, s->steps);
  64   for (int i = 0; i < len; i++)
  65     debug_raw(3, "%" PRId64 ",", s->a[i]);
  66   debug_raw(3, "\n");
  67 }
  68
  69 static void __attribute__((noreturn))
  70 crash(struct state *s, const char *msg) {
  71   printf("invalid program id=%d, pc=%d: %s\n", s->id, s->pc, msg);
  72   exit(1);
  73 }
  74
  75 static int64_t
  76 get(struct state *s, int param) {
  77   int64_t op = s->a[s->pc];
  78   int scale = 10;
  79   int mode;
  80   int64_t value;
  81
  82   if (op > 99999 || op < 0)
  83     crash(s, "unexpected opcode");
  84   if (s->pc + param > LIMIT)
  85     crash(s, "memory too short for opcode");
  86   value = s->a[s->pc + param];
  87   while (param--)
  88     scale *= 10;
  89   mode = (op / scale) % 10;
  90   debug_raw(3, "get op=%" PRId64 " mode=%d value=%" PRId64 "\n",
  91             op, mode, value);
  92   switch (mode) {
  93   case 0:
  94     if (value > LIMIT || value < 0)
  95       crash(s, "in position mode, param beyond memory");
  96     return s->a[value];
  97   case 1:
  98     return value;
  99   case 2:
 100     value += s->base;
 101     if (value > LIMIT || value < 0)
 102       crash(s, "in relative mode, param beyond memory");
 103     return s->a[value];
 104   default:
 105     crash(s, "unexpected mode");
 106   }
 107 }
 108
 109 static void
 110 put(struct state *s, int param, int64_t value) {
 111   int64_t op = s->a[s->pc];
 112   int scale = 10;
 113   int mode;
 114   int64_t offset;
 115
 116   if (op > 99999 || op < 0)
 117     crash(s, "unexpected opcode");
 118   if (s->pc + param > LIMIT)
 119     crash(s, "memory too short for opcode");
 120   offset = s->a[s->pc + param];
 121   while (param--)
 122     scale *= 10;
 123   mode = (op / scale) % 10;
 124   debug_raw(3, "put op=%" PRId64 " mode=%d value=%" PRId64 " offset=%" PRId64
 125             "\n", op, mode, value, offset);
 126   switch (mode) {
 127   case 0:
 128     if (offset > LIMIT || offset < 0)
 129       crash(s, "in position mode, param beyond memory");
 130     s->a[offset] = value;
 131     return;
 132   case 2:
 133     offset += s->base;
 134     if (offset > LIMIT || offset < 0)
 135       crash(s, "in relative mode, param beyond memory");
 136     s->a[offset] = value;
 137     return;
 138   default:
 139     crash(s, "unexpected mode");
 140   }
 141 }
 142
 143 static void
 144 init(struct state *s, int64_t in) {
 145   memset(s, 0, sizeof  *s);
 146   memcpy(s->a, orig, len * sizeof orig[0]);
 147   s->has_in = true;
 148   s->in = in;
 149   dump(s);
 150 }
 151
 152 /* Returns -1 for stalled on input, 0 for done, 1 for stalled on output */
 153 static int
 154 run(struct state *s) {
 155   int jump;
 156
 157   while (1) {
 158     debug_raw(2, "executing id=%d step=%d pc=%d base=%d %" PRId64
 159               ",%" PRId64 ",%" PRId64 ",%" PRId64 "\n", s->id,
 160               s->steps++, s->pc, s->base, s->a[s->pc], s->a[s->pc+1],
 161               s->a[s->pc+2], s->a[s->pc+3]);
 162     if (!(s->steps % 10000))
 163       debug(" steps=%d\n", s->steps);
 164     if (s->pc > LIMIT || s->pc < 0)
 165       crash(s, "program ran out of bounds");
 166     switch (s->a[s->pc] % 100) {
 167     case 1:
 168       put(s, 3, get(s, 1) + get(s, 2));
 169       jump = 4;
 170       break;
 171     case 2:
 172       put(s, 3, get(s, 1) * get(s, 2));
 173       jump = 4;
 174       break;
 175     case 3:
 176       if (!s->has_in) {
 177         debug_raw(2, "id=%d stalling for input\n", s->id);
 178         s->steps--;
 179         return -1;
 180       }
 181       put(s, 1, s->in);
 182       s->has_in = false;
 183       jump = 2;
 184       break;
 185     case 4:
 186       if (s->has_out) {
 187         debug_raw(2, "id=%d stalling for output\n", s->id);
 188         s->steps--;
 189         return 1;
 190       }
 191       s->has_out = true;
 192       s->out = get(s, 1);
 193       jump = 2;
 194       break;
 195     case 5:
 196       if (get(s, 1)) {
 197         s->pc = get(s, 2);
 198         jump = 0;
 199       } else
 200         jump = 3;
 201       break;
 202     case 6:
 203       if (!get(s, 1)) {
 204         s->pc = get(s, 2);
 205         jump = 0;
 206       } else
 207         jump = 3;
 208       break;
 209     case 7:
 210       put(s, 3, get(s, 1) < get(s, 2));
 211       jump = 4;
 212       break;
 213     case 8:
 214       put(s, 3, get(s, 1) == get(s, 2));
 215       jump = 4;
 216       break;
 217     case 9:
 218       s->base += get(s, 1);
 219       if (s->base < 0 || s->base > LIMIT)
 220         crash(s, "relative base out of bounds");
 221       jump = 2;
 222       break;
 223     case 99:
 224       debug_raw(2, "id=%d halting\n", s->id);
 225       return 0;
 226     default:
 227       crash(s, "unexpected opcode");
 228     }
 229     s->pc += jump;
 230     dump(s);
 231   }
 232 }
 233
 234 static const char *
 235 setup(int i) {
 236   static char buf[20 * 9];
 237   char *p = buf;
 238   const char *items[] = { "jam", "loom", "mug", "spool of cat6",
 239                           "prime number", "food ration", "fuel cell",
 240                           "manifold" };
 241   int j;
 242
 243   for (j = 0; j < 8; j++) {
 244     if (i & (1 << j))
 245       p = stpcpy(p, "take ");
 246     else
 247       p = stpcpy(p, "drop ");
 248     p = stpcpy(p, items[j]);
 249     *p++ = '\n';
 250   }
 251   p = stpcpy(p, "north\n");
 252   return buf;
 253 }
 254
 255 int
 256 main(int argc, char **argv) {
 257   FILE *f;
 258   bool output = false, seen_bang = false;
 259   int i = 0;
 260   const char *p = "", prep[] =
 261     "north\n"
 262     "north\n"
 263     "west\n"
 264     "take mug\n"
 265     "east\n"
 266     "north\n"
 267     "east\n"
 268     "east\n"
 269     "take loom\n"
 270     "west\n"
 271     "west\n"
 272     "south\n"
 273     "south\n"
 274     "south\n"
 275     "east\n"
 276     "take food ration\n"
 277     "south\n"
 278     "take prime number\n"
 279     "north\n"
 280     "east\n"
 281     "take manifold\n"
 282     "east\n"
 283     "east\n"
 284     "take jam\n"
 285     "west\n"
 286     "north\n"
 287     "east\n"
 288     "take spool of cat6\n"
 289     "west\n"
 290     "north\n"
 291     "take fuel cell\n"
 292     "south\n"
 293     "south\n"
 294     "west\n"
 295     "west\n"
 296     "west\n"
 297     "north\n"
 298     "west\n"
 299     "north\n"
 300     "west\n"
 301     "north\n"
 302     "inv\n";
 303
 304   debug_init();
 305   if (argc > 1 && strcmp("-", argv[1]))
 306     if (!(stdin = freopen(argv[1], "r", stdin))) {
 307       perror("failure");
 308       exit(2);
 309     }
 310
 311   while (scanf("%" SCNd64 "%*[,\n]", &orig[len]) == 1)
 312     if (len++ > LIMIT - 3)
 313       die("recompile with larger LIMIT");
 314   printf("Read %u slots\n", len);
 315   f = fopen("/dev/tty", "r");
 316   if (!f)
 317     die("failed to open tty");
 318   if (argc <= 2)
 319     p = prep;
 320
 321   init(&s, 0);
 322   s.has_in = false;
 323   while (run(&s) && !feof(f)) {
 324     if (s.has_out) {
 325       if (isascii(s.out)) {
 326         if (output)
 327           putchar(s.out);
 328         if (s.out == '!') {
 329           seen_bang = true;
 330           debug("seen bang\n");
 331         }
 332       } else
 333         die("unexpected output %" PRId64, s.out);
 334       s.has_out = false;
 335       continue;
 336     }
 337     if (s.has_in)
 338       die("expecting input to be consumed");
 339     if (*p)
 340       s.in = *p++;
 341     else {
 342       output = true;
 343       if (seen_bang && i <= 256) {
 344         p = setup(i++);
 345         debug("trying: %s\n", p);
 346         s.in = *p++;
 347         seen_bang = false;
 348       } else
 349         s.in = fgetc(f);
 350     }
 351     s.has_in = true;
 352   }
 353   return 0;
 354 }