2018/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 <inttypes.h>
   8 #include <assert.h>
   9
  10 bool __attribute__((format(printf, 1, 2)))
  11 debug(const char *fmt, ...) {
  12   va_list ap;
  13   if (getenv("DEBUG")) {
  14     va_start(ap, fmt);
  15     vfprintf(stderr, fmt, ap);
  16     va_end(ap);
  17     return true;
  18   }
  19   return false;
  20 }
  21
  22 static int64_t regs[6];
  23 static uint8_t ip;
  24 typedef struct op {
  25   char op;
  26   int a;
  27   int b;
  28   int c;
  29   int visited;
  30 } op;
  31 static op *program;
  32 static unsigned int max;
  33
  34 static int lookup(const char *opcode) {
  35   switch (*opcode) {
  36   case 'a':
  37     return opcode[3] == 'i';
  38   case 'm':
  39     return 2 + (opcode[3] == 'i');
  40   case 'b':
  41     return 4 + 2 * (opcode[1] == 'o') + (opcode[3] == 'i');
  42   case 's':
  43     return 8 + (opcode[3] == 'i');
  44   case 'g':
  45     return 10 + (opcode[2] == 'r') + (opcode[3] == opcode[2]);
  46   case 'e':
  47     return 13 + (opcode[2] == 'r') + (opcode[3] == opcode[2]);
  48   }
  49   fprintf(stderr, "failed decoding instruction %s\n", opcode);
  50   exit(1);
  51 }
  52
  53 static int64_t get(int r) {
  54   assert(0 <= r && r < sizeof regs / sizeof *regs);
  55   return regs[r];
  56 }
  57
  58 static void set(int r, int64_t v) {
  59   assert(0 <= r && r < sizeof regs / sizeof *regs);
  60   regs[r] = v;
  61   assert(v >= 0 || !"resize regs to be larger type");
  62 }
  63
  64 static const char *step(int op, int a, int b, int c) {
  65   switch (op) {
  66   case 0:
  67     set(c, get(a) + get(b)); return "addr";
  68   case 1:
  69     set(c, get(a) + b); return "addi";
  70   case 2:
  71     set(c, get(a) * get(b)); return "mulr";
  72   case 3:
  73     set(c, get(a) * b); return "muli";
  74   case 4:
  75     set(c, get(a) & get(b)); return "banr";
  76   case 5:
  77     set(c, get(a) & b); return "bani";
  78   case 6:
  79     set(c, get(a) | get(b)); return "borr";
  80   case 7:
  81     set(c, get(a) | b); return "bori";
  82   case 8:
  83     set(c, get(a)); return "setr";
  84   case 9:
  85     set(c, a); return "seti";
  86   case 10:
  87     set(c, a > get(b)); return "gtir";
  88   case 11:
  89     set(c, get(a) > b); return "gtri";
  90   case 12:
  91     set(c, get(a) > get(b)); return "gtrr";
  92   case 13:
  93     set(c, a == get(b)); return "eqir";
  94   case 14:
  95     set(c, get(a) == b); return "eqri";
  96   case 15:
  97     set(c, get(a) == get(b)); return "eqrr";
  98   default:
  99     return NULL;
 100   }
 101 }
 102
 103 static uint32_t shuffle(uint32_t in) {
 104   int r1 = 1;
 105   int r2 = 1;
 106   int r3 = in >> 24;
 107   int r4 = in & 0xffffff;
 108
 109   r3 = r4 | 65536; // bori 4 65536 3
 110   r4 = 4332021; // seti 4332021 4 4
 111  l7:
 112   r2 = r3 & 255; // bani 3 255 2
 113   r4 += r2; // addr 4 2 4
 114   r4 &= 16777215; // bani 4 16777215 4
 115   r4 *= 65899; // muli 4 65899 4
 116   r4 &= 16777215; // bani 4 16777215 4
 117   r2 = 256 > r3; // gtir 256 3 2
 118   if (r2) // addr 2 5 5; addi 5 1 5
 119     goto l27; // seti 27 5 5
 120   r2 = 0; // seti 0 2 2
 121  l17:
 122   r1 = r2 + 1; // addi 2 1 1
 123   r1 *= 256; // muli 1 256 1
 124   r1 = r1 > r3; // gtrr 1 3 1
 125   if (r1) // addr 1 5 5; addi 5 1 5
 126     goto l25; // seti 25 2 5
 127   r2++; // addi 2 1 2
 128   goto l17; // seti 17 3 5
 129  l25:
 130   r3 = r2; // setr 2 7 3
 131   goto l7; // seti 7 1 5
 132  l27:
 133   assert((r3 & 0xff) == r3 && (r4 & 0xffffff) == r4);
 134   return (r3 << 24) | r4;
 135 }
 136
 137 int main(int argc, char **argv) {
 138   size_t len = 0, count = 0;
 139   char *line;
 140   op *o;
 141   uint32_t limit = 100000;
 142
 143   /* Part 1 - read in entire program */
 144   if (argc > 3)
 145     limit = atoll(argv[3]);
 146   if (argc > 2)
 147     regs[0] = atoi(argv[2]);
 148   if (argc > 1 && !(stdin = freopen(argv[1], "r", stdin))) {
 149     perror("failure");
 150     exit(2);
 151   }
 152
 153   if (getline(&line, &len, stdin) < 0 ||
 154       sscanf(line, "#ip %hhu\n", &ip) != 1) {
 155     fprintf(stderr, "missing #ip line\n");
 156     exit(1);
 157   }
 158   while (getline(&line, &len, stdin) > 0) {
 159     program = reallocarray(program, ++count, sizeof *program);
 160     o = &program[count - 1];
 161     o->op = lookup(line);
 162     if (sscanf(line + 5, "%d %d %d\n", &o->a, &o->b, &o->c) != 3) {
 163       fprintf(stderr, "corrupt program\n");
 164       exit(1);
 165     }
 166     o->visited = 0;
 167   }
 168   printf("program has %u instructions\n", max = count);
 169
 170   /* Part 2 - run it */
 171   count = 0;
 172   bool d = false;
 173   while (regs[ip] < max && count < limit) {
 174     d = regs[ip] == 28;
 175     const char *s;
 176     if (!(count % 1000000))
 177       printf("%8zu...\n", count);
 178     if (d)
 179       debug("%5zu: ip=%"PRId64" [%"PRIx64", %"PRIx64", %"PRIx64", %"PRIx64
 180             ", %"PRIx64", %"PRIx64"] ", count, regs[ip], regs[0],
 181             regs[1], regs[2], regs[3], regs[4], regs[5]);
 182     count++;
 183     o = &program[regs[ip]];
 184     s = step(o->op, o->a, o->b, o->c);
 185     if (d)
 186       debug("%s %d %d %d ", s, o->a, o->b, o->c);
 187     o->visited++;
 188     if (d)
 189       debug("[%"PRIx64", %"PRIx64", %"PRIx64", %"PRIx64", %"PRIx64", %"PRIx64
 190             "] (%d)\n", regs[0], regs[1], regs[2],
 191             regs[3], regs[4], regs[5], o->visited);
 192     regs[ip]++;
 193   }
 194   printf("%s execution after %zu steps\n",
 195          regs[ip] < max ? "gave up" : "completed", count);
 196   for (int i = 0; 0 && i < max; i++) {
 197     o = &program[i];
 198     if (!debug("program line %s %d %d %d executed %d times\n",
 199                step(o->op, 0, 0, 0), o->a, o->b, o->c, o->visited))
 200       break;
 201   }
 202
 203   /* Part 3: look for cycle with hand-rolled retype of program for speed */
 204   uint32_t slow, fast;
 205   uint32_t prev;
 206   count = 0;
 207   slow = fast = 0x0191f7da;
 208   do {
 209     count++;
 210     slow = shuffle(slow);
 211     prev = shuffle(fast);
 212     fast = shuffle(prev);
 213     if (count < 10 || count > 6300)
 214       debug(" %08zu: %08x %08x %08x\n", count, slow, prev, fast);
 215   } while ((slow & 0xffffff) != (fast & 0xffffff));
 216   printf("found loop after %zu cycles, now finding last integer in loop\n",
 217          count);
 218   slow = 0x0191f7da;
 219   count = 0;
 220   while ((slow & 0xffffff) != (fast & 0xffffff)) {
 221     count++;
 222     prev = fast;
 223     slow = shuffle(slow);
 224     fast = shuffle(fast);
 225     if (count > 4390)
 226       debug(" %08zu: %08x %08x %08x\n", count, slow, prev, fast);
 227   }
 228   printf("repeat state after %zu cycles, previous state %d\n",
 229          count, prev & 0xffffff);
 230   printf("checking: %x %x %x\n", prev, shuffle(prev), slow);
 231   return 0;
 232 }