2018/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 <inttypes.h>
   8 #include <assert.h>
   9
  10 void debug(const char *fmt, ...) {
  11   va_list ap;
  12   if (getenv("DEBUG")) {
  13     va_start(ap, fmt);
  14     vfprintf(stderr, fmt, ap);
  15     va_end(ap);
  16   }
  17 }
  18
  19 static int regs[6];
  20 static uint8_t ip;
  21 typedef struct op {
  22   char op;
  23   int a;
  24   int b;
  25   int c;
  26   int visited;
  27 } op;
  28 static op *program;
  29 static unsigned int max;
  30
  31 static int lookup(const char *opcode) {
  32   switch (*opcode) {
  33   case 'a':
  34     return opcode[3] == 'i';
  35   case 'm':
  36     return 2 + (opcode[3] == 'i');
  37   case 'b':
  38     return 4 + 2 * (opcode[1] == 'o') + (opcode[3] == 'i');
  39   case 's':
  40     return 8 + (opcode[3] == 'i');
  41   case 'g':
  42     return 10 + (opcode[2] == 'r') + (opcode[3] == opcode[2]);
  43   case 'e':
  44     return 13 + (opcode[2] == 'r') + (opcode[3] == opcode[2]);
  45   }
  46   fprintf(stderr, "failed decoding instruction %s\n", opcode);
  47   exit(1);
  48 }
  49
  50 static int get(int r) {
  51   assert(0 <= r && r < sizeof regs / sizeof *regs);
  52   return regs[r];
  53 }
  54
  55 static void set(int r, int v) {
  56   assert(0 <= r && r < sizeof regs / sizeof *regs);
  57   regs[r] = v;
  58   assert(v >= 0 || !"resize regs to be larger type");
  59 }
  60
  61 static const char *step(int op, int a, int b, int c) {
  62   switch (op) {
  63   case 0:
  64     set(c, get(a) + get(b)); return "addr";
  65   case 1:
  66     set(c, get(a) + b); return "addi";
  67   case 2:
  68     set(c, get(a) * get(b)); return "mulr";
  69   case 3:
  70     set(c, get(a) * b); return "muli";
  71   case 4:
  72     set(c, get(a) & get(b)); return "banr";
  73   case 5:
  74     set(c, get(a) & b); return "bani";
  75   case 6:
  76     set(c, get(a) | get(b)); return "borr";
  77   case 7:
  78     set(c, get(a) | b); return "bori";
  79   case 8:
  80     set(c, get(a)); return "setr";
  81   case 9:
  82     set(c, a); return "seti";
  83   case 10:
  84     set(c, a > get(b)); return "gtir";
  85   case 11:
  86     set(c, get(a) > b); return "gtri";
  87   case 12:
  88     set(c, get(a) > get(b)); return "gtrr";
  89   case 13:
  90     set(c, a == get(b)); return "eqir";
  91   case 14:
  92     set(c, get(a) == b); return "eqri";
  93   case 15:
  94     set(c, get(a) == get(b)); return "eqrr";
  95   default:
  96     return NULL;
  97   }
  98 }
  99
 100 int main(int argc, char **argv) {
 101   size_t len = 0, count = 0;
 102   char *line;
 103   op *o;
 104
 105   /* Part 1 - read in entire program */
 106   if (argc > 2)
 107     regs[0] = atoi(argv[2]);
 108   if (argc > 1 && !(stdin = freopen(argv[1], "r", stdin))) {
 109     perror("failure");
 110     exit(2);
 111   }
 112
 113   if (getline(&line, &len, stdin) < 0 ||
 114       sscanf(line, "#ip %hhu\n", &ip) != 1) {
 115     fprintf(stderr, "missing #ip line\n");
 116     exit(1);
 117   }
 118   while (getline(&line, &len, stdin) > 0) {
 119     program = reallocarray(program, ++count, sizeof *program);
 120     o = &program[count - 1];
 121     o->op = lookup(line);
 122     if (sscanf(line + 5, "%d %d %d\n", &o->a, &o->b, &o->c) != 3) {
 123       fprintf(stderr, "corrupt program\n");
 124       exit(1);
 125     }
 126     o->visited = 0;
 127   }
 128   printf("program has %u instructions\n", max = count);
 129
 130   /* Part 2 - run it */
 131   count = 0;
 132   while (regs[ip] < max) {
 133     bool d = regs[ip] == 7;
 134     const char *s;
 135     if (!(count % 1000000))
 136       printf("%8zu...\n", count);
 137     if (d)
 138     debug("%5d: ip=%d [%d, %d, %d, %d, %d, %d] ", count, regs[ip], regs[0],
 139           regs[1], regs[2], regs[3], regs[4], regs[5]);
 140     count++;
 141     o = &program[regs[ip]];
 142     s = step(o->op, o->a, o->b, o->c);
 143     if (d)
 144     debug("%s %d %d %d ", s, o->a, o->b, o->c);
 145     o->visited++;
 146     if (d)
 147     debug("[%d, %d, %d, %d, %d, %d] (%d)\n", regs[0], regs[1], regs[2],
 148           regs[3], regs[4], regs[5], o->visited);
 149     regs[ip]++;
 150   }
 151   printf("completed execution after %zu steps, reg 0 contains %d, 5 is %d\n",
 152          count, regs[0], regs[5]);
 153   for (int i = 0; i < max; i++) {
 154     o = &program[i];
 155     printf("program line %s %d %d %d executed %d times\n",
 156            step(o->op, 0, 0, 0), o->a, o->b, o->c, o->visited);
 157   }
 158   return 0;
 159 }