commit - 4e6f21582d9227d70475791ac29421d5bf3e4f44
commit + b80049b66156a9cbb8f881dc7a18b7c4a1642138
blob - /dev/null
blob + 39ac3ad0aea1ac763b07da136f4760fd131c9cd3 (mode 644)
--- /dev/null
+++ input/16.txt
@@ -0,0 +1,141 @@
+#############################################################################################################################################
+#.........#.............#.....#.....#.....#.........#...#.............#...#.............#.........#.....#...................#.....#.#......E#
+#.#######.#.###########.#.###.###.#.#.#.#.#.#.#.###.###.#.###########.#.###.#####.#######.#.###.#.###.#.#.###########.#.###.###.#.#.#.###.###
+#.......................#.#.....#.#.#.#.#.#...#...#...#.#.#.......#...#.......................#.#...............#...........................#
+#.#.#.#.#####.#####.#.###.#####.#.#.###.#.###.###.###.#.#.#.#.#.###.###.#.###.#.#.#.#########.#.#####.#######.#.#.#.###.#.###.#.#.###.#####.#
+#...#.#.#...#.#...#...#...#...#...#...#.#.........#.....#.#.#.#.#...#...#.#...#.#.....#.....#.#.....#.....#.#.#.#.#.....#.............#.....#
+#.###.###.#.###.#.#.#####.#.#.#######.#.#####.#.#######.#.#.#.###.###.###.#.###########.###.#######.#.###.#.#.#.#.#####.#.#######.#.###.#####
+#.#.#...#.#.....#.#.......#.#...#...#...#...#.#.#...#...#.#.#.....#...#...#.#...#.....#.#.#.........#.#...............#...........#.#.#.....#
+#.#.###.#.#######.#######.#.###.#.#######.#.#.#.#.#.#####.#####.#.#.#.#.#.#.#.#.#.###.#.#.###########.#.###.###.#.#.#.#.#####.#####.#.#####.#
+#.#...#...................#...#.#.....#...#...#.#.#.....#.......#.#.#.......#.#...#.#.#.#...........#...#.#.#...#...#.#.#...#.....#.......#.#
+#.#.#.#.#####.#.#.#.#####.#.###.###.#.#.#####.#.#.#####.#.#####.#.#######.###.#####.#.#.#.#######.#.#.###.#.#.#.#####.#.#.#.#.#######.###.#.#
+#...#.#.....#.................................#.#.#.....#.....#.#...........#...#...#...#.#.....#.#.#.#.....#.#.#...#.#.#.#.#.#...#...#.....#
+#####.#####.#.#.#####.#.#.#.#.###.###.#.#####.#.#.#####.#######.#########.#.###.###.#####.#.###.###.#.###.###.#.###.#.#.#.#.###.#.#.###.#.#.#
+#.#...#...#...#.....#.#.#...#...#...#...#.......#.....#.......#.#.#.........#...#.....#...#...#.....#...#.....#.....#.....#.....#...#...#...#
+#.#.###.#.#####.###.###.#.#####.#.#.#####.###########.#######.#.#.#.#####.###.###.#####.#####.#########.#####.#####.###.#############.###.###
+#...#...#.#.....#.......#.......#.#.................#.#...#...#.#.#.......#...#.......#.#...#...#...#.........#...#.......#.......#...#.....#
+#.###.#####.#.#########.#.#######.###################.#.#.#.###.#.#######.#.#.#######.#.#.#.###.#.#.#.###.#####.#.#####.###.#####.#.###.#.#.#
+#.#.#...#...#.....#...#.#.#.....#.#...#.#.............#.#.......#.........#.#.#.....#.#...#...#...#.#.#...#.....#.#...#...#...#.....#...#...#
+#.#.#.#.#.#######.#.#.###.#.#.###.#.#.#.#.###########.###########.#######.#.#.#.###.#.#######.#####.#.#.###.#####.#.#.#.#.###.#.###.#.###.#.#
+#.#...#.....#...#...#...#.#.#.#...#.#...#.......#...#.#.......#.....#...#.#.#.#.#.......#.....#...#.#.#.#...#...#...#.#.#.....#.#...#...#.#.#
+#.#.#########.#.#.###.#.#.#.###.###.###.#######.#.#.#.#.#.###.#######.#.#.###.#.#########.#.#####.#.#.#.#.###.#.#####.#.#######.#.###.#.#.#.#
+#.#.....#.....#.#...#...#.#.#...#.....#.....#.#.#.#...#.....#.#.......#.#.....#.........#.........#.#.#.#...#.#.....#.#...............#.#.#.#
+#.#####.#.#####.#####.#.#.#.#.#######.#####.#.#.###########.#.#.#######.#######.#######.#######.###.#.#####.#.###.###.#.#####.#.#.#.#.#.#.#.#
+#.#.....#...#.#.......#.#.#.#.#.......#...#...#.............#...#.#.....#.....#.#.....#...#.....#...#.......#.....#...#.....#...#.#.#...#.#.#
+#.#####.###.#.#########.#.#.#.#.#######.#####.#########.#########.#.###.#.###.#.#####.#.###.#####.###########.#####.###.###.###.#.#.#.###.#.#
+#.....#...#.#.........#.#.#.....#...#...#.....#.......#...#.......#.#...#.#.#.#.......#...#.....#.....#...#...#.....#.....#.....#.......#.#.#
+#####.#.#.#.#########.#.#.#####.#.###.#.#.#####.#####.###.#.#######.#####.#.#.#######.###.###.#######.#.#.#.#.#.#.#.#########.#.#####.#.#.#.#
+#.....#...#.........#.#.#...#.........#.....#...#...#.#.#.#.#.......#.....#.#.......#...#.....#.....#...#...#...#.#...#.......#.....#...#.#.#
+#.###.#.#.#.#.#####.#.#.###.#####.###########.###.###.#.#.#.#.#######.#####.#######.#.#########.###.#.#########.#.###.#.###########.#.#.#.#.#
+#.#...#...#.....#...#.#.#...#...#...#.........#.....#.#...#.#.......#.#.........#...#.#...........#.#.........#.....#.#.....#.....#...#.#.#.#
+#.#.#.#.#.#.#####.###.#.#.###.#.#####.#########.###.#.###.#.#######.#.#.#######.#.#.###.#########.#.#########.#.#####.#####.#.###.###.#.#.###
+#...#...#.#.#...#...#.#.#.....#.#...#.#...#...#...#.#...#.#.......#.#.#...#.#...#.#.....#...#...#.#.#.........#...#...#.....#...#...#.#.#...#
+#####.#.#.###.#.###.#.#.#######.#.#.#.#.#.#.#.###.#.###.#.###.#.#.#.#.###.#.#.###.#.#####.#.#.#.###.###.#######.#.#.###.#########.#.#.###.#.#
+#.#...#.......#.....#...#...#.#.#.#.#.#.#.#.#...#.#...#.#...#.#...#.....#...#...#...#...#.#.#.#...#...#...#...#.#.#.#...#.........#.#...#.#.#
+#.#.#.#.#.###.#########.#.#.#.#.#.#.#.#.#.#.###.#.###.#.#.#.#.#########.#######.#####.#.#.#.#.###.###.#.###.#.###.#.#.###.#.#########.#.###.#
+#.#.#...#...#.#...#...#...#...#...#.#...#...#...#.#.#...#.#...#.....#.....#...#...#...#...#...#...#...#.#...#...#.#.#.#...#.................#
+#.#.###.#.#.#.#.#.#.#.#######.#####.#########.###.#.#####.#.###.###.#####.#.#.#.###.###########.###.#####.#####.#.#.#.#.###########.#.#####.#
+#.#...#...#.#.#.#...#.#...#...#...........#...#...#.#.......#...#.#.....#...#...#...............#.#...........#.#.#...#...........#.......#.#
+#.###.#.#.#.###.#.###.#.#.###.#.###.#######.###.###.#.###.###.###.#####.#####.###.###.###########.#.#########.#.#.#######.#####.#######.###.#
+#...#.#.#.....#.#.#...#.#.....#...#.........#.#.#.....#...#...#...#.....#.....#...#...#...#.....#...#...#...#.#.#.......#.....#.......#.....#
+#.#.#.#.#.###.#.#.#.###.###.#.###.#.#.#######.#.#####.#.###.###.###.###########.###.#.#.#.###.#.#.###.#.#.#.#.#.#######.#####.#######.#######
+#.#...#.....#...#...#...#...#.#...#.#.#.......#.....#...#...#.......#...........#.....#.#.....#.#.#...#...#.#.#.#.....#.....#.#.......#.....#
+#####.###.#.#####.###.#.#.#####.#.###.#####.#.#####.###.#.###.#######.###########.#####.#######.###.#######.###.#.###.#.###.#.#.#####.#.#####
+#...#.#...........#.....#.....#.#...#.....#.#.......#...#.............#.........#.#.....#...#...#...#.....#...#...#.#.#...#.#...#.....#.....#
+#.#.###.#####.#######.#####.#.#.#.#.###.#.#.###############.###########.#######.#.#.#######.#.###.#######.###.###.#.#.#.#.#######.#####.###.#
+#.#...#.#...#.#.......#.....#...#.#...#.#.#...#.............#.#...............#.....#.......#.....#...#.....#...#...#.#.#.......#.....#.#...#
+#.###.#.#.###.#.#######.###.###.#.###.###.###.###.###########.#.#####################.###.#.#######.#.#.#######.#####.#####.#########.###.###
+#...#...#.....#.......#.#...#.#.#...#.#...#.#...#.....#.......#...#...#.#.........#...#...#.........#.#.#.......#...#.#...#.........#...#...#
+###.#####.#####.#####.###.#.#.#.###.#.#.###.###.#.###.#.#####.###.#.#.#.#.#######.#####.#.###########.#.#.#######.#.#.#.#.###.###.#.###.#.#.#
+#...#.#.........#...#...#.#...#.#...#.#.#.......#.#.#.......#.......#...#.#...#...#...#.#.#...#.........#.#.......#.#.#.#.#.......#.#...#.#.#
+#.###.#.###.#####.#####.#.#####.#.###.#.#.#######.#.#.###################.#.#.#.###.#.#.###.#.#.#######.#.#.#######.#.#.#.#.#######.#.###.#.#
+#.#.....#.......#...#...#.#.....#.......#...#...#...#.....#...............#...#.....#.#.....#.#.....#.....#.#.....#...#.#...#.....#.#...#.#.#
+#.#.###########.#.#.#.###.#.#####.#########.###.#.#######.#.###############.#.#######.#.###.#.#######.#####.#.#.#######.###.#.###.#.###.###.#
+#.#.......#.#...#.#.#.#...#...#.#.........#...#...#.....#...#.........#.....#.......#.#...#.......#...#.....#.#.#.....#.....#...#...#.#.....#
+#.#######.#.#.#####.#.#.#.###.#.#.#####.#.###.#####.###.#.#.###.#.###.#.#######.###.#.###.#.#.#.#.#.###.#####.#.#.###.#.###.#######.#.#.#.#.#
+#.#.......#.....#...#.#.#.....#.#.....#.#.#.#.......#...#.......#...#.#.........#...#.#.#.#.#.#.#...#.....#...#.#...#...#.#.......#.#.#...#.#
+#.#.###########.#.###.#######.#.#.###.###.#.#########.###########.#.#.###.#####.#.#.#.#.#.#.###.#####.###.#.#######.#####.###.###.#.#.#####.#
+#.#...#.....#...#.#...#.....#...#.#.#.....#.........#...#...#...#.#.#...#...#.#.#.#...#.#.#.....#.....#...#.#.....#.......#.....#.#.....#...#
+#.###.###.#.###.#.#.###.###.#####.#.#.#######.#.###.###.#.#.#.#.#.#.###.###.#.#.#.#####.#.#############.###.#.#.#.#######.#.#####.#.###.#.###
+#.......#.#...#...#.......#...#...#...#.....#.#.#...#...#.#...#...#...#.....#...#...#...#...#.....#.....#...#.#.........#.#.....#.#.....#...#
+###.###.#.###.#####.#########.#.#######.###.###.#.###.###.#####.#####.#######.#####.#.#.###.#.###.#.#####.###.#.###.#####.#####.#.#.#######.#
+#...#...#.#.#.#...#.#.........#.........#...#...#.#...#.........#.......#.....#.#...#.#...#.......#.#...#.#...#.#...#.....#...#.#.#.#...#.#.#
+#.###.###.#.#.#.#.###.###.###############.###.###.#.#.###.#.#.###.#.###.#.#####.#.###.###.#####.###.#.#.#.#.###.#####.#####.#.#.#.#.#.#.#.#.#
+#...#.....#.....#.....#...#.........#...#...#.#.....#.....#...#...#.#.#.#.......#.#.......#...#...#...#.#.#.#.#.......#...............#...#.#
+#.#.###########.#######.###.#####.#.###.###.#.#####.#####.###.#.###.#.#.#.#######.###.#####.#.###.#####.#.#.#.#######.#####.#.###.#.###.###.#
+#.#...#...#...#.#.............#...#.....#...#.....#.#...#...#.#.#...#...#.#.....#...#.......#...#.......#...#...............#...............#
+#.###.#.#.#.#.###.#######.#####.#####.###.#.#.###.###.#.###.#.#.#.###.#####.###.#.#.#######.###.#####.###.#########.#########.#.#.#.###.#.###
+#.#.#...#...#...#...........#...#.....#...#.....#...#.#.......#.#...#.......#...#.#.......#.#.....#.............#...#.....#...#.#.#...#.#.#.#
+#.#.###########.#########.###.#.#####.#.###.#######.#.#########.###.#########.###########.#.#.#####.#.#.#######.#.###.###.###.#.#.#.#.#.#.#.#
+#.#.....#.....#...........#...#.....#.#...#.#...#...#.....#.......#.#...#...#...#.........#.#.#.....#...#.........#...#.#.....#.#.#.#.#.#.#.#
+#.#####.#.###.#.###.#.#####.#####.#.#####.#.#.#.#.###.#####.#.#####.#.#.#.#.###.#.#########.#.#.#####.#.###########.###.#####.#.###.#.###.#.#
+#...#...#.#...#...#.#.#.....#.....#.#...#.#.#.#.#.....#.....#...#...#.#.#.#...#...#...#.....#...#.....#...#.......#.#.......#.#.....#...#.#.#
+#.#.#.#.#.#.#.#.#.#.#.#.###.#.###.#.#.#.#.###.#.#######.#####.#.#.###.#####.#######.#.#.#.#.#####.#######.#.#####.#.#.###.###.#.#######.#.#.#
+#...#.#.........#.#.#.#...#.#.#...#...#.#.....#.#.....#.#.....#.#...#.#...#.........#...#.#.......#.......#.#...#...#.#...#...#.#.......#.#.#
+#.###.###.#######.#.#.###.###.#.#.#####.###.###.#.###.#.#.###.#####.#.#.#.#.#.#########.#.#########.#.#.###.#.#.#####.#####.#####.#####.#.#.#
+#.#.......#...#.#.#.#...#.....#.#.....#.....#...#.#.#...#.........#.#...#.#.#.....#...#...#.....#.....#.#...#.#...#.......#.....#.....#.#...#
+#.#####.###.#.#.#.#.###.###########.#.#.###.#.#.#.#.#########.#.###.#####.#.#####.###.#####.#.###.###.#.#.#.#.###.###.###.#####.#.###.#####.#
+#.....#...#.#.#.#.#.................#.#.#.#.#.#.#.#.........#.#...#...#...#.#...#...#.......#.#.....#...#.#...#.#...#...........#...#.#.....#
+#.###.###.#.#.#.#.###.#####.###########.#.#.#.#.#.#####.#.#.#.###.###.#.###.###.###.#####.###.#.#####.###.#####.###.#####.###########.#.#####
+#...#.#.....#...#...........#.....#...#.#...#.#.#.#.......#.#.#.....#.....#.....#...#...#...#.#.#...#.........#...#...............#...#.#...#
+#.#.#.#########.#.#########.#.###.#.#.#.#####.#.#.#.#######.###.###.#####.#####.#.###.#.#####.#.#.#.###.#####.###.#####.#########.#.#.#.###.#
+#.#.#...#.#...#.#.....#...#.#...#.#.#.#.....#.#.#.#...#.........#.#...#.......#.#.....#.......#.#.#...#.#.....#.......#.#...#.....#.#.#...#.#
+#.#####.#.#.#.#.#####.###.#.###.#.#.#.#####.#.###.#.#.###.###.###.###.#.#.#####.###########.#.#.#.###.#.###.###.#.###.#.#.#.#.#####.#.###.#.#
+#.......#...#.#.#...#...#...#...#...#.....#.#.....#.#...#.#.....#...#...#.#.....#.........#.#...#...#.#...#.....#...#.#.#.#.#...#...#.#.#.#.#
+#.#######.###.#.###.###.#####.#########.###.#.#####.###.###.###.#.#####.###.#########.###.#.#.#####.#.###.###.###.#.###.#.###.#.###.#.#.#.#.#
+#...#.......#.#.....#...#...#...#.....#...#.......#...#...#.#.#.#...........#.....#...#...#.#.#...#.#...#...#.#...#.....#...........#...#...#
+###.#######.#.#.#.###.###.#.###.#.###.###.#####.###.#####.#.#.#.###.#####.###.#.#.#.###.###.###.#.#.###.###.###.###.#######.###############.#
+#.#.#...#...#...#.#...#...#.#...#...#...#.....#...#.#.....#.#.#...#...#.#...#.#.#.#.#.#.#.#.....#...#.#.#.......#...#.....#.#.....#.........#
+#.#.#.#.#.###.#.#.#.###.###.#.#####.###.###.#####.#.#.###.#.#.###.###.#.###.#.#.#.#.#.#.#.###########.#.#####.#######.###.#.#.###.#.#########
+#.#...#.#.#.....#.#.....#...#.#.....#.#.#.#.....#...#.#...#.#...#.#.......#.#.#.#...#.#.....#.............#.#.#.....#...#.#.#.#.#.#.#.......#
+#.#####.#.#.#.#.#.#######.###.#.#.###.#.#.#####.#####.#.###.###.#.#######.#.#.#.#####.#.#####.###.###.###.#.#.#.###.###.#.#.#.#.#.#.#.###.#.#
+#.......#.#.#...#.....#...#...#.#.#...#...#...#...#...#.#...#...#.......#.#...#...#.#...#.....#.........#.....#.#.#.....#...#...#.#.#.#...#.#
+#.#######.#.#.#.###.#.#.###.#####.###.#.#.#.###.#.#.#####.###.#########.#####.#.#.#.#.###.#####.#.#.###.#.###.#.#.#######.#.#.###.#.###.###.#
+#.#.#.....#.....#.#...#...#.#.....#...#...#...#.#.#...#...#...........#.#.....#.#.#...#.........#.....#.#...#.#.......#.#.#...#...#.....#.#.#
+#.#.#.#####.#.#.#.###.###.#.#.#####.###.###.#.#.#####.#.###.#########.#.#.#######.#.###.#.#.###.###.#.#####.#########.#.#.#.###.#########.#.#
+#.#...#...........#...#.#.#...#...#...#.#...#.#.....#...#...#...#.....#.#.#.......#...#.#...#...#...#.....#.....#.....#.#.#...#.......#.#...#
+#.#####.#.###.#####.###.#.#####.#.#.#.#.#####.###.#######.#####.#.###.#.#.#.###.#######.#.#.###.#.#.#####.#####.#.#.#.#.#.###.###.###.#.#.###
+#.......#...#.........#.........#...#...#.......#.......#.#.....#...#.#...#...#.#.......#.#...#...#.#.........#.#.......#...#...#.#.....#.#.#
+###########.#.#######.#.#####.###.#.#####.#####.#######.#.#.###.###.#######.#.###.#######.###.#####.#.#####.#.#.#.#######.#.#.###.###.#.#.#.#
+#.#.......#.......#.#.....#...#...#.#.....#...#.#.......#...#...#...#.......#.......#.....#.#.#.....#.#.......#.....#.....#.#.#...#...#.#...#
+#.#.#.#######.###.#.#####.#.###.###.#.###.#.#.###.###.#######.###.#.#.###############.#####.#.#######.###.###########.#####.#.#.###.#.#.#.#.#
+#.#.#...#.......#.#.......#.......#.#.#.#.#.#...#.#...#.....#.#.#.#.#.#...#.....#.....#.....#...#...#...#...#.......#.#.....#.#.....#.#.#.#.#
+#.#.###.#.###.#.#.#.#.#####.#######.#.#.#.#.###.#.#.###.#.###.#.#.#.#.#.###.#.###.#####.###.###.#.#.###.#####.#####.#.#######.#######.###.#.#
+#...#...#...#.#.#.#.#.#...#...#.....#...#.....#.#.#.#...#...#.#.#.....#.....#...#...#...#.#.#...#.#.....#...#...#.#.#.#.....#.#.....#...#...#
+#.#.#.#####.#.#.#.#.#.#.#.###.#.###########.###.#.###.#####.#.#.#######.#######.###.###.#.#.#.###.#####.#.#.###.#.#.#.#.###.#.#.###.#.#.###.#
+#.#.#...#...#.#.#.#.#.#...#...#...#.......#.#...#...#.#...#...#...........#...#...#...#...#...#...#.....#.#...#.#.....#...#.#...#.#.#.#.....#
+#.#.###.#.###.#.#.#.#.#.#.#.#####.#.#####.###.#.###.#.###.###.###########.###.#.#####.###.#####.#.#.###.#.#.#.#.#########.#.#####.#.#.#######
+#.#...#...#...#...#...#.#.#.....#...#.#...#...#.#...#.....#...................#.....#...#.......#.#.#.#.#.#...#.........#.#.....#...#.......#
+#.#.#.#####.#.###.#.###.#.#####.#####.#.###.#.#.#.#######.###.#########.###.#.#####.###.###########.#.#.#.#.#.#.#####.#.#.#.#####.###.###.###
+#.#.................#...#.....#.......#.#...#.#...#.....#...#...#.....#.....#.....#...#...#.....#...#.#.....#.#...#...#.#.#.......#...#.....#
+#.#.#.#.###.#########.###.###.#.###.###.#.###.#.#.#.###.###.#.#.#.###.#####.#######.#####.#.###.#.###.#####.#.#.#.#.#####.#.#######.#.#.#.#.#
+#...#.#...#.........#.#...#.....#.#.#...#...#.#.....#.#...#.#.#.....#...#.#.......#.....#.#...#.#.#.......#.#.#.#.#.......#.....#...#...#.#.#
+###.#.###.#.#######.#.#####.#####.#.#.#####.#.#######.#.###.#.#######.#.#.#######.#.###.#.#.###.#.###.#.###.#.#.#.#############.#.#######.#.#
+#.#.#...#.........#.#.....#...#.....#.#.....#.#.#.....#.....#...#...#.#.#...#...#.#.#...#...#...#.....#.#...#...#...............#.#.......#.#
+#.#.###.###.#.#####.#.###.###.#######.#.#.###.#.#.###.###########.#.###.###.#.#.#.#.#.#######.#########.#.#.#################.###.#.#.###.#.#
+#.#.#.......#...#...#.#...#.#.....#...#.#.#...#.....#.............#...#.#...#.#...#.#.......#.......#...#.#.#...#...#.......#.#...#.#...#.#.#
+#.#.#.#####.###.#.###.#.#.#.#####.#.###.#.###.###.#.###.#############.#.#.###.#####.#######.#.#.###.#.###.###.#.#.#.#.###.###.#.###.###.#.#.#
+#...#.#.......#.#.#...#.#.......#...#.#.#...#.....#.....#...#.......#...#.#.....#.......#...#.....#.#.#.#.....#...#.#.#.#...#.#.....#...#...#
+#.#####.###.#.#.#.#####.#######.#####.#.###.#.###.#.#####.#.###.#.#######.#.###.#.#######.#.###.###.#.#.#######.###.#.#.###.#.#####.#.###.#.#
+#.#...#.....#.#.........#...#.#...#...#...#.....#.#.......#...#.#.......#.#...#...#...#...#.................#.....#.#.....#.......#.#.#.....#
+#.#.#.#####.#.###.#######.#.#.###.#.#####.#####.#.###########.#.#####.#.#.###.#####.#.#.#.#####.#.#########.#####.#.#####.#####.###.#.#.#.#.#
+#.#.#.#.....#...#.........#.#...#.#.........#...#.........#...#...#...#.....#.......#...#.#...#.#.................#.....#.#...#...#...#.#.#.#
+#.#.#.#.###.###.#.#########.#.#.#.#.#######.#.###########.#.###.###.###.#########.#######.#.#.#.#################.#.#.#.#.#.###.#.###.#.#.#.#
+#...#...#.....#.#.......#.#.#.#...#.......#...#.........#.#.#...#...#...#.....#...#.....#...#.#.....#.....#.........#.#.....#...#...#.#.#...#
+###########.#.#.#.#####.#.#.#.###########.#.###.#.###.###.#.#.###.#.#####.#.#.#.###.###.#####.#####.#.###.#########.#.#######.#.###.#.#.#.###
+#.#.......#.#.#.#.#.....#.#.#.......#...#.#.#.....#.#.#.....#...#.#.......#...#...#.#.#.....#.......#.......#.....#.#.......#.#...#...#.#.#.#
+#.#.###.#.#.#.#.#.#.#####.#.#######.#.#.#.#.#.#.#.#.#.#.#########.###.#####.#####.#.#.#####.#.#####.#.#.###.#.###.#.#######.#.#.#######.#.#.#
+#...#.#.#.#.#.#.#.#.#.....#.......#.#.#.#.#...#.#...#...#.......#.......#.#...............#.#.#.#.....#.......................#...#.......#.#
+#.###.#.#.###.#.###.#.#.#########.#.#.#.###.###.#########.#####.#######.#.#.#######.#.#.###.#.#.#.#.#.#.###.#.#.###.#.#.#.#####.#.#.#####.#.#
+#.#.............................................#.........#...#.....#.....#.....#...#.#...#.#...#.#.....#...#.#.#.....#.#.......#.#.#...#...#
+#.#.###.#####.#######.#####.#.#.###########.#####.#########.#######.#######.###.#.#######.#.###.#.#.#.#.#.###.#.#######.#####.#.#.#.#.#####.#
+#.#.#...#...#...#.....#.#...#.#.#.......#...#.....#.......#...#...#.#...........................#.#.#...#.....#.......#...#.......#.#.#...#.#
+#.#.#.###.#.#####.#####.#.###.#.#.#####.###.#.#.###.#####.#.#.#.#.#.#.#####.#.###.#.#####.###.#.#.#.###.#############.###.#.#.#.###.#.#.#.#.#
+#.#.#...#.#.....#...#...#.#...#.#...#.#.#.....#...#.#.....#.#...............#.....#.#.....#...#.#.#...#...#.......#...#...............#.#...#
+#.#.###.#.#####.###.###.#.###.#.###.#.#.#.#####.#.#.#.###.#.#####.#######.#.#######.#.###.#.#####.###.#.#.#.#####.#.#.#.#####.#.#.###.#.#.###
+#...#...#.#...#...#...#.#...#.#...#.#.#...#...#.#...#...#.#...#...#.......#.......#...#...#.....#...#...#...#...#...#.........#.#...#.#...#.#
+###.#.###.#.#.###.###.#.###.#####.#.#.#######.#.#######.#####.#.###.###.###.###.###.###.#.#####.###.###.#######.###.#########.#.###.#.###.#.#
+#...#...#.#.#...#...#.#...#.#...#.#.#.........#.#...#.#.......#.#...#...#...#.#.#...#.#.#.......#...#.#.#.....#...#.....#...#...#...#...#...#
+#.#####.#.#.###.#.###.#.#.#.#.#.#.#.#.#.#######.#.#.#.#########.#.###.###.#.#.#.#.###.#.#.#######.###.#.###.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#
+#S....#.....#...#.......#.............#...........#...........#.....#.........#.......#...........#.........#...#.....#...#...#...#...#.....#
+#############################################################################################################################################
blob - /dev/null
blob + 23476bde48d78b8972f836f9ccd30634a80af512 (mode 644)
--- /dev/null
+++ src/day-16.lisp
@@ -0,0 +1,78 @@
+(defpackage #:aoc/day-16
+  (:use #:cl #:aoc/utils)
+  (:export #:day-16))
+(in-package #:aoc/day-16)
+
+(defparameter *directions-clockwise* '((1 . 0) (0 . 1)
+                                       (-1 . 0) (0 . -1)))
+(defparameter *directions-counterclockwise* '((1 . 0) (0 . -1)
+                                              (-1 . 0) (0 . 1)))
+
+(defstruct node
+  position
+  direction
+  (cost 0)
+  (parents nil))
+
+(defun node-compare (node-a node-b)
+  (< (node-cost node-a) (node-cost node-b)))
+
+(defun process-next (open-list closed-list next-position next-direction next-cost parent)
+  (when (gethash (list next-position next-direction) closed-list)
+    (return-from process-next nil))
+  (let* ((existing (queue-find open-list (lambda (existing)
+                                           (and (equal (node-position existing) next-position)
+                                                (equal (node-direction existing) next-direction)))))
+         (existing (and existing (q::node-value existing))))
+    (if existing
+        (when (<= next-cost (node-cost existing))
+          (setf (node-parents existing) (if (= next-cost (node-cost existing))
+                                            (cons parent (node-parents existing))
+                                            (list parent))
+                (node-cost existing) next-cost))
+        (qpush open-list (make-node :position next-position
+                                    :direction next-direction
+                                    :cost next-cost
+                                    :parents (list parent))))))
+
+(defun path-length (end-node)
+  (loop with seen = (make-hash-table :test #'equal)
+        for nodes = (list end-node) then (mappend #'node-parents nodes)
+        until (null nodes)
+        do (loop for node in nodes
+                 do (setf (gethash (node-position node) seen) t))
+        finally (return (hash-table-count seen))))
+
+(defun dijkstra (map start end)
+  (loop with open-list = (make-queue :priority-queue :compare #'node-compare)
+        with closed-list = (make-hash-table :test #'equal)
+        initially (qpush open-list (make-node :position start
+                                              :direction (first *directions-clockwise*)))
+        while (> (qsize open-list) 0)
+        for current = (qpop open-list)
+        for current-pos = (node-position current)
+        for current-dir = (node-direction current)
+        for current-cost = (node-cost current)
+        for next = (point+ current-pos current-dir)
+        when (equal current-pos end)
+          do (return (values current-cost
+                             (path-length current)))
+        do (setf (gethash (list current-pos current-dir) closed-list) t)
+        when (char/= (map-cell map next) #\#)
+          do (process-next open-list closed-list next current-dir (1+ current-cost) current)
+        do (process-next open-list closed-list current-pos
+                         (or (cadr (member current-dir *directions-clockwise* :test #'equal))
+                             (first *directions-clockwise*))
+                         (+ current-cost 1000)
+                         current)
+           (process-next open-list closed-list current-pos
+                         (or (cadr (member current-dir *directions-counterclockwise* :test #'equal))
+                             (first *directions-counterclockwise*))
+                         (+ current-cost 1000)
+                         current)))
+
+(defun day-16 (input)
+  (let* ((map (make-map input))
+         (start (map-find map #\S))
+         (end (map-find map #\E)))
+    (dijkstra map start end)))
blob - 47b8bae5c57636dded7d94322e776d29b057d45e
blob + 8d9cb790806b0b4492d45670206eaaa30475b759
--- src/utils.lisp
+++ src/utils.lisp
@@ -12,6 +12,7 @@
    #:make-map
    #:make-empty-map
    #:print-map
+   #:map-find
    #:input-map
    #:input-map-width
    #:input-map-height
@@ -140,6 +141,13 @@
                    finally (format stream "~%"))
         else
           do (format stream "~A~%" line)))
+
+(defun map-find (map needle)
+  (loop for y from 0 below (input-map-height map)
+        for line = (aref (input-map-data map) y)
+        for pos = (position needle line)
+        when pos
+          do (return (cons pos y))))
 
 (declaim (inline point+ point- point* point-mod point-x point-y)
          (ftype (function (cons) fixnum) point-x point-y))
blob - /dev/null
blob + a001ffd5c5d659b9cdc48968f0d56e5441c5aab1 (mode 644)
--- /dev/null
+++ t/day-16.lisp
@@ -0,0 +1,45 @@
+(defpackage #:aoc-test/day-16
+  (:use #:cl #:lisp-unit2)
+  (:import-from #:aoc/day-16))
+(in-package #:aoc-test/day-16)
+
+(define-test test-day-16
+    ()
+  (multiple-value-bind (task-1 task-2)
+      (aoc:run-day 16 "###############
+#.......#....E#
+#.#.###.#.###.#
+#.....#.#...#.#
+#.###.#####.#.#
+#.#.#.......#.#
+#.#.#####.###.#
+#...........#.#
+###.#.#####.#.#
+#...#.....#.#.#
+#.#.#.###.#.#.#
+#.....#...#.#.#
+#.###.#.#.#.#.#
+#S..#.....#...#
+###############")
+    (assert= 7036 task-1)
+    (assert= 45 task-2))
+  (multiple-value-bind (task-1 task-2)
+      (aoc:run-day 16 "#################
+#...#...#...#..E#
+#.#.#.#.#.#.#.#.#
+#.#.#.#...#...#.#
+#.#.#.#.###.#.#.#
+#...#.#.#.....#.#
+#.#.#.#.#.#####.#
+#.#...#.#.#.....#
+#.#.#####.#.###.#
+#.#.#.......#...#
+#.#.###.#####.###
+#.#.#...#.....#.#
+#.#.#.#####.###.#
+#.#.#.........#.#
+#.#.#.#########.#
+#S#.............#
+#################")
+    (assert= 11048 task-1)
+    (assert= 64 task-2)))