day 20

diff --git a/16b.c b/16b.c
index 6c93a16..9b5f3e1 100644 (file)
--- a/16b.c
+++ b/16b.c
@@ -13,10 +13,9 @@ struct stream { int pos; char *buf; };
 
 int next(struct stream *f)
 {
-       int r;
        if (*f->buf == '\0')
-               f->buf = hex2bin[r];
-       r =*(f->buf++) == '1' ? 1 : 0;
+               f->buf = hex2bin[getchar()];
+       int r = *(f->buf++) == '1' ? 1 : 0;
        f->pos++;
        return r;
 }

diff --git a/18.txt b/18.txt
new file mode 100644 (file)
index 0000000..619ba12
--- /dev/null
+++ b/18.txt
@@ -0,0 +1,100 @@
+[[1,[8,[5,8]]],[[4,4],[8,[8,8]]]]
+[[[3,[2,3]],[[8,0],2]],[0,[[8,1],[7,0]]]]
+[4,[[0,3],[[6,6],[3,8]]]]
+[[[7,[6,4]],[[0,6],[2,0]]],[[[5,6],[0,4]],[[8,1],[9,1]]]]
+[[[6,3],[[6,9],4]],[[1,[4,2]],[[0,0],1]]]
+[[2,0],[3,[0,8]]]
+[[0,[5,5]],[[4,2],[3,[6,4]]]]
+[[[[9,9],[8,5]],[7,4]],[[6,9],[8,[0,8]]]]
+[[[[7,1],[2,9]],[[9,3],0]],[3,[[0,6],[7,6]]]]
+[[[[3,7],[7,1]],[[5,8],[0,1]]],3]
+[[[[4,6],[6,2]],[[9,1],7]],[[9,1],[8,0]]]
+[[[[2,7],0],[[9,4],[2,6]]],[0,[[7,4],[0,3]]]]
+[[5,[[0,2],[8,8]]],[[[4,1],9],3]]
+[[[7,1],[[3,7],[3,4]]],[[[0,7],[1,6]],1]]
+[[[6,5],[[1,8],[8,8]]],[[4,5],[3,7]]]
+[[[1,[3,3]],[[3,2],[5,7]]],[[8,[9,3]],[[5,3],4]]]
+[[[4,[2,7]],9],[9,[[5,6],4]]]
+[[[9,1],3],[[1,2],9]]
+[[[[0,0],[2,3]],[[7,8],[1,5]]],[[[8,6],7],[[8,3],9]]]
+[6,[[5,[0,8]],1]]
+[4,[[[3,0],[2,0]],[[7,2],[1,4]]]]
+[[[[4,3],[4,1]],8],[[[9,4],[1,9]],[4,[0,6]]]]
+[4,[5,6]]
+[[[0,[6,1]],[[6,1],3]],[[0,[7,8]],[1,0]]]
+[[5,[[8,7],8]],8]
+[[5,[[5,2],0]],[[1,[4,7]],[[0,9],[2,3]]]]
+[[7,[2,2]],[[6,3],[5,8]]]
+[[[0,9],5],[1,[[5,7],1]]]
+[[8,[3,[0,3]]],[[[2,2],2],[[8,8],[8,9]]]]
+[[6,[[3,2],[2,6]]],[5,1]]
+[[[[9,8],[6,8]],[0,7]],7]
+[[[7,2],[[6,3],4]],2]
+[[[5,2],[[1,6],[8,3]]],[6,5]]
+[[5,2],[0,5]]
+[[[[4,5],5],[[4,6],[1,2]]],[[[3,6],[4,9]],[1,9]]]
+[[1,[4,1]],[[9,[5,5]],[[9,0],[5,7]]]]
+[[[[8,9],[7,7]],2],[8,1]]
+[[[8,1],[8,[9,5]]],3]
+[[[2,[3,9]],[[5,4],[7,9]]],[9,8]]
+[8,[[2,[0,9]],[[5,0],4]]]
+[[[6,[4,8]],[0,6]],[[8,[1,8]],1]]
+[[6,[[1,0],[6,2]]],[[9,[3,7]],[5,[4,0]]]]
+[[8,[0,[9,1]]],8]
+[7,[4,[7,2]]]
+[[1,[[5,7],[5,4]]],[[5,[8,0]],[1,6]]]
+[[[[0,6],[6,2]],3],[[[9,3],7],[7,[1,2]]]]
+[[[6,[4,9]],8],[6,5]]
+[[[0,[1,9]],[[1,9],[3,9]]],[[[3,4],[7,5]],3]]
+[[[[9,3],5],[[0,5],[2,7]]],9]
+[[[6,[7,5]],5],[1,[[7,0],[3,4]]]]
+[[[2,1],[[1,3],[1,5]]],[4,[9,[7,9]]]]
+[[[[7,9],4],[[8,8],7]],[[[3,5],2],[[4,4],[6,5]]]]
+[[1,1],[1,1]]
+[[8,[0,2]],8]
+[[[2,[2,1]],[[1,7],[1,2]]],[[1,6],5]]
+[6,[0,[[1,0],[0,9]]]]
+[6,[[2,[8,0]],[8,[8,8]]]]
+[4,[[3,[0,3]],4]]
+[[[5,3],3],[[0,[7,6]],[2,[5,8]]]]
+[[[[8,1],[4,1]],[[5,8],[4,8]]],[[[1,7],[7,2]],[0,[2,7]]]]
+[[[2,[3,5]],3],5]
+[[7,[[9,5],[8,2]]],[[[1,8],8],5]]
+[[3,5],[[4,[9,3]],5]]
+[[[[4,6],2],[2,2]],[0,[0,4]]]
+[[[[5,8],[6,6]],[2,0]],[[[2,3],9],[[4,5],2]]]
+[[[[1,9],3],[[3,4],6]],[[3,6],[6,[0,7]]]]
+[[[0,[5,5]],[2,6]],[[[7,4],4],2]]
+[0,[[8,[6,2]],[5,[1,5]]]]
+[[[[5,5],[9,6]],[[5,2],2]],[[4,7],[[5,5],[1,6]]]]
+[[4,7],[[[1,8],[9,6]],[2,3]]]
+[5,[5,4]]
+[[[[2,1],[7,0]],[5,[7,8]]],[6,[3,1]]]
+[[[3,1],[[2,4],6]],[[[1,8],[2,1]],[[1,7],4]]]
+[[[5,[3,3]],6],[[[0,0],9],[1,[7,4]]]]
+[[[6,5],[[7,3],4]],[[9,[0,3]],[3,[6,0]]]]
+[[[3,4],7],[8,[[1,7],[9,9]]]]
+[[[[2,1],6],[2,6]],[[[8,1],[6,2]],[9,0]]]
+[[8,4],[5,2]]
+[[4,[[4,5],9]],[[3,[5,2]],[4,2]]]
+[[[8,8],[[8,0],[5,3]]],4]
+[[1,8],[0,2]]
+[[[[7,2],[9,0]],[[9,2],[1,2]]],[[[4,0],3],0]]
+[[[[1,2],[1,8]],[[4,3],[8,6]]],[[[5,1],8],[8,1]]]
+[[[[5,3],[7,2]],7],[[6,[7,9]],[[3,8],[9,4]]]]
+[[[[3,1],[2,5]],6],[[[3,2],[8,8]],[4,6]]]
+[9,[[3,[2,3]],6]]
+[[[[4,0],[5,6]],[5,4]],[[[9,0],[1,8]],[5,[3,6]]]]
+[[[[9,5],[9,4]],[[5,7],5]],[[[1,4],7],[6,1]]]
+[[2,[6,[8,2]]],[7,[1,[3,3]]]]
+[[[9,1],[0,[6,3]]],[[5,[1,5]],[7,[1,0]]]]
+[1,6]
+[[0,[2,[8,9]]],[[[4,5],[5,4]],1]]
+[[[1,[4,1]],8],[[2,[7,0]],[7,[9,9]]]]
+[[[[5,7],[3,5]],[[6,6],2]],[2,[8,[9,0]]]]
+[6,[[[3,9],8],[[4,3],[6,1]]]]
+[[[[6,7],[7,6]],[2,8]],[[9,[4,1]],6]]
+[[[[4,5],[4,5]],[[0,6],5]],[[[6,5],[7,0]],1]]
+[[[[6,7],9],[[5,5],[6,6]]],[[7,1],[[8,2],[3,1]]]]
+[[[9,6],7],[[[1,8],8],[1,7]]]
+[[5,2],[[1,9],[2,2]]]

