2017/advent21.c

   1 #define _GNU_SOURCE 1
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include <unistd.h>
   6 #include <stdbool.h>
   7 #include <ctype.h>
   8 #include <assert.h>
   9
  10 #define MAX 2187  // precomputed for 18 iterations
  11 #define OUT_2 6   // 2x2 transformations: 6 among 16 (others by flip/rotate)
  12 #define OUT_3 102 // 3x3 transformations: 102 among 512 (others by flip/rotate)
  13 static unsigned short in2[1 << 4];
  14 static int in3[1 << 9];
  15 static char buf[4000]; // sized based on wc output
  16 static bool grid[MAX][MAX];
  17
  18 int
  19 main (int argc, char **argv)
  20 {
  21   // initial pattern is fixed
  22   int size = 3;
  23   grid[0][1] = grid[1][2] = grid[2][0] = grid[2][1] = grid[2][2] = true;
  24   memset(in2, -1, sizeof in2);
  25   memset(in3, -1, sizeof in3);
  26   int iter = 5, read2 = OUT_2, read3 = OUT_3;
  27   if (argc > 1)
  28     iter = atoi (argv[1]);
  29   if (argc > 2)
  30     read2 = atoi (argv[2]);
  31   if (argc > 3)
  32     read3 = atoi (argv[3]);
  33   int x, y, i;
  34   unsigned short p_in, p_out;
  35   // read the rules
  36   i = fread (buf, 1, sizeof buf, stdin);
  37   assert (i > 0 && i < sizeof buf);
  38   char *p = buf;
  39   while (read2--) {
  40     assert (p[6] == '=' && p[7] == '>' && p[20] == '\n');
  41     p_in = (((p[0] == '#') << 3) |
  42             ((p[1] == '#') << 2) |
  43             ((p[3] == '#') << 1) |
  44             ((p[4] == '#') << 0));
  45     p_out = (((p[9] == '#') << 8) |
  46              ((p[10] == '#') << 7) |
  47              ((p[11] == '#') << 6) |
  48              ((p[13] == '#') << 5) |
  49              ((p[14] == '#') << 4) |
  50              ((p[15] == '#') << 3) |
  51              ((p[17] == '#') << 2) |
  52              ((p[18] == '#') << 1) |
  53              ((p[19] == '#') << 0));
  54     // For 2x2, rotations is sufficient to cover all flips
  55     for (i = 0; i < 4; i++) {
  56       p_in = ((((p_in & (1 << 3)) != 0) << 2) |
  57               (((p_in & (1 << 2)) != 0) << 0) |
  58               (((p_in & (1 << 1)) != 0) << 3) |
  59               (((p_in & (1 << 0)) != 0) << 1));
  60       if (in2[p_in] <= 0x1ff)
  61         assert (in2[p_in] == p_out);
  62       in2[p_in] = p_out;
  63     }
  64     p += 21;
  65   }
  66   while (read3--) {
  67     assert (p[12] == '=' && p[13] == '>' && p[34] == '\n');
  68     p_in = (((p[0] == '#') << 8) |
  69             ((p[1] == '#') << 7) |
  70             ((p[2] == '#') << 6) |
  71             ((p[4] == '#') << 5) |
  72             ((p[5] == '#') << 4) |
  73             ((p[6] == '#') << 3) |
  74             ((p[8] == '#') << 2) |
  75             ((p[9] == '#') << 1) |
  76             ((p[10] == '#') << 0));
  77     p_out = (((p[15] == '#') << 15) |
  78              ((p[16] == '#') << 14) |
  79              ((p[17] == '#') << 13) |
  80              ((p[18] == '#') << 12) |
  81              ((p[20] == '#') << 11) |
  82              ((p[21] == '#') << 10) |
  83              ((p[22] == '#') << 9) |
  84              ((p[23] == '#') << 8) |
  85              ((p[25] == '#') << 7) |
  86              ((p[26] == '#') << 6) |
  87              ((p[27] == '#') << 5) |
  88              ((p[28] == '#') << 4) |
  89              ((p[30] == '#') << 3) |
  90              ((p[31] == '#') << 2) |
  91              ((p[32] == '#') << 1) |
  92              ((p[33] == '#') << 0));
  93     // For 3x3, need rotations + 1 flip
  94     for (i = 0; i < 4; i++) {
  95       p_in = ((((p_in & (1 << 8)) != 0) << 6) |
  96               (((p_in & (1 << 7)) != 0) << 3) |
  97               (((p_in & (1 << 6)) != 0) << 0) |
  98               (((p_in & (1 << 5)) != 0) << 7) |
  99               (((p_in & (1 << 4)) != 0) << 4) |
 100               (((p_in & (1 << 3)) != 0) << 1) |
 101               (((p_in & (1 << 2)) != 0) << 8) |
 102               (((p_in & (1 << 1)) != 0) << 5) |
 103               (((p_in & (1 << 0)) != 0) << 2));
 104       if (in3[p_in] >= 0)
 105         assert (in3[p_in] == p_out);
 106       in3[p_in] = p_out;
 107     }
 108     p_in = (((p_in & (7 << 6)) >> 6) |
 109             ((p_in & (7 << 3)) >> 0) |
 110             ((p_in & (7 << 0)) << 6));
 111     for (i = 0; i < 4; i++) {
 112       p_in = ((((p_in & (1 << 8)) != 0) << 6) |
 113               (((p_in & (1 << 7)) != 0) << 3) |
 114               (((p_in & (1 << 6)) != 0) << 0) |
 115               (((p_in & (1 << 5)) != 0) << 7) |
 116               (((p_in & (1 << 4)) != 0) << 4) |
 117               (((p_in & (1 << 3)) != 0) << 1) |
 118               (((p_in & (1 << 2)) != 0) << 8) |
 119               (((p_in & (1 << 1)) != 0) << 5) |
 120               (((p_in & (1 << 0)) != 0) << 2));
 121       if (in3[p_in] >= 0)
 122         assert (in3[p_in] == p_out);
 123       in3[p_in] = p_out;
 124     }
 125     p += 35;
 126   }
 127   // perform the expansions
 128   for (i = 0; i < iter; i++) {
 129     if (size & 1) { // expand 3x3 into 4x4
 130       for (y = size / 3; y--; )
 131         for (x = size / 3; x--; ) {
 132           p_in = ((grid[y * 3 + 0][x * 3 + 0] << 8) |
 133                   (grid[y * 3 + 0][x * 3 + 1] << 7) |
 134                   (grid[y * 3 + 0][x * 3 + 2] << 6) |
 135                   (grid[y * 3 + 1][x * 3 + 0] << 5) |
 136                   (grid[y * 3 + 1][x * 3 + 1] << 4) |
 137                   (grid[y * 3 + 1][x * 3 + 2] << 3) |
 138                   (grid[y * 3 + 2][x * 3 + 0] << 2) |
 139                   (grid[y * 3 + 2][x * 3 + 1] << 1) |
 140                   (grid[y * 3 + 2][x * 3 + 2]));
 141           if (in3[p_in] < 0) {
 142             printf ("3x3 mapping for %x not found!\n", p_in);
 143             return 1;
 144           }
 145           p_out = in3[p_in];
 146           grid[y * 4 + 0][x * 4 + 0] = p_out & (1 << 15);
 147           grid[y * 4 + 0][x * 4 + 1] = p_out & (1 << 14);
 148           grid[y * 4 + 0][x * 4 + 2] = p_out & (1 << 13);
 149           grid[y * 4 + 0][x * 4 + 3] = p_out & (1 << 12);
 150           grid[y * 4 + 1][x * 4 + 0] = p_out & (1 << 11);
 151           grid[y * 4 + 1][x * 4 + 1] = p_out & (1 << 10);
 152           grid[y * 4 + 1][x * 4 + 2] = p_out & (1 << 9);
 153           grid[y * 4 + 1][x * 4 + 3] = p_out & (1 << 8);
 154           grid[y * 4 + 2][x * 4 + 0] = p_out & (1 << 7);
 155           grid[y * 4 + 2][x * 4 + 1] = p_out & (1 << 6);
 156           grid[y * 4 + 2][x * 4 + 2] = p_out & (1 << 5);
 157           grid[y * 4 + 2][x * 4 + 3] = p_out & (1 << 4);
 158           grid[y * 4 + 3][x * 4 + 0] = p_out & (1 << 3);
 159           grid[y * 4 + 3][x * 4 + 1] = p_out & (1 << 2);
 160           grid[y * 4 + 3][x * 4 + 2] = p_out & (1 << 1);
 161           grid[y * 4 + 3][x * 4 + 3] = p_out & (1 << 0);
 162         }
 163       size = size / 3 * 4;
 164     } else { // expand 2x2 into 3x3
 165       for (y = size / 2; y--; )
 166         for (x = size / 2; x--; ) {
 167           p_in = ((grid[y * 2 + 0][x * 2 + 0] << 3) |
 168                   (grid[y * 2 + 0][x * 2 + 1] << 2) |
 169                   (grid[y * 2 + 1][x * 2 + 0] << 1) |
 170                   (grid[y * 2 + 1][x * 2 + 1]));
 171           if (in2[p_in] > 0x1ff) {
 172             printf ("2x2 mapping for %x not found!\n", p_in);
 173             return 1;
 174           }
 175           p_out = in2[p_in];
 176           grid[y * 3 + 0][x * 3 + 0] = p_out & (1 << 8);
 177           grid[y * 3 + 0][x * 3 + 1] = p_out & (1 << 7);
 178           grid[y * 3 + 0][x * 3 + 2] = p_out & (1 << 6);
 179           grid[y * 3 + 1][x * 3 + 0] = p_out & (1 << 5);
 180           grid[y * 3 + 1][x * 3 + 1] = p_out & (1 << 4);
 181           grid[y * 3 + 1][x * 3 + 2] = p_out & (1 << 3);
 182           grid[y * 3 + 2][x * 3 + 0] = p_out & (1 << 2);
 183           grid[y * 3 + 2][x * 3 + 1] = p_out & (1 << 1);
 184           grid[y * 3 + 2][x * 3 + 2] = p_out & (1 << 0);
 185         }
 186       size = size / 2 * 3;
 187     }
 188   }
 189   // describe the result
 190   int on = 0;
 191   for (y = 0; y < size; y++)
 192     for (x = 0; x < size; x++)
 193       if (grid[y][x])
 194         on++;
 195   printf ("after %d cycles, image size %d, %d pixels are on\n", iter, size, on);
 196   return 0;
 197 }