commit 6762b968d50545722de1e399ce1db7a7a3a679e8
parent 181394b2c5e14fdd2b82face143c37cf9bb6148e
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Sun, 20 Dec 2020 09:03:49 -0600
Add 2020 day 20
Diffstat:
A | 2020/day20/input.txt | | | 1728 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
A | 2020/day20/main.go | | | 318 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 2046 insertions(+), 0 deletions(-)
diff --git a/2020/day20/input.txt b/2020/day20/input.txt
@@ -0,0 +1,1728 @@
+Tile 2957:
+#..##.#.#.
+...#......
+.#....#...
+....#.#...
+#.......#.
+#........#
+.....#..#.
+.....##.##
+#......#..
+###...####
+
+Tile 3499:
+#.#.#..###
+##.#...#.#
+..###...##
+...##...#.
+...##..###
+####..#...
+#.#...#..#
+##....#...
+#..#...#..
+.####.###.
+
+Tile 3583:
+.#######.#
+.....##...
+#........#
+####..#.#.
+..#...#...
+.#.##..#..
+.#.#..###.
+.........#
+...#...#.#
+.#.#.##.#.
+
+Tile 2309:
+.######...
+.#..#....#
+#...##....
+#.#....##.
+....#....#
+.##...##.#
+###.......
+###..#...#
+#...#.#.##
+.##.###..#
+
+Tile 1297:
+#..#.####.
+.#.#....##
+..#....#.#
+........##
+.#....##.#
+....#..#.#
+.#...#...#
+.....#.#.#
+#...###...
+##..#.####
+
+Tile 3779:
+#...#..##.
+.....###.#
+#.##..##..
+.####...#.
+#.....#...
+#..###.#..
+#....#.###
+#......#.#
+..#.##.#..
+.###.....#
+
+Tile 1471:
+#.##.....#
+...#.##...
+....#.####
+#.#.....#.
+..#.#...#.
+#.#...#..#
+.#.......#
+...#..##.#
+##...###..
+.######.#.
+
+Tile 3803:
+##..###..#
+#..#......
+#.#.#....#
+.#..##..##
+...#.#.#.#
+...##.#...
+........##
+........#.
+.......###
+#.#.####.#
+
+Tile 2473:
+#.#####.#.
+##.......#
+#.##...##.
+..#....#.#
+#.#...#.##
+......#.##
+#..#......
+#.#...#.#.
+#...###...
+#...#.##..
+
+Tile 1193:
+#..##...#.
+....#.#..#
+...#....#.
+.#........
+#.#....#.#
+#...#.....
+.###...#.#
+#..#..#.#.
+#.##....#.
+#.##.###.#
+
+Tile 1879:
+#..#..##.#
+##....#...
+...##....#
+#.##..#.#.
+#..#.#.#..
+#.###.....
+#.##......
+#..#......
+.......#.#
+.##..##..#
+
+Tile 1049:
+######.#..
+#.#...#...
+#.#.....#.
+###.###..#
+###...#..#
+##.##..#..
+#......#..
+...##..#..
+.###......
+#.#...####
+
+Tile 2917:
+#..##.###.
+........##
+#..#.#.#..
+#..#......
+.......#..
+#.#.#..#..
+##....#.#.
+......#.#.
+##...#####
+##.##..#.#
+
+Tile 1619:
+.#####.#.#
+.....##...
+##.#......
+..##..#.#.
+.#.......#
+#.##......
+#####.....
+#...#.###.
+..#....#.#
+#..#.#..##
+
+Tile 1663:
+#.###.##..
+####..##.#
+..##...#..
+.###...##.
+.#.##.....
+........##
+#.#..#..#.
+#..#..##..
+#.###..#..
+##..##.###
+
+Tile 3571:
+..#.##.###
+.##..#..##
+#...#...#.
+#.##.###.#
+......#..#
+#..####.##
+#.##...###
+.#.#.#...#
+....#....#
+##.....##.
+
+Tile 2969:
+#..#...#.#
+.#...#..##
+##..#..###
+#.....##..
+......#...
+...#.....#
+#.......#.
+#..#..##..
+#.#.##.###
+#..###...#
+
+Tile 2657:
+.###.##.#.
+#.#.....##
+##....#.##
+.#.#..##..
+##..#.##.#
+#.....#.##
+#..##..#..
+#.........
+#.##.#..#.
+..#..#.#.#
+
+Tile 1693:
+.###.#.##.
+###....#..
+##.#..##.#
+#.....##.#
+.#.##.#..#
+...#.#....
+#.....#...
+#....##...
+##.###....
+#.#.#..#.#
+
+Tile 3257:
+.####.#...
+##..##.###
+#.........
+.......##.
+......#..#
+###.....#.
+....#####.
+#####...#.
+###....#..
+#.#.#.##.#
+
+Tile 2707:
+..#...##.#
+.#.....#..
+#...#...#.
+##...#.##.
+.##.......
+#.##......
+.##.....#.
+##........
+...##..#..
+.#.##.###.
+
+Tile 1723:
+#..##.##.#
+#.#.....#.
+...#.##...
+#.....##.#
+...#......
+.#.#....##
+#..#..#.##
+..#......#
+.##...#...
+##...#.#.#
+
+Tile 2333:
+#..#.#####
+##.#..##.#
+#........#
+...#.#..##
+....#....#
+.####...##
+##...#..##
+##...#....
+#.....#..#
+#.#..#...#
+
+Tile 2909:
+##.#....##
+#.#..####.
+.#.##.....
+#.#...#...
+..#..#..#.
+.....#....
+#...#.####
+#.....#..#
+#.##..#..#
+#####.#.#.
+
+Tile 1637:
+##.##...#.
+.#.#..#...
+...#.##.#.
+#...#..#..
+.###.##..#
+.#......#.
+........#.
+.........#
+#.......#.
+..#...#.#.
+
+Tile 2129:
+.#....#.#.
+......##.#
+....#..#..
+#.#......#
+.#.......#
+..#....#.#
+#..#......
+#..#..#.##
+#.#.#.#.##
+#.###.#..#
+
+Tile 3083:
+#####.#.#.
+#..#.....#
+#......#..
+.#...###.#
+#.####..##
+#####....#
+#..##.....
+.......#.#
+#........#
+#.....#.#.
+
+Tile 3929:
+##..##...#
+#..#..#...
+..##...#.#
+#......##.
+..#.#...##
+..........
+...#...##.
+##......##
+#..#...#..
+#.#.#.##.#
+
+Tile 2239:
+...#.#..##
+.....##...
+#..#.....#
+..#.##...#
+#.#....##.
+#.##......
+.##......#
+.......#..
+..#.#..#.#
+#....#..##
+
+Tile 3793:
+###...##.#
+...##.#..#
+.....##.#.
+..........
+.##.....#.
+.......#.#
+##...#...#
+##....#..#
+###...#...
+#######..#
+
+Tile 3581:
+##..###.#.
+#........#
+.#...#...#
+.#.#...##.
+#....#....
+........##
+.#..##.#..
+.#..#.#.#.
+....#.#..#
+#.##.####.
+
+Tile 1553:
+#...##.#..
+##......#.
+##...#.##.
+.#..#.####
+#...##.#.#
+...##..###
+......##..
+#.##.#..##
+...##..##.
+#..#..##..
+
+Tile 2203:
+.#....###.
+..#.#....#
+..#..#...#
+#..##..#.#
+#.......##
+....#.....
+#.#......#
+...#....##
+#..###..##
+..#..#....
+
+Tile 1847:
+..####....
+###.......
+#..#..#...
+..#....###
+#....#...#
+#.#.#....#
+.....##...
+....#.#..#
+##.#...#.#
+..#..####.
+
+Tile 1367:
+.##..#..#.
+##......#.
+##.#...#..
+........##
+..#..###.#
+#...#.....
+....#..#.#
+..#..#..##
+..####..#.
+##....##.#
+
+Tile 2633:
+#.##...###
+###....###
+#...##.###
+##........
+#..##.....
+#.##.##...
+.#.##.#..#
+#.##....#.
+.........#
+#####.##..
+
+Tile 1697:
+#.####.###
+.#.###..#.
+##....#.#.
+#..#......
+.#..#.....
+#..####...
+##...#....
+....#..##.
+..#..#.#..
+######..#.
+
+Tile 1571:
+.#####...#
+#.....#...
+#..#.....#
+..#.#..#.#
+.####...##
+...#.#.###
+#....#...#
+#..#.....#
+.........#
+....###.##
+
+Tile 3889:
+...#..#..#
+......####
+#.#.##...#
+....#.....
+##.#...#..
+..#....#.#
+..#.#....#
+.###.#..#.
+..#.####..
+...#..####
+
+Tile 1039:
+...#......
+#...#.....
+##........
+#...#...##
+..#.....#.
+.##......#
+.....##..#
+..#..####.
+#........#
+.#..###.##
+
+Tile 2339:
+#..##.##..
+..#...#..#
+#.....#..#
+..#.##.#..
+###......#
+##..#.#..#
+....#..#.#
+#....#...#
+#....#.#..
+####.#####
+
+Tile 1583:
+.###.##.##
+.....#..##
+..###.#...
+..##...#.#
+..#....#.#
+#....##..#
+........##
+#...##.#.#
+...#.#..#.
+.#.....#.#
+
+Tile 3881:
+.#..####.#
+..#..#...#
+..#...##..
+#.........
+.....#.#..
+..#.....#.
+#.##......
+...##...#.
+..#....#..
+#...#.###.
+
+Tile 1123:
+.####.#.#.
+##....#.#.
+#..#.###.#
+.####.###.
+..##......
+##.#......
+.#..##....
+#...####..
+.#..#.#..#
+..##.#.#..
+
+Tile 2243:
+..#...#...
+......#.##
+..........
+.#.#..#..#
+#.#....##.
+...#...##.
+##..#.....
+..##.##..#
+#.#.....#.
+##...#.##.
+
+Tile 2063:
+#.....#..#
+.#.#.#....
+#....##..#
+#..##...#.
+###.....#.
+..#....#..
+#..#...#.#
+.........#
+...#......
+.#...#..##
+
+Tile 1621:
+..#.##.#.#
+##...#..##
+..#..##..#
+....#.....
+......###.
+#.#......#
+..#.#...##
+#.......##
+#......#.#
+.#..#...#.
+
+Tile 3331:
+#..####...
+..#..##.##
+..###.....
+..#..#....
+...#..#...
+#.#.#....#
+#....###..
+.###.#..#.
+#....#...#
+..##.##.#.
+
+Tile 1259:
+###.####..
+#.....##..
+#...#....#
+....##..#.
+##.#.##..#
+#.......##
+.....#...#
+......##..
+#.#...#.##
+.##......#
+
+Tile 3407:
+....##.#.#
+#.#....#..
+#....##...
+...##.#..#
+####....##
+.#....#..#
+#..#..##..
+#####..###
+##....#...
+..#.#..###
+
+Tile 1033:
+..#......#
+#....#.#..
+#.#.#.###.
+#.#.##.#.#
+.#.#..##..
+...##...##
+#####.....
+...#...##.
+####....##
+##..##.###
+
+Tile 3089:
+.#...##..#
+.........#
+#.#.....##
+....####.#
+.....#..#.
+.##.##..##
+#.....#..#
+#..#......
+#.#.#...##
+#.#...##..
+
+Tile 2297:
+#.#.#.####
+##..#.....
+#...#.....
+..........
+.....#....
+..#.#...#.
+.....#.#.#
+......##.#
+#..#...###
+.......#.#
+
+Tile 3259:
+.####.....
+.##.#..#..
+#........#
+.#.##..#.#
+#.###.#.#.
+#.#....##.
+#........#
+#.....#.#.
+#.......##
+#.#.......
+
+Tile 3457:
+#.####..#.
+##......##
+#....##.#.
+#.......#.
+######....
+.....#.##.
+..#..#....
+#..#####.#
+#..#...#..
+.#.##...##
+
+Tile 1423:
+##.#.#.###
+.........#
+..####.##.
+#......#..
+...#.#....
+#.#..##...
+#.....#.##
+.##..#####
+#####.#.#.
+.######.##
+
+Tile 2741:
+.#..#..#.#
+....##..#.
+#..#..####
+#...#...##
+#...##.#..
+#...#..##.
+##........
+#..#####..
+..##.....#
+##..###.#.
+
+Tile 3187:
+####.#...#
+.......#..
+#........#
+#..##..#..
+.##.#...#.
+..#.###...
+#..##....#
+....#.##.#
+#........#
+.###..##..
+
+Tile 1117:
+###.#.#.##
+.#.....###
+#....#...#
+.#.......#
+##..##..##
+##.##...#.
+##.#.#...#
+#..####..#
+..#..#...#
+.#.###.##.
+
+Tile 3271:
+.....#..#.
+......##..
+.###.#.#.#
+##..#....#
+#.#...##..
+.........#
+.#...#....
+.#..#.##.#
+..........
+.#.#....##
+
+Tile 3067:
+..#.###.#.
+..##...#.#
+..#...#.##
+#.......#.
+#..#.#..##
+..##..#.#.
+.....#.#..
+#.........
+#.#......#
+.##.#.##..
+
+Tile 1429:
+..#.##.#.#
+..........
+.#.##.#.#.
+##...###..
+##.#...#.#
+#.....#.#.
+##........
+##...#...#
+.....##..#
+##.#.###.#
+
+Tile 1801:
+#......###
+#.........
+#...#.....
+#........#
+#......#..
+#.......#.
+#..#......
+..#.#..###
+........##
+..#..#...#
+
+Tile 3853:
+###...#.##
+#...#..#..
+....#...#.
+#.#....#.#
+......#...
+#...##.###
+.#.#.#...#
+#..##.#.##
+....##...#
+#...####.#
+
+Tile 3109:
+..#...##.#
+#.#..##.#.
+#.##.##..#
+..#.##...#
+.....#..##
+###.#..###
+.##.#.#.#.
+...#.#.##.
+#..##..#.#
+#.##..####
+
+Tile 1301:
+.##..#.###
+##..#...##
+#...#..#..
+..#.#....#
+..#....#..
+#.#.#.#..#
+#.#....#..
+.........#
+.....#..#.
+#..#.##.##
+
+Tile 2017:
+....##.###
+#........#
+##........
+...#...#.#
+.......###
+.###...###
+......##..
+.#.##.....
+.#....####
+#.....#..#
+
+Tile 2621:
+...#.#.###
+###..#.###
+..#.#.#.##
+.......#..
+.#.......#
+#.#....###
+#...#...#.
+.#.#..#...
+#.#...##..
+####..#..#
+
+Tile 3697:
+...##..##.
+..#......#
+##..#.#...
+#....###..
+..#.#..#..
+##.#.##..#
+.#.#.....#
+#..#.....#
+##......#.
+##...###.#
+
+Tile 2711:
+##..###...
+#....#.#..
+##..##.#..
+#...#...##
+#..#..#...
+.#....#..#
+##.#..#...
+#.##.....#
+..........
+#.###..#.#
+
+Tile 3533:
+...#..#.##
+..#.#....#
+##.#.#....
+.#.#.#...#
+.....#..##
+##....###.
+##.##....#
+.##...#..#
+....##.#.#
+#.#..#####
+
+Tile 1907:
+#.######..
+#.......#.
+......####
+#.#.#.##.#
+..........
+......#.##
+#.#..#...#
+#...#..###
+...##.....
+##...#.##.
+
+Tile 2213:
+####.###.#
+##........
+#.....#...
+..#....#..
+.....#...#
+....##....
+...#.#..##
+....#.#..#
+##.....##.
+#....##.##
+
+Tile 1229:
+.#.#.##..#
+....##...#
+......#..#
+.#.......#
+..#.#.....
+#....#....
+#.##.....#
+.##......#
+##.#..#..#
+#..#..#.#.
+
+Tile 3797:
+#..##.####
+.##..###..
+#.........
+.......##.
+.##..#....
+#.#.##...#
+#....#...#
+#.........
+..#...#..#
+##.#...##.
+
+Tile 1087:
+##..######
+.#..#...##
+##.##.#.#.
+....#.....
+..........
+..####.###
+##.###.#..
+....#...#.
+#......#.#
+#.####.#.#
+
+Tile 2687:
+......#...
+.#.#...#.#
+#..#.#...#
+#...#.#.##
+.#....##.#
+##....#...
+#.#....#..
+##...#....
+#........#
+##.##.####
+
+Tile 1051:
+#.#####..#
+#.#...#..#
+#...#..#.#
+.#.##..#.#
+......##..
+#...##....
+........#.
+##.......#
+#......#..
+.#...###.#
+
+Tile 3739:
+##.#.####.
+#...###...
+.###...#..
+###.......
+.........#
+#....#..#.
+.....#...#
+..#......#
+....#.....
+#####.#.##
+
+Tile 2087:
+...#####.#
+.##.#....#
+#...#..##.
+#.##.....#
+......#...
+#.#.#..#..
+..##..#.#.
+#..#...###
+##.....#..
+.##.#..###
+
+Tile 2683:
+..#.....#.
+..#.#.#..#
+##.......#
+.#..#...#.
+#..#.#...#
+#...######
+#...##.#..
+##..##....
+#....#.#..
+.#####.###
+
+Tile 2137:
+###.#....#
+.....#..##
+..........
+..##...#..
+.#..##..##
+#..##..#..
+##..#.....
+...#.....#
+.#...##...
+##....####
+
+Tile 1031:
+#######...
+#......#..
+...###.##.
+.#...#.#.#
+##..#.#..#
+.#.......#
+.#........
+.......#..
+##..#.##.#
+#.##..##..
+
+Tile 2887:
+.....##.##
+.....#..##
+.##.....##
+...#.#.#.#
+#...#....#
+#......##.
+.........#
+.#..##..##
+#.#...#.##
+##...##.##
+
+Tile 2729:
+####.#..##
+#...##..#.
+#...##.##.
+...#.....#
+..#..#.#..
+.##..##..#
+.###.##...
+##........
+.##...##..
+#..##..#.#
+
+Tile 3517:
+#.#..##.##
+#.......##
+..#.#..#..
+.#.....#..
+..#.##.##.
+#.#......#
+##.#......
+#.#.##..##
+#.#....#..
+###..##..#
+
+Tile 3191:
+##...###..
+##...##...
+#..#...#.#
+##..####.#
+###...#..#
+..##...#..
+....##.##.
+##...##...
+#.###.##..
+.#..#....#
+
+Tile 1381:
+#..#.#.#.#
+....#....#
+#.##..#..#
+#.##...##.
+.#..#.....
+#...#....#
+#.....#..#
+####..##..
+###.##.###
+#.....##.#
+
+Tile 2111:
+.#.#.#..#.
+.....#.#..
+...#......
+##...##...
+##.#...#.#
+#.#..##..#
+.####....#
+...#####.#
+#.#.......
+#.#..###..
+
+Tile 3541:
+####.###.#
+..#.....##
+#..#.#...#
+.#.##.##.#
+.#...#...#
+..........
+#.#..#.#..
+#.........
+#..#...##.
+.#########
+
+Tile 1997:
+#####.#.##
+.#.#..#.##
+##..#.#.#.
+##.##..#.#
+##..#....#
+.#.##....#
+..........
+#.##...##.
+#.........
+#.#.##...#
+
+Tile 1597:
+####.#.#.#
+##.....##.
+##...#.#..
+......#...
+.#....#..#
+.##...#...
+#....#....
+......#...
+#..#.#..#.
+...#.##.##
+
+Tile 2347:
+##.#.....#
+#...#.#.##
+#..#......
+.#...#...#
+...#....#.
+#.#...#...
+#.......##
+#....#....
+#.........
+#.##.##.##
+
+Tile 3767:
+##.#.#..##
+....##.#..
+#...###.#.
+#.#.#.....
+#......#..
+...##..###
+.#...##.#.
+......#...
+..#..##...
+.#.#.#..##
+
+Tile 2003:
+...#####..
+#.#.#.#...
+#.#..#...#
+#.#..#####
+#...#..#..
+#.##.....#
+##...###.#
+#.......#.
+...#....##
+..#.###.#.
+
+Tile 1523:
+#...##....
+...#....#.
+.##.##.###
+#......##.
+.........#
+...#.....#
+#.#....#..
+###.....##
+##...#..##
+...##.##.#
+
+Tile 3079:
+...##....#
+.#..#.##.#
+#.##.#####
+#.#.......
+.#.......#
+...##.....
+#....#...#
+#...####.#
+#...###...
+#...#.#.##
+
+Tile 1069:
+........##
+.#..###..#
+#...#.....
+#.........
+.......#..
+..#..###.#
+#..#..#..#
+...###.#.#
+..##...#..
+#.#.##....
+
+Tile 2089:
+##...#..#.
+..#..##..#
+......#...
+.......#.#
+#.####....
+...#......
+#......#..
+#...###.#.
+...##..#.#
+##.##.###.
+
+Tile 3863:
+##....#.##
+.##......#
+#........#
+....##..#.
+.......#.#
+##..##..##
+..##.....#
+.###.#....
+#.#.......
+..###..##.
+
+Tile 2663:
+.#.#.##.##
+....#.....
+##.##...##
+..#.......
+##.#...#.#
+#....##..#
+#...#..###
+.....##...
+#........#
+#.###.#...
+
+Tile 1019:
+..#....###
+#..#.#..#.
+.....#...#
+....#.#...
+..#.#....#
+..#.##...#
+..#..#...#
+.##....#..
+..#....###
+#.##.##.#.
+
+Tile 3709:
+#..#....#.
+##.##.....
+#.......##
+.#.#...#.#
+.##.####.#
+#..#.###..
+#..#.#####
+#........#
+..........
+.##..###..
+
+Tile 3023:
+##.###.#.#
+..###....#
+#...##...#
+#........#
+.#.#.....#
+#.....#..#
+..........
+#..#.#....
+#...#.#..#
+#..#####.#
+
+Tile 3623:
+..#.#..#.#
+#.#.#....#
+......#...
+#...#....#
+#........#
+##..#.....
+#.##.....#
+..#.#.....
+..#......#
+#.##..#..#
+
+Tile 2161:
+.######.#.
+.........#
+#..#.#...#
+.##.......
+.....#.#.#
+......#.##
+#.#####...
+##.#......
+#.##...#.#
+#.#.#####.
+
+Tile 3037:
+##.....###
+...#......
+#.#.#..#..
+...#.#..#.
+.....#.#.#
+#...#...#.
+..#.#...##
+#....#####
+....#....#
+...##...##
+
+Tile 2539:
+#.##..##..
+.##..#.###
+#.#####...
+.#...##...
+##.###...#
+#.........
+#.....####
+.#.#....##
+#.....#...
+##.#.####.
+
+Tile 1361:
+#..###.###
+...#..#...
+.....#.#.#
+.......###
+#.#......#
+#.#...#..#
+###......#
+##.#....#.
+#...#.#..#
+#......#..
+
+Tile 1873:
+...#.#..#.
+###......#
+#.#.#.####
+#........#
+#..#.#.#.#
+..#.....##
+#....#..#.
+...#......
+..........
+##....#..#
+
+Tile 3701:
+.#..#.#...
+.#...#.#..
+####.#..##
+#.###...##
+#...###...
+#..#......
+.......##.
+#....#..#.
+##..###...
+.#.#.####.
+
+Tile 3557:
+##.#####.#
+####.....#
+..##......
+###.##..#.
+#####.....
+......#.##
+....#.##.#
+....#.#...
+..##.#....
+##.##.#.##
+
+Tile 2659:
+.#.#..#.##
+.#.....###
+##....#.#.
+#.##..#..#
+...##.....
+###.......
+#..#.....#
+##.#####.#
+..##.#..##
+#..####.##
+
+Tile 2269:
+#.#.#.#.#.
+#..#.#...#
+##..#.#.#.
+#....#.#..
+#..#....##
+.##..##..#
+.#.#...#.#
+#...##..#.
+#......#.#
+##.#.#..##
+
+Tile 3121:
+#...##..#.
+#.#.....#.
+..#......#
+.##..#..##
+##....##..
+##..#..#..
+#........#
+.###.####.
+##.....#.#
+#.#...#..#
+
+Tile 2939:
+..##.#.###
+...##....#
+#.#...#.##
+##..##...#
+#..####..#
+#....#...#
+#.#.......
+#.#...#..#
+#.......#.
+...#..#.##
+
+Tile 3967:
+.#.....##.
+#.#.#.....
+..#####..#
+..##.#..##
+.#...#....
+#.....#...
+....#.#...
+...##.#..#
+...##..#..
+##...#...#
+
+Tile 2113:
+#..##.###.
+........#.
+###..###.#
+.......#..
+#..##.#.#.
+..##...#..
+###.....##
+....#...#.
+##..##.#..
+...##.#.#.
+
+Tile 1871:
+..#..#####
+.#..#.##.#
+.....#..#.
+##.#....#.
+.##....#..
+#....#..#.
+...#......
+.#..#.....
+#..#.....#
+##.#.#....
+
+Tile 2531:
+..#.#..##.
+#.....#..#
+#.#.......
+...##.##.#
+.##..#.#..
+#...##...#
+......##.#
+..#.......
+#.#.....##
+##.#..##..
+
+Tile 2543:
+#.#..#..##
+##.##.#...
+...#.##...
+#.#......#
+.#.#...#.#
+..##.#...#
+###.#...##
+#.##..#..#
+#.##...#..
+.#.###....
+
+Tile 3041:
+.###......
+.........#
+#..##.....
+##.#....##
+###..#.###
+...#.##.#.
+.##...##.#
+#...#....#
+###...##.#
+####..#..#
+
+Tile 1559:
+##..##....
+#.##....#.
+.#.#......
+..........
+#...#.#...
+#.##....##
+.#........
+#.....#.##
+#.......#.
+....#..#.#
+
+Tile 2617:
+#.##.##.#.
+...#...#.#
+......#.#.
+#..#......
+#.#..#.#..
+......##.#
+#......#..
+.#.....#..
+###...#..#
+#.#..##..#
+
+Tile 1861:
+..#.#..###
+##.....#..
+..#.....#.
+#.........
+.####...##
+...#..##.#
+#...#####.
+....#.##..
+.##..#..#.
+#.####.##.
+
+Tile 1747:
+##...#..#.
+#....#...#
+##...#.###
+#...#.....
+#.##.#..##
+...#......
+.....#..#.
+...#.##...
+.#..###...
+#...###..#
+
+Tile 2579:
+##.###.###
+..#.#..#.#
+.##..#.#..
+##..#.####
+##..#..###
+...#.#...#
+#..#.....#
+.##.#...#.
+.#...##...
+#....##..#
+
+Tile 3761:
+.#.###.###
+#....#....
+#.#.....##
+.###...#.#
+###...##.#
+.###.....#
+...#...#..
+.....#.#.#
+.#.##.#..#
+##..####.#
+
+Tile 3463:
+######..#.
+.#..##...#
+...##...##
+.#...##.#.
+.#.#...#.#
+.........#
+#........#
+..##...#.#
+#...#....#
+#.###.....
+
+Tile 2521:
+###.##....
+###.##.#..
+#..##.....
+..#...#..#
+.#.#.....#
+##...#...#
+..#......#
+..#..##..#
+#........#
+#########.
+
+Tile 2647:
+####.#.##.
+#..#.#...#
+#.......#.
+.........#
+#.####....
+#.#..#..#.
+#........#
+#.#......#
+##..#..#..
+...##.....
+
+Tile 3847:
+.....#..#.
+#.....###.
+##......##
+###.....##
+#....#.#..
+#.##.##...
+.#..#.##..
+#...#.####
+.........#
+.##.####..
+
+Tile 2027:
+.##...#.##
+...#..##..
+#...#.###.
+#......###
+#.......#.
+#....###.#
+#.#.##....
+.........#
+.......#..
+..#..##..#
+
+Tile 3347:
+.###.#...#
+....##...#
+#...##...#
+.#.#.#...#
+#.#.#..#.#
+#.#..#.##.
+##..#.....
+..#..#.#..
+.#......##
+..#..#####
+
+Tile 3911:
+###....#.#
+....##.##.
+#.#.#....#
+...#.....#
+...##..#..
+..###.#.#.
+....#.....
+#..##....#
+#.##.#.#..
+.#..##...#
+
+Tile 1741:
+####.##...
+...##...#.
+...#......
+#...##..#.
+..#...#..#
+#.........
+.#...#....
+#..#.#..##
+#.........
+#...#..#.#
+
+Tile 3137:
+.#....#.##
+#......#..
+#.#...#...
+##....#...
+#.#.#.#..#
+....#....#
+..##.....#
+##.......#
+........##
+..#..###.#
+
+Tile 2417:
+##...##..#
+##.....#.#
+....##....
+.#...#...#
+....##.###
+#...#..#.#
+#....#...#
+..#...#..#
+#..#...#..
+...#.####.
+
+Tile 2803:
+#.###..###
+#....#...#
+#.#.......
+#..##.....
+.#....#...
+.#...#....
+#.#..#...#
+#.##.##...
+.#.##.####
+.####.....
+
+Tile 2267:
+.#.#.#..##
+..#.#....#
+#...#....#
+...#..###.
+...##.....
+#.#.......
+.#...#....
+##..#.#.#.
+.#..##.#.#
+####.#.##.
+
+Tile 1613:
+..##.#.#.#
+.......##.
+......####
+......##..
+##.#.....#
+#.......##
+#...#..#..
+.......#..
+#......#..
+#.#.#....#
+
+Tile 2777:
+.####.##.#
+#..#.....#
+##.###.###
+###.#.....
+.##..#...#
+.#.#...#..
+#.........
+...#...###
+...#....#.
+#.#.###..#
+
+Tile 3923:
+#####..#.#
+....#.#..#
+#.#..#..##
+...##.....
+#.#.......
+.........#
+..#.####.#
+#.#..####.
+#####..#.#
+#.##.###.#
+
+Tile 3919:
+...###.###
+##.#.....#
+#.........
+##....##.#
+.#.....#..
+.....#....
+...####..#
+..#.##.#..
+....#....#
+.##.....#.
+
diff --git a/2020/day20/main.go b/2020/day20/main.go
@@ -0,0 +1,318 @@
+package main
+
+import (
+ "bufio"
+ "fmt"
+ "os"
+ "regexp"
+ "strconv"
+)
+
+const (
+ LIT = 1
+ DARK = 0
+ TOP = 0
+ LEFT = 1
+ BOTTOM = 2
+ RIGHT = 3
+)
+
+type Tile struct {
+ id int
+ size int
+ v []int
+}
+
+func (this Tile) get(x, y int) int {
+ return this.v[x*this.size+y]
+}
+
+func (this Tile) set(x, y, val int) {
+ this.v[x*this.size+y] = val
+}
+
+func (this Tile) computeBorder() [4]int {
+ top, left, bottom, right := 0, 0, 0, 0
+ for i := 0; i < this.size; i++ {
+ top <<= 1
+ top += this.get(0, i)
+ left <<= 1
+ left += this.get(i, 0)
+ bottom <<= 1
+ bottom += this.get(this.size-1, i)
+ right <<= 1
+ right += this.get(i, this.size-1)
+ }
+ res := [4]int{top, left, bottom, right}
+ for i, _ := range res {
+ // Disambiguate by picking the larger between flipped versions.
+ res[i] = max(res[i], reverseBit(res[i], this.size))
+ }
+ return res
+}
+
+func (this Tile) rotate(rot int) (new Tile) {
+ // Rotate clockwise rot*90 degrees.
+ new = Tile{this.id, this.size, make([]int, this.size*this.size)}
+ for x := 0; x < this.size; x++ {
+ for y := 0; y < this.size; y++ {
+ xNew, yNew := x, y
+ for i := 0; i < rot%4; i++ {
+ xNew, yNew = yNew, this.size-1-xNew
+ }
+ new.set(xNew, yNew, this.get(x, y))
+ }
+ }
+ return new
+}
+
+func (this Tile) flip(flp int) (new Tile) {
+ // Flip left to right flp times.
+ new = Tile{this.id, this.size, make([]int, this.size*this.size)}
+ for x := 0; x < this.size; x++ {
+ for y := 0; y < this.size; y++ {
+ xNew, yNew := x, y
+ for i := 0; i < flp%2; i++ {
+ xNew, yNew = xNew, this.size-1-yNew
+ }
+ new.set(xNew, yNew, this.get(x, y))
+ }
+ }
+ return new
+}
+
+func (this Tile) toString() (res []string) {
+ for x := 0; x < this.size; x++ {
+ row := ""
+ for y := 0; y < this.size; y++ {
+ switch this.get(x, y) {
+ case LIT:
+ row += "#"
+ case DARK:
+ row += "."
+ }
+ }
+ res = append(res, row)
+ }
+ return
+}
+
+func reverseBit(x int, size int) (res int) {
+ for i := 0; i < size; i++ {
+ res <<= 1
+ res += x & 1
+ x >>= 1
+ }
+ return
+}
+
+func max(x int, y int) int {
+ if x > y {
+ return x
+ } else {
+ return y
+ }
+}
+
+func readInput(filename string) (res []Tile) {
+ file, _ := os.Open(filename)
+ defer file.Close()
+
+ matcher := regexp.MustCompile(`Tile ([0-9]{4}):`)
+ scanner := bufio.NewScanner(file)
+ for scanner.Scan() {
+ line := scanner.Text()
+ if line == "" {
+ continue
+ }
+ matched := matcher.FindStringSubmatch(line)
+ id, _ := strconv.Atoi(matched[1])
+ v := []int{}
+ size := len(line)
+ for i := 0; i < size; i++ {
+ scanner.Scan()
+ line := scanner.Text()
+ for _, ch := range line {
+ switch ch {
+ case '#':
+ v = append(v, LIT)
+ case '.':
+ v = append(v, DARK)
+ }
+ }
+ }
+ res = append(res, Tile{id, size, v})
+ }
+ return
+}
+
+func main() {
+ input := readInput("./input.txt")
+ // 7901522557967
+ fmt.Println(part1(input))
+ // 2476
+ fmt.Println(part2(input))
+}
+
+func countBorders(tiles []Tile) (res map[int]int) {
+ res = map[int]int{}
+ for _, t := range tiles {
+ for _, v := range t.computeBorder() {
+ res[v] += 1
+ }
+ }
+ return
+}
+
+func part1(input []Tile) (res int64) {
+ // Shared borders are unique, i.e. no more than 1 pair.
+ borderCount := countBorders(input)
+ // Angle tiles only have 2 shared borders.
+ angleTiles := []int{}
+ for _, t := range input {
+ sharedCount := 0
+ for _, v := range t.computeBorder() {
+ sharedCount += borderCount[v] / 2
+ }
+ if sharedCount == 2 {
+ angleTiles = append(angleTiles, t.id)
+ }
+ }
+ res = 1
+ for i := 0; i < 4; i++ {
+ res *= int64(angleTiles[i])
+ }
+ return
+}
+
+func assembleImage(tiles []Tile) (res Tile) {
+ borderCount := countBorders(tiles)
+ idMap := map[int]Tile{}
+ for _, v := range tiles {
+ idMap[v.id] = v
+ }
+ // Find correct arrangment of tile ids.
+ used := map[int]bool{}
+ image := [][]int{}
+ row := []int{}
+ leftReq, topReq := 0, 0
+ for {
+ // Find next tile according to left and top borders.
+ found := false
+ for id, t := range idMap {
+ if used[id] {
+ continue
+ }
+ leftSide, topSide := -1, -1
+ for side, v := range t.computeBorder() {
+ // 0 means unique borders not shared with others.
+ if borderCount[v] == 1 {
+ v = 0
+ }
+ if leftSide == -1 && v == leftReq {
+ leftSide = side
+ } else if topSide == -1 && v == topReq {
+ topSide = side
+ }
+ }
+ if leftSide != -1 && topSide != -1 {
+ // Add to image after correctly orienting it.
+ found = true
+ // Use top to compute rotation.
+ t = t.rotate(topSide)
+ // Use left to compute flip.
+ if left := t.computeBorder()[LEFT]; (leftReq != 0 && left != leftReq) ||
+ (leftReq == 0 && borderCount[left] != 1) {
+ t = t.flip(1)
+ }
+ idMap[id] = t
+ row = append(row, id)
+ used[id] = true
+ break
+ }
+ }
+ if !found {
+ panic("No matching tile found!")
+ }
+ // Update requirements.
+ lastBorder := idMap[row[len(row)-1]].computeBorder()
+ if borderCount[lastBorder[BOTTOM]] == 1 &&
+ borderCount[lastBorder[RIGHT]] == 1 {
+ // Image finished.
+ image = append(image, row)
+ break
+ } else if borderCount[lastBorder[RIGHT]] == 1 {
+ // Start new row.
+ image = append(image, row)
+ row = []int{}
+ leftReq = 0
+ topReq = idMap[image[len(image)-1][0]].computeBorder()[BOTTOM]
+ } else {
+ // Start next in row.
+ leftReq = lastBorder[RIGHT]
+ if len(image) == 0 {
+ topReq = 0
+ } else {
+ topReq = idMap[image[len(image)-1][len(row)]].computeBorder()[BOTTOM]
+ }
+ }
+ }
+ // Piece together full image. Resulting image is always square.
+ tileSize := idMap[image[0][0]].size
+ pixels := []int{}
+ for i := 0; i < len(image); i++ {
+ for x := 1; x < tileSize-1; x++ {
+ for j := 0; j < len(image[0]); j++ {
+ for y := 1; y < tileSize-1; y++ {
+ pixels = append(pixels, idMap[image[i][j]].get(x, y))
+ }
+ }
+ }
+ }
+ return Tile{0, (tileSize - 2) * len(image), pixels}
+}
+
+func findMonster(image []string, monsterRegex []*regexp.Regexp, monsterLen int) (res int) {
+ for x := 0; x <= len(image)-len(monsterRegex); x++ {
+ for yMax := monsterLen; yMax < len(image[0]); {
+ // Match per sliding window of same size so we have at most 1 match.
+ matchCount := 0
+ for i := 0; i < len(monsterRegex); i++ {
+ matchCount += len(monsterRegex[i].FindAllStringIndex(image[x+i][(yMax-monsterLen):yMax], -1))
+ }
+ if matchCount == len(monsterRegex) {
+ res += 1
+ // Sea monters don't overlap, so we can do this; makes counting easier too.
+ yMax += monsterLen
+ }
+ yMax += 1
+ }
+ }
+ return
+}
+
+func part2(input []Tile) (res int) {
+ monsterRegex := []*regexp.Regexp{
+ regexp.MustCompile(`..................#.`),
+ regexp.MustCompile(`#....##....##....###`),
+ regexp.MustCompile(`.#..#..#..#..#..#...`),
+ }
+ monsterLen := 20
+ monsterLitCount := 15 // Each sea monster has 15 '#'s.
+ image := assembleImage(input)
+ litSum := 0
+ for _, p := range image.v {
+ litSum += p
+ }
+ // Try all orientations of the image.
+ for rot := 0; rot <= 3; rot++ {
+ for flp := 0; flp <= 1; flp++ {
+ image := image.rotate(rot).flip(flp).toString()
+ monsterCount := findMonster(image, monsterRegex, monsterLen)
+ if monsterCount > 0 {
+ return litSum - monsterCount*monsterLitCount
+ }
+ }
+ }
+ return
+}