diff --git a/18a.c b/18a.c
new file mode 100644 (file)
index 0000000..719c3f0
--- /dev/null
+++ b/18a.c
@@ -0,0 +1,55 @@
+#include <stdio.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <ctype.h>
+
+struct number {
+       int depth;
+       int number;
+};
+
+int parse_number(struct number numbers[])
+{
+       int ns = 0;
+       int depth = 0;
+       int c = getchar();
+       while ((c = getchar()) != '\n') {
+               switch(c) {
+               case '[':
+                       depth++;
+                       break;
+               case ']':
+                       depth--;
+                       break;
+               case ',':
+                       break;
+               default:
+                       if (isdigit(c))
+                               numbers[ns++] = (struct number){.depth=depth, .number=c-'0'};
+                       else
+                               printf("halp\n");
+                       break;
+               }
+       }
+       return ns;
+}
+
+void print_number(struct number n[], int ns)
+{
+       int olddepth = 0;
+       for (int i = 0; i<ns; i++) {
+               if (n[i].depth > olddepth)
+                       printf("[");
+               else if (n[i].depth < olddepth)
+                       printf("]");
+               printf("%d ", n[i].number);
+               olddepth = n[i].depth;
+       }
+}
+
+int main ()
+{
+       struct number n[100];
+       int ns = parse_number(n);
+       print_number(n, ns);
+}

