2018/day14b.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 25000000
  22
  23 static char list[LIMIT] = "37";
  24
  25 static void dump(int iter, int size, int idx1, int idx2) {
  26   if (!debug("iter %d:", iter))
  27     return;
  28   for (int i = 0; i < size; i++)
  29     if (i == idx1)
  30       debug("(%c)", list[i]);
  31     else if (i == idx2)
  32       debug("[%c]", list[i]);
  33     else
  34       debug(" %c", list[i]);
  35   debug("\n");
  36 }
  37
  38 int main(int argc, char **argv) {
  39   const char *goal = "077201";
  40   char buf[7] = "";
  41   int max = LIMIT;
  42   int size = 2;
  43   int idx1 = 0;
  44   int idx2 = 1;
  45   int iter = 0;
  46   FILE *f;
  47
  48   if (argc > 1)
  49     goal = argv[1];
  50   f = fopen(goal, "r");
  51   if (f) {
  52     if (fread(buf, 1, 6, f) != 6) {
  53       fprintf(stderr, "error reading file %s\n", goal);
  54       exit(1);
  55     }
  56     goal = buf;
  57     fclose(f);
  58   }
  59   if (argc > 2)
  60     max = atoi(argv[2]);
  61   if (max > LIMIT) {
  62     fprintf(stderr, "recompile with larger limit\n");
  63     exit(1);
  64   }
  65
  66   while (!strstr(list + size - 10, goal) && size < max - 1) {
  67     iter++;
  68     int e = list[idx1] - '0' + list[idx2] - '0';
  69     if (e > 9) {
  70       list[size++] = '1';
  71       e -= 10;
  72     }
  73     list[size++] = e + '0';
  74     idx1 = (list[idx1] - '0' + idx1 + 1) % size;
  75     idx2 = (list[idx2] - '0' + idx2 + 1) % size;
  76     if (!(size & 0xffffe))
  77       printf("%d...\n", size);
  78   }
  79   dump(iter, size, idx1, idx2);
  80   char *p = strstr(list + size - 10, goal);
  81   if (p)
  82     printf("%td recipes before goal %s (%d iterations)\n",
  83            p - list, goal, iter);
  84   else
  85     printf("%d iterations and size %d insufficient to find goal %s\n",
  86            iter, size, goal);
  87   return 0;
  88 }