2019/day24.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 <stdint.h>
   8 #include <inttypes.h>
   9 #include <ctype.h>
  10 #include <limits.h>
  11
  12 static int debug_level = -1;
  13 static void
  14 debug_init(void) {
  15   if (debug_level < 0)
  16     debug_level = atoi(getenv("DEBUG") ?: "0");
  17 }
  18
  19 static void __attribute__((format(printf, 2, 3)))
  20 debug_raw(int level, const char *fmt, ...) {
  21   va_list ap;
  22   if (debug_level < 0)
  23     debug_level = atoi(getenv("DEBUG") ?: "0");
  24   if (debug_level >= level) {
  25     va_start(ap, fmt);
  26     vfprintf(stderr, fmt, ap);
  27     va_end(ap);
  28   }
  29 }
  30 #define debug(...) debug_raw(1, __VA_ARGS__)
  31
  32 static int __attribute__((noreturn)) __attribute__((format(printf, 1, 2)))
  33 die(const char *fmt, ...)
  34 {
  35   va_list ap;
  36   va_start(ap, fmt);
  37   vprintf(fmt, ap);
  38   va_end(ap);
  39   putchar('\n');
  40   exit(1);
  41 }
  42
  43 #define LIMIT 200
  44 static bool seen[1<<25];
  45 static int chain[2][LIMIT + 3];
  46
  47 static void
  48 dump(int gen, int val) {
  49   int i;
  50
  51   debug("at generation/level %d 0x%x:\n", gen, val);
  52   for (i = 0; i < 25; i++) {
  53     debug("%c", ".#"[!!(val & (1 << i))]);
  54     if (i % 5 == 4)
  55       debug("\n");
  56   }
  57 }
  58
  59 static int
  60 generation1(int val) {
  61   unsigned long long l = 0;
  62   int i, m, t;
  63
  64   for (i = 0; i < 5; i++)
  65     l |= (val & (0x1fULL << (5 * i))) << (8 + 2 * i);
  66   for (val = i = 0; i < 25; i++) {
  67     m = i / 5 * 7 + i % 5;
  68     t = __builtin_popcountll(l & (0x8382ULL << m));
  69     val |= (t == 2 || t == 2 - !(l & (1ULL << (m + 8)))) << i;
  70   }
  71   return val;
  72 }
  73
  74 static int
  75 generation2_one(int *p) {
  76   int r = 0, t;
  77
  78   if (!(p[-1] | p[0] | p[1]))
  79     return 0;
  80
  81   /* 1: [-1]12, [-1]8, [0]2, [0]6 */
  82   t = 4 - (!(p[-1] & (1 << 11)) + !(p[-1] & (1 << 7)) +
  83            !(p[0] & (1 << 1)) + !(p[0] & (1 << 5)));
  84   r |= (t == 1 || t == 1 + !(p[0] & (1 << 0))) << 0;
  85
  86   /* 2: [0]1, [-1]8, [0]3, [0]7 */
  87   t = 4 - (!(p[0] & (1 << 0)) + !(p[-1] & (1 << 7)) +
  88            !(p[0] & (1 << 2)) + !(p[0] & (1 << 6)));
  89   r |= (t == 1 || t == 1 + !(p[0] & (1 << 1))) << 1;
  90
  91   /* 3: [0]2, [-1]8, [0]4, [0]8 */
  92   t = 4 - (!(p[0] & (1 << 1)) + !(p[-1] & (1 << 7)) +
  93            !(p[0] & (1 << 3)) + !(p[0] & (1 << 7)));
  94   r |= (t == 1 || t == 1 + !(p[0] & (1 << 2))) << 2;
  95
  96   /* 4: [0]3, [-1]8, [0]5, [0]9 */
  97   t = 4 - (!(p[0] & (1 << 2)) + !(p[-1] & (1 << 7)) +
  98            !(p[0] & (1 << 4)) + !(p[0] & (1 << 8)));
  99   r |= (t == 1 || t == 1 + !(p[0] & (1 << 3))) << 3;
 100
 101   /* 5: [0]4, [-1]8, [-1]14, [0]10 */
 102   t = 4 - (!(p[0] & (1 << 3)) + !(p[-1] & (1 << 7)) +
 103            !(p[-1] & (1 << 13)) + !(p[0] & (1 << 9)));
 104   r |= (t == 1 || t == 1 + !(p[0] & (1 << 4))) << 4;
 105
 106   /* 6: [-1]12, [0]1, [0]7, [0]11 */
 107   t = 4 - (!(p[-1] & (1 << 11)) + !(p[0] & (1 << 0)) +
 108            !(p[0] & (1 << 6)) + !(p[0] & (1 << 10)));
 109   r |= (t == 1 || t == 1 + !(p[0] & (1 << 5))) << 5;
 110
 111   /* 7: [0]6, [0]2, [0]8, [0]12 */
 112   t = 4 - (!(p[0] & (1 << 5)) + !(p[0] & (1 << 1)) +
 113            !(p[0] & (1 << 7)) + !(p[0] & (1 << 11)));
 114   r |= (t == 1 || t == 1 + !(p[0] & (1 << 6))) << 6;
 115
 116   /* 8: [0]7, [0]3, [0]9, [1]1, [1]2, [1]3, [1]4, [1]5 */
 117   t = 8 - (!(p[0] & (1 << 6)) + !(p[0] & (1 << 2)) +
 118            !(p[0] & (1 << 8)) + !(p[1] & (1 << 0)) +
 119            !(p[1] & (1 << 1)) + !(p[1] & (1 << 2)) +
 120            !(p[1] & (1 << 3)) + !(p[1] & (1 << 4)));
 121   r |= (t == 1 || t == 1 + !(p[0] & (1 << 7))) << 7;
 122
 123   /* 9: [0]8, [0]4, [0]10, [0]14 */
 124   t = 4 - (!(p[0] & (1 << 7)) + !(p[0] & (1 << 3)) +
 125            !(p[0] & (1 << 9)) + !(p[0] & (1 << 13)));
 126   r |= (t == 1 || t == 1 + !(p[0] & (1 << 8))) << 8;
 127
 128   /* 10: [0]9, [0]5, [-1]14, [0]15 */
 129   t = 4 - (!(p[0] & (1 << 8)) + !(p[0] & (1 << 4)) +
 130            !(p[-1] & (1 << 13)) + !(p[0] & (1 << 14)));
 131   r |= (t == 1 || t == 1 + !(p[0] & (1 << 9))) << 9;
 132
 133   /* 11: [-1]12, [0]6, [0]12, [0]16 */
 134   t = 4 - (!(p[-1] & (1 << 11)) + !(p[0] & (1 << 5)) +
 135            !(p[0] & (1 << 11)) + !(p[0] & (1 << 15)));
 136   r |= (t == 1 || t == 1 + !(p[0] & (1 << 10))) << 10;
 137
 138   /* 12: [0]11, [0]7, [1]1, [1]6, [1]11, [1]16, [1]21, [0]17 */
 139   t = 8 - (!(p[0] & (1 << 10)) + !(p[0] & (1 << 6)) +
 140            !(p[1] & (1 << 0)) + !(p[1] & (1 << 5)) +
 141            !(p[1] & (1 << 10)) + !(p[1] & (1 << 15)) +
 142            !(p[1] & (1 << 20)) + !(p[0] & (1 << 16)));
 143   r |= (t == 1 || t == 1 + !(p[0] & (1 << 11))) << 11;
 144
 145   /* 14: [1]5, [1]10, [1]15, [1]20, [1]25, [0]9, [0]15, [0]19 */
 146   t = 8 - (!(p[1] & (1 << 4)) + !(p[1] & (1 << 9)) +
 147            !(p[1] & (1 << 14)) + !(p[1] & (1 << 19)) +
 148            !(p[1] & (1 << 24)) + !(p[0] & (1 << 8)) +
 149            !(p[0] & (1 << 14)) + !(p[0] & (1 << 18)));
 150   r |= (t == 1 || t == 1 + !(p[0] & (1 << 13))) << 13;
 151
 152   /* 15: [0]14, [0]10, [-1]14, [0]20 */
 153   t = 4 - (!(p[0] & (1 << 13)) + !(p[0] & (1 << 9)) +
 154            !(p[-1] & (1 << 13)) + !(p[0] & (1 << 19)));
 155   r |= (t == 1 || t == 1 + !(p[0] & (1 << 14))) << 14;
 156
 157   /* 16: [-1]12, [0]11, [0]17, [0]21 */
 158   t = 4 - (!(p[-1] & (1 << 11)) + !(p[0] & (1 << 10)) +
 159            !(p[0] & (1 << 16)) + !(p[0] & (1 << 20)));
 160   r |= (t == 1 || t == 1 + !(p[0] & (1 << 15))) << 15;
 161
 162   /* 17: [0]16, [0]12, [0]18, [0]22 */
 163   t = 4 - (!(p[0] & (1 << 15)) + !(p[0] & (1 << 11)) +
 164            !(p[0] & (1 << 17)) + !(p[0] & (1 << 21)));
 165   r |= (t == 1 || t == 1 + !(p[0] & (1 << 16))) << 16;
 166
 167   /* 18: [0]17, [1]21, [1]22, [1]23, [1]24, [1]25, [0]19, [0]23 */
 168   t = 8 - (!(p[0] & (1 << 16)) + !(p[1] & (1 << 20)) +
 169            !(p[1] & (1 << 21)) + !(p[1] & (1 << 22)) +
 170            !(p[1] & (1 << 23)) + !(p[1] & (1 << 24)) +
 171            !(p[0] & (1 << 18)) + !(p[0] & (1 << 22)));
 172   r |= (t == 1 || t == 1 + !(p[0] & (1 << 17))) << 17;
 173
 174   /* 19: [0]18, [0]14, [0]20, [0]24 */
 175   t = 4 - (!(p[0] & (1 << 17)) + !(p[0] & (1 << 13)) +
 176            !(p[0] & (1 << 19)) + !(p[0] & (1 << 23)));
 177   r |= (t == 1 || t == 1 + !(p[0] & (1 << 18))) << 18;
 178
 179   /* 20: [0]19, [0]15, [-1]14, [0]25 */
 180   t = 4 - (!(p[0] & (1 << 18)) + !(p[0] & (1 << 14)) +
 181            !(p[-1] & (1 << 13)) + !(p[0] & (1 << 24)));
 182   r |= (t == 1 || t == 1 + !(p[0] & (1 << 19))) << 19;
 183
 184   /* 21: [-1]12, [0]16, [0]22, [-1]18 */
 185   t = 4 - (!(p[-1] & (1 << 11)) + !(p[0] & (1 << 15)) +
 186            !(p[0] & (1 << 21)) + !(p[-1] & (1 << 17)));
 187   r |= (t == 1 || t == 1 + !(p[0] & (1 << 20))) << 20;
 188
 189   /* 22: [0]21, [0]17, [0]23, [-1]18 */
 190   t = 4 - (!(p[0] & (1 << 20)) + !(p[0] & (1 << 16)) +
 191            !(p[0] & (1 << 22)) + !(p[-1] & (1 << 17)));
 192   r |= (t == 1 || t == 1 + !(p[0] & (1 << 21))) << 21;
 193
 194   /* 23: [0]22, [0]18, [0]24, [-1]18 */
 195   t = 4 - (!(p[0] & (1 << 21)) + !(p[0] & (1 << 17)) +
 196            !(p[0] & (1 << 23)) + !(p[-1] & (1 << 17)));
 197   r |= (t == 1 || t == 1 + !(p[0] & (1 << 22))) << 22;
 198
 199   /* 24: [0]23, [0]19, [0]25, [-1]18 */
 200   t = 4 - (!(p[0] & (1 << 22)) + !(p[0] & (1 << 18)) +
 201            !(p[0] & (1 << 24)) + !(p[-1] & (1 << 17)));
 202   r |= (t == 1 || t == 1 + !(p[0] & (1 << 23))) << 23;
 203
 204   /* 25: [0]24, [0]20, [-1]14, [-1]18 */
 205   t = 4 - (!(p[0] & (1 << 23)) + !(p[0] & (1 << 19)) +
 206            !(p[-1] & (1 << 13)) + !(p[-1] & (1 << 17)));
 207   r |= (t == 1 || t == 1 + !(p[0] & (1 << 24))) << 24;
 208
 209   return r;
 210 }
 211
 212 static int
 213 generation2(int g) {
 214   int i;
 215   int t = 0;
 216
 217   for (i = 1; i <= LIMIT + 1; i++)
 218     t += __builtin_popcount(chain[1 - g % 2][i] =
 219                             generation2_one(&chain[g % 2][i]));
 220   return t;
 221 }
 222
 223 int
 224 main(int argc, char **argv) {
 225   int ch, i = 0, val = 0;
 226   int limit = LIMIT;
 227
 228   debug_init();
 229   if (argc > 1 && strcmp(argv[1], "-"))
 230     if (!(stdin = freopen(argv[1], "r", stdin))) {
 231       perror("failure");
 232       exit(2);
 233     }
 234   if (argc > 2) {
 235     limit = atoi(argv[2]);
 236     if (limit % 2 || limit > LIMIT)
 237       die("need even limit less than %d", LIMIT);
 238   }
 239
 240   while ((ch = getchar()) != EOF) {
 241     if (ch == '\n')
 242       continue;
 243     val |= (ch == '#') << i++;
 244   }
 245   if (i != 25)
 246     die("incorrect input");
 247   chain[0][limit / 2 + 1] = val;
 248
 249   dump(0, val);
 250   for (i = 0; i < limit; i++) {
 251     seen[val] = true;
 252     val = generation1(val);
 253     if (seen[val])
 254       break;
 255     dump(i + 1, val);
 256   }
 257   //  if (i == LIMIT)
 258   //    die("recompile with larger LIMIT");
 259   printf("part1: first repeating generation %d has score %d\n", i, val);
 260
 261   dump(-1, chain[0][limit / 2]);
 262   dump(0, chain[0][limit / 2 + 1]);
 263   dump(1, chain[0][limit / 2 + 2]);
 264   for (i = 0; i < limit; i++) {
 265     val = generation2(i);
 266     dump(-1, chain[1 - i % 2][limit / 2]);
 267     dump(0, chain[1 - i % 2][limit / 2 + 1]);
 268     dump(1, chain[1 - i % 2][limit / 2 + 2]);
 269   }
 270   printf("part2: after %d generations, there are %d bugs\n", i, val);
 271   return 0;
 272 }