diff --git a/20.txt b/20.txt
new file mode 100644 (file)
index 0000000..8949da3
--- /dev/null
+++ b/20.txt
@@ -0,0 +1,102 @@
+#.#..#.#...##.###.##.#.###....#..##..#.#####.#.##.#.##..##..#.#.######..##..####.#....#.#....##....#####..#######..###..#.##..#....#....#....#..#..#..##...####..###.##..##..#.#.#.#.#.#.#..##.###.##.#.##.#.##.#####..###.#.#...##..##...###...###..##...##.######....####.###...####.##.....###.##.#.##.#.....##.##..###.....#..##....#.##.#...##.###.###.#..####....#.###...#....#..###...##..#####..#.######..#.#....####.####.#.#....#.###..##...#.###.####....#.##.#....##...##.#..#....#.##...#....#.####..#.#..####.#...
+
+####.#.#####..#.#####..###.###...##...##.#.##.###..#...#......##.##..##.####.........#..##...#.####.
+#.#.###...###.####....##..##......##.#.####...#########.#.###.#.#.#..###..##...###.###.#.######.#.#.
+##...#.#..##.#.##...#..##.####.###.###..###...#####.##.#..##.#.#####.###...#.###.....#######..##...#
+####..#.###..####..##...#..######.##.#...#.#..#...#.##..####...##...#.#.#.##.##......##.##.#.##.....
+.#########.###.###..#......##.###.####.#..###.#.##.####.#..###....##.##.##.#..##..#..##..#.##.#.#...
+..#.#.#...#.###...##..#.#....#.###..#.##...#.#....#.##.#.##.##..###.##.####..#.###.#.####..##....###
+.##....#.#.##.....####..#..##...#..............#...###.####....#..#....##.####..###....##...#.###.##
+.#.########..###.#..###.#..###.#.##.#.#.#.###...##..##.#.#..#..##.#......###.###..#.##.####.....#...
+...###.#...#.##..#...##..###...###...#....#..#.#######...#..##..###.#.#......#.#..###..#.#.###.#..##
+..#####...##.##.....#.#####....#..#.#......#.#.#....####.##..#.##.##..##.#########.##.###...###...##
+#...#...#####....##.#.#.###......##.#####.#.###.#.#.#.####...##.#..#.#.#..#.#..####..##...#.#....#..
+.#..#.##.#.#.##.#..#.######.#.#....#.##.#..#.#.##...####..##.##..####.####.#...#...#####.#....####..
+.....#.##..#.#.###.##....##....##.##.#...###.#.#..#.##.###.#...#...#.#####..#.##.....#...#.#.#.#....
+....##.##...##..##.########...###...###..###..#..#...####..#..#..####.#..#.#.....###.#..#.#...#..#..
+...#.#.#.###...#...#####.#....##..####..##.####.#..###..#.##.###...#...#..#.##...##.#...#.....###...
+##....#..#.#...#.......#.##.######....#..##.##..#...###.#..###..#.#..##.#.........##..###.#......#.#
+###...#########.#....###...#.#...#.#..#..##.##.#..#.#......##.#.##.#....#########...#.#.##..########
+.###...#######.#......####.#.##.###.##.#..##.###.##..########.#..##.##..#..#..#...#.#..###..##...###
+..#...##.....#.#..###.#..#.##.#..#.#.#.##.#####....####.#.#..#...##.##.##.#..####.#..#.#####......#.
+#...##..##########.......#.....##.####..#####..##...#...##..###.#.#.#.#.#####.####.##.##.#.#.....###
+.#.###.#..#..###.#..#.#.#....#.#####.##....#.#.#..##.#.#.#.###.#..#..##..#..###....#...##.#..#.#.#.#
+...###.#..#....##.#...#...#..#....###...#.....#..####.##..#.###...#....###..##.#.##...#..##..#.##.#.
+#.#.###.#..#....##.#..#####..###...##.##...#...###.#.##.#.#.#...#.#.#....####..#.##..##...#.#.##...#
+.#..#..#..##########.#.###.#..##..##.#.##.#..#.##..#..#.#.##....##..##....##.######..#....#.#..#####
+...#.##.#.###.#..#####.#........#.#.####.##..##..#.#..##...#..#..#..#.#.#.#..#..#.###..#..#.####.###
+.###...###.#..#..#....##.#.##.#.....#..#.#.#...##.##.#...####..##..#.#..#...#....###.#..#####.#####.
+...#.#.##.#......#.#....#####..#.#..##..#.#.#..###.##...#..#..##...#...#######.###.#####.###...#....
+.##....#...###..####....#.#..##.#.#.##..###########...#.###..#.##.##.##.#....##.##..####......###...
+#.##......#.##.###.##...##..#.##.#.##.##..#..#.#####....##.##.###.#########.#..###.....#....##..##.#
+#.####.#.#...#.#.#.##..##.###..###.#..#..#####...####.####....#.##...####..#######.#....#######.#.#.
+##...#..#...##...#.#...#.##.#......#.#.#.....#.#.#....#.#.#...#.#.#######.##.#.#..##..#....#.#..#..#
+#..##..#.#..#.#..#.#.#.#.#....#.#.##.##.#.##.....##...##...##.#####.#.###.#..#..####.#.#..#######.#.
+.#.##..#.##..#....##.#.#..#..##..##...#...######.###....#..#...##..#.#..........#.######.........#..
+###.#.#..#.#..#.#.#.##..######.#.......###.###.#..#....#.##.#####.#.###.##.####.#.##..##.##.####.#..
+##.#...#.....#...##.##.##....########......#.#.#...#.#..#.#....###...##.##...........####.##.##..#.#
+####.###.#.#...#.##....#.##..###..#.#.#####..####.#.#..#..#....#...#..#...##...#..#.###..###..#.#.##
+#.#..#..#.###....##.#..##.#..#...##..##..#.#.#.#..#...##.######..#.#..####.#.###..####..##...#.#...#
+.###...#...#####...#.#...#.##..#...###.##.###...#..#.#.#.#...#.##.##.##.##.##...#...#.###.#.#......#
+#.......#.#....####.....#..#.#.#..##.#####..##..#..###.#..#..##...####....##.#.#..###...#.##.#.###..
+#.#..#.#.##.#.#####.#######.#####.#..###..#.#.......#.##...#..##..##....#.#..######.....##.##..##.##
+#####.#....######.....##.#...#..##....#...###.##..#..##..###.###..###.####..#...#######....######...
+#####.........#....#....#..#####.###.#..#.#....##.##..###..#..#.#...#.##...#.#..##..#.#.###.####.#.#
+...###.#####.#.##..###.....#.#.......##...#....#.#.##.#......#.#...#.#..#...#.####.######.##...##.##
+#...#..#..#..#...##.#.....#.#.##..####..##.#..#.#.#####.#.##.###.#....###...######........#..#..##..
+..##.......##.##.#....###.#...#...#.##.###..###.#..####.#.######.#..#######.......#.##..#.####...#.#
+......##.##..#####.##....#..#..##.#...#...####..##...##.##.#....#....#.#.###.....##..##.#...##....#.
+####...#......#.#........##.#..#...#.#.###..#....##.###.#..#.#.##.##......#.#...#.##...##.###..#.###
+.##....##..##.########.##..##..#.#.....#..#...#.#.#.#..#.##..#.##.#..#.#....####......#..#...#.#.#..
+.##.#...#.##.##.#.#..###..#.#...##.#.#.#.##..#..######..##.#.##....###.#....##..#.###.##.##..#...#.#
+..#.#.#...#...###..##....#.##..#..#...#....#.#...#####...##.####.#.#...#..#.##.###...#...#..#.##....
+...#.####.###.#...#####..####.####..#.##...########...#.#...#.##.#.#..##.#..#..##.###.#####..##.##.#
+##.#.#..##.###.##.#......###.#..#.#..#.#...#.#.#...#.##.###.#####.##..##...##.#..#..#.....#.###....#
+......##.#..###....#.#####.###.###.###...#.....####.###.........#....###.####.#.......#..#........#.
+...####.##....#.#.#.#.##..#..#.#..##....#...##..#...#.#..#.####..#.##.##.##......###..#...####..#.##
+##.#.#####.....#...####.##.#.#.####.#......#.######...######.##.######....##..######..##.#...##.#..#
+..#.##.......#.#####.#......###.###.##..####.#.###....#.###.#..#..#########..#..#..##.##.#....#....#
+....####...#.#.#...####.#.#..###...#...#..##.##..####.#.#..##.#.#.#.###...........##..##..####.####.
+#.#..###..######..##.##..#...#.#####......#.....######.##..#.#####...##..####.###.#..######...#.###.
+..#####.#..#...#.####.###.#..##....####.#.#.#.#.##.####.#.##.###.###...#..#...#.##..##...#.....#....
+..#.##.#..##....####.#.....##.##...##.#.#.####.##.#..####...###..#.#.######.#.###..#..#...#....##.##
+#...##.#...#.###...#.##...#.#..###.#####.#....#########....##.#..###..##......#.#.........#.#...##.#
+##..##.#.#...#..#..#####..#.#....#...###.##..#.####..#......##..##..##..#....#..#####.#.#.####.##..#
+#.###...###..#.......#.#.##.##..###.####...##.##.#..#.#..#..#.###...#..######......##...##.##.#..#.#
+.####.#...##.#..#...#.###..##.#..##.....###..###..##.####...#....#######.#.############.##.....##.##
+#..####.#..#........##.#.#.#####.#.#.#.#.##.#..#...#..##...#...#.#..##.###.#.#######.#.#####..#.###.
+#######...#####.#.##..####.#......##.#..#.###.####.#......####.#.##.#..##...#.....#.##.####.##.....#
+#.....#......##...#.#.##.####.######...#.....#..##..##.####....##..##..#.#.##..###.##...#.##..#..###
+....##.#..#.#..##.####.#.##..##.#.##.##.#..##########.#..##.....##....#.##.#...#.#..#..#..#.#.#.###.
+#......###......###.#.#.#..##....##..##..##.#..#.#.####.####...##.#...##.####..#.....#...#.#.#####..
+###..###.#...#..###.#......####.##.#.#.###...#..........##......####.###.###.#..#.....#####..####.##
+..#.####..#...##.###...####.##.......#.##.##.#.#.#.##....#..###.....#....###.#..#...######.#...#..#.
+#..#..#.#..#...#.#.###.####.##........#.##.####..#..############.#.###...###.#######.#.#....#...###.
+#.######.###.##.#..#####.#.#....##.#.##..#######..##...##...#...##..##...#.##.##.#####...##.#...##..
+##.###.###..##..##.#.#.##..#...#.#...##.#.........#.#.#.......###...#.##..#.##.#.##.####...##...###.
+..#.##..####.##...##....###.#...#..#..##.##..###..###.###...#.#.#.####..#.#.##...#.#..####...#..##.#
+#.#.#..#....#.#.#.#......#..#..#...#.#...#...#..#..#.##..#..#....#.##..#..#...##.######..#..##.#####
+.#..##..#.#...#..#..##....##.....#....##.#..######...##.##.......#.#.....#####.####.#.##.#.#.##.###.
+##.#..##.#...#..#.####...###..##.#####....#..#...#.##...#.#..###...####.#.##....#..#.#.##.#..####...
+#.#######...##.####..#...#...##.#.###..#..###.#.#..#.###.#.##.#.###....#.##..###..#.#.########......
+###.##.###.#...##....#.#..##.###.#..#.#.##.#.##....#.#####...###..###..#..##..#..#.#..#####.###..#..
+.###.###.##..##..#######.##########.#.###.#.#.#....#..#.###...##.##.....#..#....###.....#....##...##
+##...###.##.##....#.#....#####..#.######.##.#########..#.#...#.##....#.####.#.###.##.####.#.#.#####.
+###.###.....##.###.#..##.#...#......#.###.#..##.#...###..##.#.#.#...###.#.#...##..##....#####....##.
+#.#..#..###.##.##.##....#..###.#.###..#######.#...####..#####..#.......#..#.#.##.#..##..#.####..##.#
+..##....##...###.###...#.###.....####.#..###.#.........#....####.#..#.#.##...#...###...#.##.....###.
+.#..#.##.#.#.#.#.#..###.#..#.#.#######.####.###..#.#.##.......##.#...#...##..##.##.#.#..##.###.###..
+#.#..#...#...###.#.#....#..#..###.#####.#.#.#..##.#.#........###.#.#...#.....#..###..##.##..###..#..
+....#.#..#..##..#....###....#....###..##...#.#....#.###.####..#.#.##.####.#..#..##.....#.##.#...#.#.
+...#..#.#.#..#.###...###...####..#....###.##.#..###.##.#.#.#.##...#...#.#...##....#.#.##.#.##..#.#..
+##.#..###...#...##..#....###.#.##....##.#.##.#.##....####..#...#.#####.....#.##.#..#.#.###.#....#..#
+#.#.##..#..##.##..##.##.#####.####..#..#..#....###.##.#..#####.##.#####..######.#...#...#..#.#..###.
+..#.#......#..##.#...#.#..###..####.##.##..#..#####.##....#.##.....###.###........##.......##.#.####
+##..##.#.#.#..##..#.#.#..##.#.######...##..##...##..#####.#...#.#.....###.#...##....#...#.#.#...###.
+#......#.###.##.#####..##.#..#.#...######....#..#....#...#####.#.#.#.#.#...####..#...#.....#..#.#.##
+..##.##..####...##.#...##...#####...#...#.##.###..#....####.#..#..#.####.##..##.#..####..#.#..####..
+#####.#...#.##..##.#..####.#.#..#.#....#.####.#.####..#..####...#.#..##.#.#....#####..#..####..#...#
+..#.......##.#..##.#..#..#.######.#...#.....###.###.####..#.#....#..#...#.#..#..##...#.##.#######.##
+#.##..##..#.#.#####.........###..##.#.#...###.#.###...###.#...###..##..#.###..#.#.#....####...##....
+##....#.##.##.#..###...#.#.##..#.#......#...#.#.#.#.#..###.#.....#.##.##..#.###..##..###.##....#####
+...#.#..#...#..##...##....##....#.#..###..#....#..#.#.###.....##....#..#....##.###....#.#..#.#.#.#..

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);
+}

