2018/day16.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 #include <endian.h>
  10 #include <math.h>
  11
  12 void debug(const char *fmt, ...) {
  13   va_list ap;
  14   if (getenv("DEBUG")) {
  15     va_start(ap, fmt);
  16     vfprintf(stderr, fmt, ap);
  17     va_end(ap);
  18   }
  19 }
  20
  21 static int16_t regs[4];
  22 static uint16_t possible[16];
  23 static char known[16];
  24
  25 static int get(int r) {
  26   assert(0 <= r && r < sizeof regs / sizeof *regs);
  27   return regs[r];
  28 }
  29
  30 static void set(int r, int v) {
  31   assert(0 <= r && r < sizeof regs / sizeof *regs);
  32   regs[r] = v;
  33   assert(regs[r] == v || !"resize regs to be larger type");
  34 }
  35
  36 static const char *step(int op, int a, int b, int c) {
  37   switch (op) {
  38   case 0:
  39     set(c, get(a) + get(b)); return "addr";
  40   case 1:
  41     set(c, get(a) + b); return "addi";
  42   case 2:
  43     set(c, get(a) * get(b)); return "mulr";
  44   case 3:
  45     set(c, get(a) * b); return "muli";
  46   case 4:
  47     set(c, get(a) & get(b)); return "banr";
  48   case 5:
  49     set(c, get(a) & b); return "bani";
  50   case 6:
  51     set(c, get(a) | get(b)); return "borr";
  52   case 7:
  53     set(c, get(a) | b); return "bori";
  54   case 8:
  55     set(c, get(a)); return "setr";
  56   case 9:
  57     set(c, a); return "seti";
  58   case 10:
  59     set(c, a > get(b)); return "gtir";
  60   case 11:
  61     set(c, get(a) > b); return "gtri";
  62   case 12:
  63     set(c, get(a) > get(b)); return "gtrr";
  64   case 13:
  65     set(c, a == get(b)); return "eqir";
  66   case 14:
  67     set(c, get(a) == b); return "eqri";
  68   case 15:
  69     set(c, get(a) == get(b)); return "eqrr";
  70   default:
  71     return NULL;
  72   }
  73 }
  74
  75 static int try(int b0, int b1, int b2, int b3, int op, int a, int b, int c,
  76                int a0, int a1, int a2, int a3) {
  77   int r = 0;
  78   const char *str = NULL;
  79   debug("Want %d %d %d %d into %d %d %d %d given %d %d %d\n",
  80         b0, b1, b2, b3, a0, a1, a2, a3, a, b, c);
  81   for (int i = 0; i < 16; i++) {
  82     regs[0] = b0;
  83     regs[1] = b1;
  84     regs[2] = b2;
  85     regs[3] = b3;
  86     const char *tmp = step(i, a, b, c);
  87     debug("op %2d converted to %d %d %d %d", i,
  88           regs[0], regs[1], regs[2], regs[3]);
  89     if (regs[0] == a0 && regs[1] == a1 && regs[2] == a2 && regs[3] == a3) {
  90       debug(", matching %s\n", str = tmp);
  91       r++;
  92     } else {
  93       debug("\n");
  94       possible[op] &= ~(1 << i);
  95     }
  96   }
  97   debug("%d possible ops as decode\n", r);
  98   return r;
  99 }
 100
 101 int main(int argc, char **argv) {
 102   size_t len = 0, count = 0;
 103   char *line;
 104   int ret = 0;
 105   int b0, b1, b2, b3;
 106   int a0, a1, a2, a3;
 107   int op, a, b, c;
 108   int i, j;
 109   bool reduced = false;
 110
 111   /* Part 1 - read in samples */
 112   memset(possible, -1, sizeof possible);
 113   memset(known, -1, sizeof known);
 114   if (argc > 1 && !(stdin = freopen(argv[1], "r", stdin))) {
 115     perror("failure");
 116     exit(2);
 117   }
 118
 119   while (1) {
 120     if (getline(&line, &len, stdin) <= 0)
 121       break;
 122     if (sscanf(line, "Before: [%1d, %1d, %1d, %1d]\n",
 123                &b0, &b1, &b2, &b3) != 4)
 124       break;
 125
 126     if (getline(&line, &len, stdin) <= 0)
 127       break;
 128     if (sscanf(line, "%d %d %d %d\n", &op, &a, &b, &c) != 4)
 129       break;
 130
 131     if (getline(&line, &len, stdin) <= 0)
 132       break;
 133     if (sscanf(line, "After:  [%1d, %1d, %1d, %1d]\n",
 134                &a0, &a1, &a2, &a3) != 4)
 135       break;
 136
 137     if (getline(&line, &len, stdin) < 0)
 138       break;
 139
 140     if (try(b0, b1, b2, b3, op, a, b, c, a0, a1, a2, a3) >= 3)
 141       ret++;
 142     count++;
 143   }
 144   printf("%zu stanzas read, found %d states with 3+ opcodes\n", count, ret);
 145
 146   /* Part 2 - decode */
 147   for (i = 0; i < 16; i++)
 148     printf("op %2d could be %04x\n", i, possible[i]);
 149   printf("Reducing possible...\n");
 150   while (!reduced) {
 151     reduced = true;
 152     for (i = 0; i < 16; i++) {
 153       if (known[i] != -1 || (possible[i] & (possible[i] - 1)))
 154         continue;
 155       reduced = false;
 156       known[i] = log2(possible[i]);
 157       printf("op %d is %s\n", i, step(known[i], 0, 0, 0));
 158       for (j = 0; j < 16; j++)
 159         if (i != j)
 160           possible[j] &= ~possible[i & 0xf];
 161     }
 162   }
 163
 164   /* Part 3 - run program */
 165   memset(regs, 0, sizeof regs);
 166   count = 0;
 167   while (1) {
 168     if (getline(&line, &len, stdin) < 0)
 169       break;
 170     if (line[0] == '\n')
 171       continue;
 172     count++;
 173     if (sscanf(line, "%d %d %d %d\n", &op, &a, &b, &c) != 4)
 174       break;
 175     step(known[op], a, b, c);
 176   }
 177   printf("After %zu instructions, reg 0 contains %d\n", count, regs[0]);
 178   return 0;
 179 }