2019/day9.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 %" PRId64 ",%" PRId64
 138               ",%" PRId64 ",%" PRId64 "\n", s->id,
 139               s->steps++, s->pc, s->a[s->pc], s->a[s->pc+1], s->a[s->pc+2],
 140               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         return -1;
 158       }
 159       put(s, 1, s->in);
 160       s->has_in = false;
 161       jump = 2;
 162       break;
 163     case 4:
 164       if (s->has_out)
 165         printf("program id=%d overwriting output %" PRId64" \n", s->id, s->out);
 166       s->has_out = true;
 167       s->out = get(s, 1);
 168       jump = 2;
 169       break;
 170     case 5:
 171       if (get(s, 1)) {
 172         s->pc = get(s, 2);
 173         jump = 0;
 174       } else
 175         jump = 3;
 176       break;
 177     case 6:
 178       if (!get(s, 1)) {
 179         s->pc = get(s, 2);
 180         jump = 0;
 181       } else
 182         jump = 3;
 183       break;
 184     case 7:
 185       put(s, 3, get(s, 1) < get(s, 2));
 186       jump = 4;
 187       break;
 188     case 8:
 189       put(s, 3, get(s, 1) == get(s, 2));
 190       jump = 4;
 191       break;
 192     case 9:
 193       s->base += get(s, 1);
 194       if (s->base < 0 || s->base > LIMIT)
 195         crash(s, "relative base out of bounds");
 196       jump = 2;
 197       break;
 198     case 99:
 199       debug_raw(2, "id=%d halting\n", s->id);
 200       return 0;
 201     default:
 202       crash(s, "unexpected opcode");
 203     }
 204     s->pc += jump;
 205     dump(s);
 206   }
 207 }
 208
 209 static struct state s;
 210 int
 211 main(int argc, char **argv) {
 212   int i;
 213
 214   debug("");
 215   if (argc > 1)
 216     if (!(stdin = freopen(argv[1], "r", stdin))) {
 217       perror("failure");
 218       exit(2);
 219     }
 220
 221   while (scanf("%" SCNd64 "%*[,\n]", &orig[len]) == 1)
 222     if (len++ > LIMIT - 3) {
 223       printf("recompile with larger LIMIT\n");
 224       exit(2);
 225     }
 226   printf("Read %u slots\n", len);
 227
 228   for (i = 1; i <= 2; i++) {
 229     init(&s, i);
 230     if (run(&s) != 0)
 231       crash(&s, "not enough input");
 232     if (s.has_out)
 233       printf("part %d final output %" PRId64 "\n", i, s.out);
 234     else
 235       printf("part %d no final output\n", i);
 236   }
 237
 238   return 0;
 239 }