day 20

[advent21.git] / 20a.c

diff --git a/20a.c b/20a.c
new file mode 100644 (file)
index 0000000..7919730
--- /dev/null
+++ b/20a.c
@@ -0,0 +1,93 @@
+#include <stdio.h>
+
+#include <uthash.h>
+
+struct point {int x; int y; int gen; };
+struct entry {
+       struct point p;
+       char c;
+       UT_hash_handle hh;
+};
+
+char *key = NULL;
+
+void add_point(struct entry **board, int x, int y, int gen, char c)
+{
+       struct entry *e = calloc(1, sizeof(struct entry));
+       e->p = (struct point){.x=x, .y=y, .gen=gen};
+       e->c = c;
+       HASH_ADD(hh, *board, p, sizeof(struct point), e);
+}
+
+char get_point(struct entry **board, int x, int y, int gen)
+{
+       struct entry *e;
+       struct point p;
+       memset(&p, 0, sizeof(p));
+       p.x = x;
+       p.y = y;
+       p.gen = gen;
+       HASH_FIND(hh, *board, &p, sizeof(struct point), e);
+       if (e == NULL) {
+               if (key[0] == '#')
+                       return gen % 2 == 0 ? '.' : '#';
+               else
+                       return '.';
+       }
+       return e->c;
+}
+
+char evolve(struct entry **board, int px, int py, int gen)
+{
+       int r = 0;
+       for (int y = py-1; y<=py+1; y++)
+               for (int x = px-1; x<=px+1; x++)
+                       r = r*2 + (get_point(board, x, y, gen) == '#' ? 1 : 0);
+       return key[r];
+}
+
+int main()
+{
+       size_t len = 0;
+       if (getline(&key, &len, stdin) == -1)
+               return -1;
+       if (getchar() != '\n')
+               return 1;
+
+       struct entry *board = NULL;
+       int x = 0, minx = 0, maxx = 0;
+       int y = 0, miny = 0, maxy = 0;
+
+       int c;
+       while ((c = getchar()) != EOF) {
+               if (c == '\n') {
+                       if (x > maxx)
+                               maxx = x;
+                       x = 0;
+                       y++;
+               } else {
+                       add_point(&board, x++, y, 0, c);
+               }
+       }
+       maxy = y;
+
+       int gen = 1;
+       for (; gen <= 2; gen++) {
+               minx -= 3;
+               miny -= 3;
+               maxx += 3;
+               maxy += 3;
+
+               for (y = miny; y<maxy; y++)
+                       for (x = minx; x<maxx; x++)
+                               add_point(&board, x, y, gen,
+                                       evolve(&board, x, y, gen-1));
+       }
+
+       int r = 0;
+       for (y = miny; y<maxy; y++)
+               for (x = minx; x<maxx; x++)
+                       if (get_point(&board, x, y, gen-1) == '#')
+                               r++;
+       printf("%d\n", r);
+}