2018/day14c.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 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     return true;
  17   }
  18   return false;
  19 }
  20
  21 #define LIMIT 5000000
  22
  23 #define PACK(a, b) (((a)<<4)|(b))
  24 #define NEXT(a) a&0xf
  25 static uint8_t array[LIMIT] = {
  26   [0] = PACK(3, 4),
  27   [1] = PACK(7, 8),
  28   [2] = PACK(3, 2),
  29   [3] = PACK(0, 1),
  30   [4] = PACK(1, 2),
  31   [5] = PACK(0, 1),
  32   [6] = PACK(1, 2),
  33   [7] = PACK(2, 3),
  34   [8] = PACK(4, 4),
  35   [9] = PACK(5, 4),
  36   [10] = PACK(1, 1),
  37   [11] = PACK(8, 3),
  38   [12] = PACK(9, 4),
  39   [13] = PACK(6, 2),
  40   [14] = PACK(1, 2),
  41   [15] = PACK(0, 1),
  42   [16] = PACK(7, 1),
  43 };
  44
  45 static unsigned need; /* iterations needed for part 1 */
  46 static char part1[11] = "unknown";
  47 static unsigned pattern; /* goal for part 2 */
  48 static unsigned mask;
  49 static unsigned recipes; /* recipes processed so far */
  50 static uint64_t recent; /* fifo of most-recently-seen hex digits */
  51 static unsigned next; /* next array index awaiting assignment */
  52 static uint8_t remain; /* recipes to skip before assigning next */
  53
  54 static bool e(uint8_t value) {
  55   if (value >= 10)
  56     return e(1) || e(value - 10);
  57   if (recipes++ == need)
  58     sprintf(part1, "%010llx", recent & 0xffffffffffULL);
  59   assert(next < LIMIT);
  60   if (remain)
  61     remain--;
  62   else
  63     array[next++] = PACK(remain = value, 1);
  64   recent = (recent << 4) | value;
  65   return (recent & mask) == pattern;
  66 }
  67
  68 int main(int argc, char **argv) {
  69   const char *goal = "077201";
  70   char buf[7] = "";
  71   int len;
  72   int idx1, idx2;
  73   int val;
  74   int iter = 0;
  75   FILE *f;
  76
  77   if (argc > 1)
  78     goal = argv[1];
  79   f = fopen(goal, "r");
  80   if (f) {
  81     if (fread(buf, 1, 6, f) != 6) {
  82       fprintf(stderr, "error reading file %s\n", goal);
  83       exit(1);
  84     }
  85     goal = buf;
  86     fclose(f);
  87   }
  88   need = strtol(goal, NULL, 10) + 10;
  89   len = strlen(goal);
  90   pattern = strtol(goal, NULL, 16);
  91   mask = (1 << 4*len) - 1;
  92
  93   idx1 = 4;
  94   idx2 = 12;
  95   recipes = 24;
  96   recent = 0x1677925107ULL;
  97   next = 17;
  98   remain = 7;
  99   do {
 100     iter++;
 101     if (!array[idx1])
 102       idx1 = remain;
 103     if (!array[idx2])
 104       idx2 = remain;
 105     val = (array[idx1] + array[idx2]) >> 4;
 106     idx1 += NEXT(array[idx1]);
 107     idx2 += NEXT(array[idx2]);
 108   } while (!e(val));
 109
 110   printf("after %s recipes, next ten recipes are %s\n", goal, part1);
 111   printf("%s found after %d recipes (%d iterations, array len %d)\n", goal,
 112          recipes - len, iter, next);
 113   return 0;
 114 }