2019/day13.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 /* Returns -1 for stalled on input, 0 for done, 1 for stalled on output */
 133 static int
 134 run(struct state *s) {
 135   int jump;
 136
 137   while (1) {
 138     debug_raw(2, "executing id=%d step=%d pc=%d base=%" PRId64 " %" PRId64
 139               ",%" PRId64 ",%" PRId64 ",%" PRId64 "\n", s->id,
 140               s->steps++, s->pc, s->base, s->a[s->pc], s->a[s->pc+1],
 141               s->a[s->pc+2], s->a[s->pc+3]);
 142     if (!(s->steps % 10000))
 143       debug(" steps=%d\n", s->steps);
 144     if (s->pc > LIMIT || s->pc < 0)
 145       crash(s, "program ran out of bounds");
 146     switch (s->a[s->pc] % 100) {
 147     case 1:
 148       put(s, 3, get(s, 1) + get(s, 2));
 149       jump = 4;
 150       break;
 151     case 2:
 152       put(s, 3, get(s, 1) * get(s, 2));
 153       jump = 4;
 154       break;
 155     case 3:
 156       if (!s->has_in) {
 157         debug_raw(2, "id=%d stalling for input\n", s->id);
 158         s->steps--;
 159         return -1;
 160       }
 161       put(s, 1, s->in);
 162       s->has_in = false;
 163       jump = 2;
 164       break;
 165     case 4:
 166       if (s->has_out) {
 167         debug_raw(2, "id=%d stalling for output\n", s->id);
 168         s->steps--;
 169         return 1;
 170       }
 171       s->has_out = true;
 172       s->out = get(s, 1);
 173       jump = 2;
 174       break;
 175     case 5:
 176       if (get(s, 1)) {
 177         s->pc = get(s, 2);
 178         jump = 0;
 179       } else
 180         jump = 3;
 181       break;
 182     case 6:
 183       if (!get(s, 1)) {
 184         s->pc = get(s, 2);
 185         jump = 0;
 186       } else
 187         jump = 3;
 188       break;
 189     case 7:
 190       put(s, 3, get(s, 1) < get(s, 2));
 191       jump = 4;
 192       break;
 193     case 8:
 194       put(s, 3, get(s, 1) == get(s, 2));
 195       jump = 4;
 196       break;
 197     case 9:
 198       s->base += get(s, 1);
 199       if (s->base < 0 || s->base > LIMIT)
 200         crash(s, "relative base out of bounds");
 201       jump = 2;
 202       break;
 203     case 99:
 204       debug_raw(2, "id=%d halting\n", s->id);
 205       return 0;
 206     default:
 207       crash(s, "unexpected opcode");
 208     }
 209     s->pc += jump;
 210     dump(s);
 211   }
 212 }
 213
 214 #define GRID 50
 215 enum tile {
 216   EMPTY,
 217   WALL,
 218   BLOCK,
 219   PADDLE,
 220   BALL,
 221 };
 222 static enum tile grid[GRID][GRID];
 223 static int maxx, maxy;
 224 static int score;
 225 static int padx, ballx;
 226
 227 static struct state s;
 228
 229 static void
 230 display(void) {
 231   int x, y;
 232
 233   printf("score %d\n", score);
 234   for (y = 0; y <= maxy; y++) {
 235     for (x = 0; x <= maxx; x++)
 236       putchar(" #x_@"[grid[y][x]]);
 237     putchar('\n');
 238   }
 239 }
 240
 241 int
 242 main(int argc, char **argv) {
 243   int count = 0, blocks = 0;
 244   int begin = 1;
 245   int x, y;
 246   bool done;
 247
 248   debug("");
 249   if (argc > 1)
 250     if (!(stdin = freopen(argv[1], "r", stdin))) {
 251       perror("failure");
 252       exit(2);
 253     }
 254
 255   if (argc > 2)
 256     begin = atoi(argv[2]);
 257
 258   while (scanf("%" SCNd64 "%*[,\n]", &orig[len]) == 1)
 259     if (len++ > LIMIT - 3) {
 260       printf("recompile with larger LIMIT\n");
 261       exit(2);
 262     }
 263   printf("Read %u slots\n", len);
 264
 265   init(&s, 0);
 266   s.a[0] = begin;
 267   s.has_in = false;
 268   while (!done) {
 269     count++;
 270     switch (run(&s)) {
 271     case 0:
 272       crash(&s, "unexpected completion");
 273     case -1:
 274       s.in = (ballx > padx) - (ballx < padx);
 275       s.has_in = true;
 276       printf("tilting joystick %" PRId64 "\n", s.in);
 277       display();
 278       continue;
 279     }
 280     if (s.out < -1 || s.out > GRID)
 281       crash(&s, "recompile with larger GRID");
 282     x = s.out;
 283     s.has_out = false;
 284     if (x > maxx)
 285       maxx = x;
 286
 287     if (run(&s) != 1)
 288       crash(&s, "unexpected completion/input request");
 289     if (!s.has_out)
 290       crash(&s, "missing expected output y");
 291     if (s.out < 0 || s.out > GRID)
 292       crash(&s, "recompile with larger GRID");
 293     y = s.out;
 294     if (x == -1 && y)
 295       crash(&s, "invalid y for displaying score");
 296     s.has_out = false;
 297     if (y > maxy)
 298       maxy = y;
 299
 300     if (run(&s) == 0)
 301       done = true;
 302     if (!s.has_out)
 303       crash(&s, "missing expected output tile");
 304     if (x >= 0) {
 305       if (s.out < EMPTY || s.out > BALL)
 306         crash(&s, "unexpected output tile");
 307       if (s.out == BLOCK && grid[y][x] != BLOCK)
 308         blocks++;
 309       else if (s.out != BLOCK && grid[y][x] == BLOCK) {
 310         debug("hit a block\n");
 311         display();
 312       }
 313       grid[y][x] = s.out;
 314       if (s.out == BALL)
 315         ballx = x;
 316       else if (s.out == PADDLE)
 317         padx = x;
 318       debug("setting %d,%d to '%c'\n", x, y, " #X_@"[s.out]);
 319     } else {
 320       score = s.out;
 321       debug("setting score to %d\n", score);
 322       display();
 323     }
 324     s.has_out = false;
 325   }
 326   display();
 327   printf("program done: %d tuples, %d.%d grid, %d blocks, final score %d\n",
 328          count, maxx, maxy, blocks, score);
 329   return 0;
 330 }