2018/day12.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 void 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   }
  17 }
  18
  19 #define LIMIT 200
  20 static bool next[32];
  21 static int size;
  22
  23 static void dump(int g, bool *a) {
  24   for (int i = 0; i < size; i++)
  25     debug("%c", a[i] ? '#' : '.');
  26   debug("\n");
  27 }
  28
  29 static void gen(int g, bool *a, bool *b) {
  30   int i;
  31   uint8_t act = 0;
  32
  33   debug("beginning generation %d\n", g);
  34   assert(!(a[0] | a[1] | a[size - 2] | a[size - 1]));
  35   for (i = 0; i < size - 2; i++) {
  36     act = ((act << 1) & 0x1f) | a[i + 2];
  37     b[i] = next[act];
  38   }
  39 }
  40
  41 static int sum(int offset, bool *a) {
  42   int s = 0;
  43   int i;
  44   for (i = 0; i < size; i++)
  45     if (a[i])
  46       s += i - offset + 1;
  47   return s;
  48 }
  49
  50 int main(int argc, char **argv) {
  51   size_t len = 0, count = 0;
  52   char *line;
  53   char *p;
  54   int offset;
  55   int generations = 20;
  56   bool *state[2];
  57   int i;
  58
  59   /* Part 1 - read in initial line */
  60   if (argc > 2)
  61     generations = atoi(argv[2]);
  62   if (argc > 1 && !(stdin = freopen(argv[1], "r", stdin))) {
  63     perror("failure");
  64     exit(2);
  65   }
  66
  67   if (getline(&line, &len, stdin) < 0 || getchar() != '\n') {
  68     fprintf(stderr, "bad input\n");
  69     exit(1);
  70   }
  71   p = strchr(line, ':');
  72   if (p[1] != ' ') {
  73     fprintf(stderr, "bad input\n");
  74     exit(1);
  75   }
  76   p++;
  77   offset = 3 + LIMIT;
  78   size = strchr(p, '\n') - p + 2 * offset;
  79   state[0] = calloc(size, sizeof(bool));
  80   state[1] = calloc(size, sizeof(bool));
  81   count = offset - 2;
  82   while (*p != '\n')
  83     state[0][count++] = *p++ == '#';
  84
  85   /* Part 2 - read in rules */
  86   count = 0;
  87   while (getline(&line, &len, stdin) >= 0) {
  88     ++count;
  89     int idx = 0;
  90     for (i = 0; i < 5; i++)
  91       idx = (idx << 1) | (line[i] == '#');
  92     next[idx] = line[9] == '#';
  93   }
  94   printf("Read %zu lines\n", count);
  95   assert(!(next[0] | next[1] | next[16])); /* Otherwise offset is too small */
  96   debug("%*c\n", offset, '0');
  97   dump(0, state[0]);
  98
  99   /* Part 3 - determine output */
 100   int s = sum(offset, state[0]);
 101   int diff = 0;
 102   count = 0;
 103   for (i = 1; i <= LIMIT; i++) {
 104     int s2;
 105     gen(i, state[(i + 1) % 2], state[i % 2]);
 106     dump(i, state[i % 2]);
 107     s2 = sum(offset, state[i % 2]);
 108     if (generations == i)
 109       printf("sum at generation %d is %d\n", i, s2);
 110     if (s2 - s == diff)
 111       count++;
 112     else {
 113       count = 0;
 114       diff = s2 - s;
 115     }
 116     s = s2;
 117   }
 118   printf("pattern locked at diff of %d for last %zu iterations of %d\n",
 119          diff, count, LIMIT);
 120   printf("sum(%d) is %d, projection is %" PRId64 "\n", LIMIT, s,
 121          diff * (UINT64_C(50000000000) - LIMIT) + s);
 122   return 0;
 123 }