diff --git a/20b.c b/20b.c
new file mode 100644 (file)
index 0000000..90e7524
--- /dev/null
+++ b/20b.c
@@ -0,0 +1,110 @@
+#include <stdio.h>
+
+#include <uthash.h>
+
+struct point {int x; int y; int gen; };
+struct entry {
+       struct point p;
+       int c;
+       UT_hash_handle hh;
+};
+
+int key[512] = {0};
+
+void add_point(struct entry **board, int x, int y, int gen, int 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);
+}
+
+struct entry *get_entry(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);
+       return e;
+}
+
+void del_point(struct entry **board, int x, int y, int gen)
+{
+       struct entry *e = get_entry(board, x, y, gen);
+       if (e != NULL)
+               HASH_DEL(*board, e);
+}
+
+int get_point(struct entry **board, int x, int y, int gen)
+{
+       struct entry *e = get_entry(board, x, y, gen);
+       if (e == NULL)
+               return key[0] == 1 ? gen % 2 : 0;
+       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);
+       return key[r];
+}
+
+int main()
+{
+       int c;
+       int i = 0;
+       while ((c = getchar()) != '\n')
+               key[i++] = c == '#' ? 1 : 0;
+       if (getchar() != '\n')
+               return 1;
+
+       struct entry *board = NULL;
+       int x = 0, minx = 0, maxx = 0;
+       int y = 0, miny = 0, maxy = 0;
+
+       while ((c = getchar()) != EOF) {
+               if (c == '\n') {
+                       if (x > maxx)
+                               maxx = x;
+                       x = 0;
+                       y++;
+               } else {
+                       add_point(&board, x++, y, 0, c == '#' ? 1 : 0);
+               }
+       }
+       maxy = y;
+
+       int r = 0;
+       for (int gen = 1; gen <= 50; gen++) {
+               minx -= 3;
+               miny -= 3;
+               maxx += 3;
+               maxy += 3;
+
+               //Calculate r immediately all the time, saves 25ms
+               r = 0;
+               for (y = miny; y<maxy; y++) {
+                       for (x = minx; x<maxx; x++) {
+                               int nc = evolve(&board, x, y, gen-1);
+                               r += nc;
+                               add_point(&board, x, y, gen, nc);
+                       }
+               }
+               //Delete old items (saves ±1second, 160k instead of 3.6 elems)
+               struct entry *e, *tmp;
+               HASH_ITER(hh, board, e, tmp) {
+                       if (e->p.gen == gen-1)
+                               HASH_DEL(board, e);
+                       else
+                               break;
+               }
+       }
+
+       printf("%d\n", r);
+}

