2019/day7.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
   8 #define LIMIT 2000
   9 static int orig[LIMIT];
  10 static int len;
  11 struct state {
  12   int id;
  13   int a[LIMIT];
  14   int pc;
  15   bool has_in;
  16   int in;
  17   bool has_out;
  18   int out;
  19   int steps;
  20 };
  21 struct state amps[5];
  22 static int max;
  23
  24 static int debug_level = -1;
  25 static void
  26 debug_raw(int level, const char *fmt, ...) {
  27   va_list ap;
  28   if (debug_level < 0)
  29     debug_level = atoi(getenv("DEBUG") ?: "0");
  30   if (debug_level >= level) {
  31     va_start(ap, fmt);
  32     vfprintf(stderr, fmt, ap);
  33     va_end(ap);
  34   }
  35 }
  36 #define debug(...) debug_raw(1, __VA_ARGS__)
  37
  38 static void
  39 dump(struct state *s) {
  40   if (debug_level < 2)
  41     return;
  42   debug(" state of id=%d: pc=%d in=%s%d out=%s%d steps=%d\n", s->id, s->pc,
  43         s->has_in ? "" : "!", s->in, s->has_out ? "" : "!", s->out, s->steps);
  44   for (int i = 0; i < len; i++)
  45     debug_raw(3, "%d,", s->a[i]);
  46   debug_raw(3, "\n");
  47 }
  48
  49 static void __attribute__((noreturn))
  50 crash(struct state *s, const char *msg) {
  51   printf("invalid program id=%d, pc=%d: %s\n", s->id, s->pc, msg);
  52   exit(1);
  53 }
  54
  55 static int
  56 get(struct state *s, int param) {
  57   int op = s->a[s->pc];
  58   int scale = 10;
  59   int mode;
  60   int value;
  61
  62   if (s->pc + param > len)
  63     crash(s, "program too short for opcode");
  64   value = s->a[s->pc + param];
  65   while (param--)
  66     scale *= 10;
  67   mode = (op / scale) % 10;
  68   debug_raw(3, "get op=%d mode=%d value=%d\n", op, mode, value);
  69   switch (mode) {
  70   case 0:
  71     if (value > len || value < 0)
  72       crash(s, "in position mode, param beyond end of program");
  73     return s->a[value];
  74   case 1:
  75     return value;
  76   default:
  77     crash(s, "unexpected mode");
  78   }
  79 }
  80
  81 static void
  82 put(struct state *s, int param, int value) {
  83   int op = s->a[s->pc];
  84   int scale = 10;
  85   int mode;
  86   int offset;
  87
  88   if (s->pc + param > len)
  89     crash(s, "program too short for opcode");
  90   offset = s->a[s->pc + param];
  91   while (param--)
  92     scale *= 10;
  93   mode = (op / scale) % 10;
  94   debug_raw(3, "put op=%d mode=%d value=%d offset=%d\n", op, mode, value, offset);
  95   switch (mode) {
  96   case 0:
  97     if (offset > len)
  98       crash(s, "in position mode, param beyond end of program");
  99     s->a[offset] = value;
 100     return;
 101   default:
 102     crash(s, "unexpected mode");
 103   }
 104 }
 105
 106 static int
 107 run(struct state *s) {
 108   int jump;
 109
 110   while (1) {
 111     debug_raw(2, "executing id=%d step=%d pc=%d %d,%d,%d,%d\n", s->id,
 112               s->steps++, s->pc, s->a[s->pc], s->a[s->pc+1], s->a[s->pc+2],
 113               s->a[s->pc+3]);
 114     if (s->pc > len || s->pc < 0)
 115       crash(s, "program ran out of bounds");
 116     switch (s->a[s->pc] % 100) {
 117     case 1:
 118       put(s, 3, get(s, 1) + get(s, 2));
 119       jump = 4;
 120       break;
 121     case 2:
 122       put(s, 3, get(s, 1) * get(s, 2));
 123       jump = 4;
 124       break;
 125     case 3:
 126       if (!s->has_in) {
 127         debug_raw(2, "id=%d stalling for input\n", s->id);
 128         return -1;
 129       }
 130       put(s, 1, s->in);
 131       s->has_in = false;
 132       jump = 2;
 133       break;
 134     case 4:
 135       if (s->has_out)
 136         printf("program id=%d overwriting output %d\n", s->id, s->out);
 137       s->has_out = true;
 138       s->out = get(s, 1);
 139       jump = 2;
 140       break;
 141     case 5:
 142       if (get(s, 1)) {
 143         s->pc = get(s, 2);
 144         jump = 0;
 145       } else
 146         jump = 3;
 147       break;
 148     case 6:
 149       if (!get(s, 1)) {
 150         s->pc = get(s, 2);
 151         jump = 0;
 152       } else
 153         jump = 3;
 154       break;
 155     case 7:
 156       put(s, 3, get(s, 1) < get(s, 2));
 157       jump = 4;
 158       break;
 159     case 8:
 160       put(s, 3, get(s, 1) == get(s, 2));
 161       jump = 4;
 162       break;
 163     case 99:
 164       debug_raw(2, "id=%d halting\n", s->id);
 165       return 0;
 166     default:
 167       crash(s, "unexpected opcode");
 168     }
 169     s->pc += jump;
 170     dump(s);
 171   }
 172 }
 173
 174 static void
 175 doit (int *p)
 176 {
 177   int data = 0, i;
 178   bool done = false, has_out = true;
 179
 180   debug("computing %d,%d,%d,%d,%d...\n", p[0], p[1], p[2], p[3], p[4]);
 181   for (i = 0; i < 5; i++) {
 182     memset(&amps[i], 0, sizeof amps[i]);
 183     amps[i].id = i;
 184     memcpy(amps[i].a, orig, len * sizeof orig[0]);
 185     amps[i].has_in = true;
 186     amps[i].in = p[i];
 187     if (run(&amps[i]) != -1 || amps[i].has_in)
 188       crash(&amps[i], "program finished too soon");
 189   }
 190
 191   while (!done) {
 192     done = true;
 193     for (i = 0; i < 5; i++) {
 194       if (amps[i].has_in)
 195         printf("program id=%d skipping input %d\n", amps[i].id, amps[i].in);
 196       amps[i].has_in = has_out;
 197       amps[i].in = data;
 198       if (run(&amps[i]) == -1)
 199         done = false;
 200       else if (!amps[i].has_out)
 201         printf("program id=%d completed with stale output\n", amps[i].id);
 202       has_out = amps[i].has_out;
 203       data = amps[i].out;
 204       amps[i].has_out = false;
 205     }
 206   }
 207   data = amps[4].out;
 208   debug("...%d\n", data);
 209   if (data > max)
 210     max = data;
 211 }
 212
 213 static void
 214 permute(int *p, int size, int n)
 215 {
 216   int i, t;
 217   if (size == 1) {
 218     doit(p);
 219     return;
 220   }
 221   permute(p, size - 1, n);
 222   for (i = 0; i < size - 1; i++) {
 223     if (size & 1) {
 224       t = p[0];
 225       p[0] = p[size - 1];
 226       p[size - 1] = t;
 227     } else {
 228       t = p[i];
 229       p[i] = p[size - 1];
 230       p[size - 1] = t;
 231     }
 232     permute(p, size - 1, n);
 233   }
 234 }
 235
 236 int
 237 main(int argc, char **argv) {
 238   int i;
 239   int phase[] = { 0, 1, 2, 3, 4 };
 240
 241   debug("");
 242   if (argc > 1)
 243     if (!(stdin = freopen(argv[1], "r", stdin))) {
 244       perror("failure");
 245       exit(2);
 246     }
 247
 248   while (scanf("%d%*[,\n]", &i) == 1) {
 249     orig[len++] = i;
 250     if (len > LIMIT - 3) {
 251       printf("recompile with larger LIMIT\n");
 252       exit(2);
 253     }
 254   }
 255   printf("Read %u slots\n", len);
 256   memcpy(amps[0].a, orig, len * sizeof orig[0]);
 257   dump(&amps[0]);
 258
 259   permute(phase, 5, 5);
 260   printf("part 1 best output %d\n", max);
 261
 262   for (i = 0; i < 5; i++)
 263     phase[i] += 5;
 264   max = 0;
 265   permute(phase, 5, 5);
 266   printf("part 2 best output %d\n", max);
 267
 268   return 0;
 269 }