diff --git a/20e.txt b/20e.txt
new file mode 100644 (file)
index 0000000..8fa4bd4
--- /dev/null
+++ b/20e.txt
@@ -0,0 +1,7 @@
+..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..###..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#..#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#......#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#.....####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.......##..####..#...#.#.#...##..#.#..###..#####........#..####......#..#
+
+#..#.
+#....
+##..#
+..#..
+..###

diff --git a/20e2.txt b/20e2.txt
new file mode 100644 (file)
index 0000000..00f88c0
--- /dev/null
+++ b/20e2.txt
@@ -0,0 +1,102 @@
+#.#.#.#.#......#.#.#.#.##..#.##.##..#..##...#.#.#.#...##.##.##.###....#..#...#.#..###.#...#..##.#.###..#..####.###...#.#.#..##..##.##..##..###..#....#.#....#####.#...###...#.#....###...#..##.##..#..#.##..###..#.##.###..#.####...#.##.....#.###...#.##.##.#.#######...#.###..##..##..#.#.#.#####...#....#.....##.#.#...##.######....#..#......#.#.#.#.##...######.#.#####..#####..#.#.#.#.###.#.#....#..##..#..#.#.#..##....##..#.#.......##...#..####.####.#.#..#.###..#...#......###...#...#.##.#.####..#.#....###.####..#.
+
+.#.#.########.##.#...##.####...##..#####...##..#.#.###..#...#.#.##.#.....#..#.###...##..#.###.###.##
+.######.#..##.##...#.#.####.#.###..#..#.##.##...##.#...##..#.######...##....###...###..#.#.##.##....
+..######.#.#.##.#.##.###.##..#####.####..#......#.##.###.#.#.##...#####.###..###...#..#..#..##.#....
+###..##.#...##.#.#...######..#.#..##..##.#.##.#.#.#.##.#..####.#.#.##......#.#.#...#.##..#.###.###.#
+#.#.#...#..####...#.#..#.##.####.#..#..###########...#....#.#.##.###..#####.#.#.#.###...##..####.#..
+#.#..#.##.#..#..#..#....##.#.#.#...#..###.#.##.##.#.#.##.##..#.#.####.#######....###..#.######.#.#..
+......###..#..##.####.##.##..#..#.##.##.#..#...###...####.#..#...###.##.#.#####.....#...#..#...####.
+####..##.###.#...##..#.##....#..##.##..####.#.#.####.##..#..#.....#.###......#.#....#.#.....#.#..#..
+.###.####.#..###..#.#.#.#...##.####.#..#..##....#...###.#.#....#..#######.###.....#.#.#.##...##.#..#
+##.#......#.##.###.#.##..##.##..#######.###..##..#.#####..#.#..#.#.#..#..##..##.##...#####.#.##.####
+.#.###....##.......#######..#.########..#..##..#.####.###..#..###.##..#...####.#.#..#.##.######.#..#
+..###.#.##..##.#....#..#.####.....#.#..#..##.##.###..#.###.....##..#.##..#..#.#...#...#.#########.##
+..#.#.#.#..#...#.##.#.##.#..#...##.#..........#.###.##.##....#####...#.#####.###.#......#..#.#.#..##
+#....#..#.#.#.####.#####.#.#.####.###......#.....#.#..######....##....#.##..##.##...#.#####.##..##.#
+#.#....#####....###.###.#.#...#.##.#..........#....##.#..##..##.####.##.#.##....##..#.#.##..##.#.###
+..####...####..##.#.....#........#.#..##..#.#..###.....####...#...#.###....#....##.#..##.#.##....##.
+...#.###........####...#...##..#..##.#.######...#...#.#.#...###....##..##.#..##.......###.##.###...#
+##.#####...#.#.##.##.#...#.....#.##.########.....#.##..#.####.##...#......####..#.#..#..#...#.......
+.....###..##.###.#.#.#.....##.#.####...#..######.##....#.##.#.#.#...##.####.####.##....##.#.#.###..#
+.########..#.#.#.##..#..#..#.#..#..#.#.##.###.###.#...#.#..#####..##.###.#.##..###.###.#.#.####...##
+###..##.##...#...#.....####.#.#......##.####..#......##..#####.#.....#.###.##.....#.##...#...#...###
+#.#.#.....##.##..#..#.###.#..##..##..#....#...##.....##..##.####.#######.....#........###..#.##.#.##
+.#....##..###.#..###.#...###.#...###...#.#..####..######......##.##.##..#...#..#####.####...##..#...
+####.#..#.##....#.#.#...#.#.#####.###.#..##.#.###.....#..#.##......#.##...##..##...##..####.#...##..
+....#.####..#..##.####.#######...#..#########.##.##..#..#.##.##.#.###.##.#.#....#####.###...#.####.#
+..#.....##...###..#.##...#.#...###...#######.##..####.##.##..##.#########..###........##....#..#..#.
+.#.##.#.#.##.....##.#.##..###.###.#.....###...###..#.#.#####.##.#....##.#.##.##.##.#.#....#........#
+.#.#..#.#............#....###.#...####..####....#..#.##..#.##..#####...###.######...##..#####..###..
+###.#..##.#...##..#.#..#..##.#..#..#..#..#####......##.##..#####..#......#..#####.##.####......##.##
+##...#...##.#####..#...#.#.....#.#..###.#..#.####.....#.....#.#.#.#.###.####..#.......##.#....#..##.
+#...#.#..#####..###.........#.####.###..#....###...#......#...#.#..#.....#####..#.###...#.#...#.....
+###....#..##.##.####.###.#.#.##.#.#....##..#....##..#.#.###..######.#.#.#..####.##...####..##..##.##
+.###...##.#.#####.#...#.###..##..###....#.##....#...#.#..#...##.###...#.#.#.#######......###.###.#.#
+.#.#.#.....#..##..#.##.#..#.....#.#.######..#.##.#....###.#....#...#####..#.######.###....###...####
+####..#....########...#..##..#####.#...#.##..##..###...###.#####....##.#.#..#.###.#.#..#.#.#..#.###.
+.##.##.##.#####...#..#..#.###.#.#..###.#......###.##.#.###..#####.#.#...#.###.#.#.###.##.#...#.##.#.
+#.#.##....#####...##.#.##.######.#.#.##.###.#.......###......##..###.#.###...##..##.#.#...#..##.####
+##.#....#.##.#..#...#.#...#.##......####.#.#..#..###.#####.#...##.####...#..###.##.#.##..###.####.#.
+#.#..#.#.##...##.....###.#.#.#..##.###.#######........###..#.....####.#.##.##...####.##.#.##.###.###
+##...#.####..#...#...##.#.##..#.##.###..#.##..##......#..#.#...######..#....#.######..######..####..
+.....#.#.......####.....#..#.####.#...##..##...#....#.########.#.#.##..##.##..####..##.####..#.#.###
+.#..#.#....#..##..#....##...###........#.#..#.##.####....###..#..##...#..##.#.#.###.#.#.#..#.####...
+#.#...###.#....#...##############...###..##...#.#.##..#..#....#...####....##..###.##..##..##.#..##.#
+##..#....#...#..#..##.#..###....#.#.#.###.#.#.###..###..####.###.#.#.###.#..###.#.###.#.##...#.#####
+#..#..####.....###..#.#...##.######..####..#..#....#####...#...#..#..#.....#.##.####......#..##.###.
+##.##..###.###.#..###...#.####...#....#........#..#..##..##..##.#.##....#.......#.###...#..###.#....
+#.##.#.#..#..###..###...#...#.###..####.#.#....#.#.......##...#..#......##....##.#####.......#...#..
+....#..#..##.##.#.##.#.##..#.##..##.##.##.##..##.######.##..##.....#.###..#...#.##.#.#.####.###.###.
+.###....##.##..##..#.###..##.#..#.#.##..##.###..##.###..#......########.#####....##...#...##...##.##
+.###.###.#.#######.......#.#.#.##.##..#.#.#.##..#.##...##.##.#...##.#.#######.#..#..##..#.#..##.##.#
+....#.###.#.##...##..#...#...#..##...#.##...##.##.##.#.#####.....#.#.#.##..####.####.#..####..#..##.
+##..#.##.#######.#.#...###.#....###.###..##.###.##.##.#.#..##.....#.##......##.###..##.#.#.##..##...
+...#####.#.##.#..##....##.###.##.#..##..###......#.#..####.##...##.#.###...##.....#..#..###..#####..
+.#####.#.#..#....####.#####.#..##..#.#####.##..#.#.#..##...#.#..######.###..##....###.#....###...#.#
+..###......##.##.#.##..#..##.....##....##.##..##.....###.#..##.#.#######..#...####..#.###.#####.###.
+##..#.######.####..#.#..###.#..#.#..#######.#...#...##.#.###.#.##..##.#......##.#.#..##.#.#.#.####..
+..#.#.####.##..##.#.#.#..####.#.##...###..#.##..#.##.###..####......#..#..#####.#..#.#####.#.###.###
+#..#.#.....#.#...#..###.####..##..#....##.#.###..##..#.#..#.####...##..##..#..####...#########....##
+.#.....#......##.#..#.####.######..#.#.#.#.##...#..#..#...#.###..#....#..#.#...#####..###.##...#.##.
+.####....#.###..#..###.#...#..###.#.#..#......###.##.#.#.#.#####..#######..####.##.....#....#..##.#.
+...#.##.#.#..####.#####..##..#.##.###.#####..###...##...##.##..#.####..##.#...####...#..##......###.
+###...##.....#.###...##.#..#.#......##..#...##.#..##.#.#..#.###..#..#####..#.###..#.#...#..##.#.#.#.
+##.##.##.#.#.#.####.##..##....#.####.####.####...##.####.#....###....###.###.#..#.####.#...####.#.#.
+####.###...####.#.##...#...##..##...##....#.#.####..#..#.....#.....##....###.....###...#...##.#.###.
+######..#..#####...#..#..######.##...#.###.#....####..####.##.#.#..#.#.####.##.####..##...####.##.#.
+##....#.#...#..###..#.##.#.#...###..####.....#.##.#.####..#.##....##...##########..##...###.#.###.##
+..#.#######....#####..##.####.##.#####..###.#.#..####.....###########...##.#....#.#..##.##.###..###.
+##.....##...#..#....#####...#...#..#.#.#.#.####....##...####.#.#.#.....#.#..........#.###..##.#.#.#.
+.#####...#..#.##..##.#...#.#.##..###..#.#....#...#.#.#..#.#..#..#.###.#...######.#.####..##..##.#...
+..#.#.#.##..#.##..#.###......###..#....##.###.#..###.#...##.#.#.....#.##....##.##.##.#...####.####.#
+##..#.##.##.##.#....##.#..#..#.##.###..##.##.#.#.#......####..##.#.#.###.....##.....#.##..####..##.#
+.###.#.##.#..##.##.#.###.#.##.##.#####...#.#..#..#..#..#.####..#.######..#.#.#...#..#####...#.#..##.
+..#...#.####.####.####...#..#..##..#.##.#.#..#..####..#...#.####.#.###.##..#......#..#...#..#..###..
+.#..#.###.......#..##.#.#..##..#.#..#..##..#.....####.###...#..#.###.##.#..#.#..##..#...##.##.##....
+#....##..#...##.###.#......##..###...##.###..##..###.####.....#...###..#.#...#####.#.#.######..#..#.
+##.###.....#...#.#..##.#.#..#.#....#...#..##.######.###.#.####.#.######...#.#.#....##.##..#...#...#.
+.......#..#.##..#..##...#.##.#####..###.####.###.#.#..###....#.#........#..#.#.#.......####..#......
+#####...##.######....#.#.##.#..##...#..#..#..#...#..##.###....#.#.......##...#.###.###..####.##.###.
+.###.##.#....#.#..#..#..##....##...##.#...##....#......#####...####.######.#.#.##.##..##.#.#.....#..
+..#.##..#.####..####.##.#...#..####..##.....###.#...###..#.###.######.#.#.##..#.#.#####.#.##.#.##...
+.##.###########.#..####.#.####..#.####.##########..#.##.#.#.#..#.#..#.#####.....##.#...#.###..#.##..
+...###.#.#..#.#.#.#....#..##..####.##...###.#....#.#.####.#.#..#..####...####..###.##..######.##....
+#..#####.#######.#.###......#..#.#.##.##.###.#.##.#...#....#.#####..###..##.#.#####.#..#..#.###.#..#
+#.####..#..#.......###..#..####.#.#.#..#.#..#..#.#...#####.#.......####.#.#.##.##.#..#..##.#....##.#
+###.###...#..#..##.#..#.#..#..#####.#.#####.....#..#..####....##.##.....#.....#.###.#.#.#.##.#.####.
+.#.##.#.#..#.#####.#.##.#.###.#...#..#..#.#...##.#.##......#.#.#####..#......###.########.#..#.###.#
+#.##.....#.####..######..##..#...#.....##..##..#.#.##.###.#.#.#.#.....#...#.#..###..##..##.######.##
+####......#.##..#.##..##.##..#.##.....#####...#.#...###.#..##..###.##.###..............##.#.#....#.#
+###...##.##.##.####....####..#...##...#.####.#....#.....#####.....##...##..###.#...##.#...##.##.##..
+#.#.####...###.....###.###.##.###.....##.##.....###..###..##......##..####.#..##.#.##....##.#.#..#.#
+####...###.#####.#####.......##..##.###..#..##.##..#..###.#..#..###.....##..##..##.##.#..####.#.#.#.
+######....#.##.##.#.###...##...###.###.#.##.###....##.#......#.##.##.#####...#..##....###...#..##...
+..#...........##..........#.##.#.##.##.###...##..##.#####.#####.#...##..####.....#.##....#..#.###.##
+.#..##.#...#.#####...##.#.#.###.#.#..##..#..##########..#.#...#...#...##.##.#...##..#.#.#.##.#..#..#
+..##....##.#..#...#.#...#.#....#..#.#.#####.##.#......#...##..######..##....####..##.##.##.###.###..
+#.......#..############...##....##...#.#....#...##..###..##....####..##....#...##.###...#..#...#####
+..##..##..#.###.#.##.#.####.#.##...#.#..#.#####...######...######.####...###.#.#.##..#.######..#.#..
+###.#....#####..#.##.##..###..##.#..#.#.#.##.#......#..#....##.#.#.###..#.#######.###..#..#..#.###..
+#...#.#..#.####.###..##.#.#####...#.#.##..#..#.#####.#.###.##.####..#..##.#.##...##...####.#..#.###.
+...#.##.##...#.#...####....#..#####...#.#.....####.##.######.#.#...#...###.##..##.#.#.#..#...###.#..

diff --git a/Makefile b/Makefile
index 7bd5349..a350a35 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -1,9 +1,9 @@
 CFLAGS:=-Wall -Wextra -O3
 LFLAGS:=-f
 
-BINARIES:=$(foreach num,$(shell seq -f '%02.0f' 1 16),$(num)a $(num)b)
+BINARIES:=$(filter-out 18a 18b 19a 19b,$(foreach num,$(shell seq -f '%02.0f' 1 20),$(num)a $(num)b))
 
-all: $(BINARIES)
+all: 
 
 clean:
        $(RM) *.o a.out $(BINARIES)