commit b80049b66156a9cbb8f881dc7a18b7c4a1642138 parent 4e6f21582d9227d70475791ac29421d5bf3e4f44 Author: Lukas Henkel <lh@entf.net> Date: Mon, 16 Dec 2024 06:50:12 +0100 Day 16 Diffstat:
| A | input/16.txt | | | 141 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/day-16.lisp | | | 78 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | src/utils.lisp | | | 8 | ++++++++ |
| A | t/day-16.lisp | | | 45 | +++++++++++++++++++++++++++++++++++++++++++++ |
4 files changed, 272 insertions(+), 0 deletions(-)
diff --git a/input/16.txt b/input/16.txt @@ -0,0 +1,141 @@ +############################################################################################################################################# +#.........#.............#.....#.....#.....#.........#...#.............#...#.............#.........#.....#...................#.....#.#......E# +#.#######.#.###########.#.###.###.#.#.#.#.#.#.#.###.###.#.###########.#.###.#####.#######.#.###.#.###.#.#.###########.#.###.###.#.#.#.###.### +#.......................#.#.....#.#.#.#.#.#...#...#...#.#.#.......#...#.......................#.#...............#...........................# +#.#.#.#.#####.#####.#.###.#####.#.#.###.#.###.###.###.#.#.#.#.#.###.###.#.###.#.#.#.#########.#.#####.#######.#.#.#.###.#.###.#.#.###.#####.# +#...#.#.#...#.#...#...#...#...#...#...#.#.........#.....#.#.#.#.#...#...#.#...#.#.....#.....#.#.....#.....#.#.#.#.#.....#.............#.....# +#.###.###.#.###.#.#.#####.#.#.#######.#.#####.#.#######.#.#.#.###.###.###.#.###########.###.#######.#.###.#.#.#.#.#####.#.#######.#.###.##### +#.#.#...#.#.....#.#.......#.#...#...#...#...#.#.#...#...#.#.#.....#...#...#.#...#.....#.#.#.........#.#...............#...........#.#.#.....# +#.#.###.#.#######.#######.#.###.#.#######.#.#.#.#.#.#####.#####.#.#.#.#.#.#.#.#.#.###.#.#.###########.#.###.###.#.#.#.#.#####.#####.#.#####.# +#.#...#...................#...#.#.....#...#...#.#.#.....#.......#.#.#.......#.#...#.#.#.#...........#...#.#.#...#...#.#.#...#.....#.......#.# +#.#.#.#.#####.#.#.#.#####.#.###.###.#.#.#####.#.#.#####.#.#####.#.#######.###.#####.#.#.#.#######.#.#.###.#.#.#.#####.#.#.#.#.#######.###.#.# +#...#.#.....#.................................#.#.#.....#.....#.#...........#...#...#...#.#.....#.#.#.#.....#.#.#...#.#.#.#.#.#...#...#.....# +#####.#####.#.#.#####.#.#.#.#.###.###.#.#####.#.#.#####.#######.#########.#.###.###.#####.#.###.###.#.###.###.#.###.#.#.#.#.###.#.#.###.#.#.# +#.#...#...#...#.....#.#.#...#...#...#...#.......#.....#.......#.#.#.........#...#.....#...#...#.....#...#.....#.....#.....#.....#...#...#...# +#.#.###.#.#####.###.###.#.#####.#.#.#####.###########.#######.#.#.#.#####.###.###.#####.#####.#########.#####.#####.###.#############.###.### +#...#...#.#.....#.......#.......#.#.................#.#...#...#.#.#.......#...#.......#.#...#...#...#.........#...#.......#.......#...#.....# +#.###.#####.#.#########.#.#######.###################.#.#.#.###.#.#######.#.#.#######.#.#.#.###.#.#.#.###.#####.#.#####.###.#####.#.###.#.#.# +#.#.#...#...#.....#...#.#.#.....#.#...#.#.............#.#.......#.........#.#.#.....#.#...#...#...#.#.#...#.....#.#...#...#...#.....#...#...# +#.#.#.#.#.#######.#.#.###.#.#.###.#.#.#.#.###########.###########.#######.#.#.#.###.#.#######.#####.#.#.###.#####.#.#.#.#.###.#.###.#.###.#.# +#.#...#.....#...#...#...#.#.#.#...#.#...#.......#...#.#.......#.....#...#.#.#.#.#.......#.....#...#.#.#.#...#...#...#.#.#.....#.#...#...#.#.# +#.#.#########.#.#.###.#.#.#.###.###.###.#######.#.#.#.#.#.###.#######.#.#.###.#.#########.#.#####.#.#.#.#.###.#.#####.#.#######.#.###.#.#.#.# +#.#.....#.....#.#...#...#.#.#...#.....#.....#.#.#.#...#.....#.#.......#.#.....#.........#.........#.#.#.#...#.#.....#.#...............#.#.#.# +#.#####.#.#####.#####.#.#.#.#.#######.#####.#.#.###########.#.#.#######.#######.#######.#######.###.#.#####.#.###.###.#.#####.#.#.#.#.#.#.#.# +#.#.....#...#.#.......#.#.#.#.#.......#...#...#.............#...#.#.....#.....#.#.....#...#.....#...#.......#.....#...#.....#...#.#.#...#.#.# +#.#####.###.#.#########.#.#.#.#.#######.#####.#########.#########.#.###.#.###.#.#####.#.###.#####.###########.#####.###.###.###.#.#.#.###.#.# +#.....#...#.#.........#.#.#.....#...#...#.....#.......#...#.......#.#...#.#.#.#.......#...#.....#.....#...#...#.....#.....#.....#.......#.#.# +#####.#.#.#.#########.#.#.#####.#.###.#.#.#####.#####.###.#.#######.#####.#.#.#######.###.###.#######.#.#.#.#.#.#.#.#########.#.#####.#.#.#.# +#.....#...#.........#.#.#...#.........#.....#...#...#.#.#.#.#.......#.....#.#.......#...#.....#.....#...#...#...#.#...#.......#.....#...#.#.# +#.###.#.#.#.#.#####.#.#.###.#####.###########.###.###.#.#.#.#.#######.#####.#######.#.#########.###.#.#########.#.###.#.###########.#.#.#.#.# +#.#...#...#.....#...#.#.#...#...#...#.........#.....#.#...#.#.......#.#.........#...#.#...........#.#.........#.....#.#.....#.....#...#.#.#.# +#.#.#.#.#.#.#####.###.#.#.###.#.#####.#########.###.#.###.#.#######.#.#.#######.#.#.###.#########.#.#########.#.#####.#####.#.###.###.#.#.### +#...#...#.#.#...#...#.#.#.....#.#...#.#...#...#...#.#...#.#.......#.#.#...#.#...#.#.....#...#...#.#.#.........#...#...#.....#...#...#.#.#...# +#####.#.#.###.#.###.#.#.#######.#.#.#.#.#.#.#.###.#.###.#.###.#.#.#.#.###.#.#.###.#.#####.#.#.#.###.###.#######.#.#.###.#########.#.#.###.#.# +#.#...#.......#.....#...#...#.#.#.#.#.#.#.#.#...#.#...#.#...#.#...#.....#...#...#...#...#.#.#.#...#...#...#...#.#.#.#...#.........#.#...#.#.# +#.#.#.#.#.###.#########.#.#.#.#.#.#.#.#.#.#.###.#.###.#.#.#.#.#########.#######.#####.#.#.#.#.###.###.#.###.#.###.#.#.###.#.#########.#.###.# +#.#.#...#...#.#...#...#...#...#...#.#...#...#...#.#.#...#.#...#.....#.....#...#...#...#...#...#...#...#.#...#...#.#.#.#...#.................# +#.#.###.#.#.#.#.#.#.#.#######.#####.#########.###.#.#####.#.###.###.#####.#.#.#.###.###########.###.#####.#####.#.#.#.#.###########.#.#####.# +#.#...#...#.#.#.#...#.#...#...#...........#...#...#.#.......#...#.#.....#...#...#...............#.#...........#.#.#...#...........#.......#.# +#.###.#.#.#.###.#.###.#.#.###.#.###.#######.###.###.#.###.###.###.#####.#####.###.###.###########.#.#########.#.#.#######.#####.#######.###.# +#...#.#.#.....#.#.#...#.#.....#...#.........#.#.#.....#...#...#...#.....#.....#...#...#...#.....#...#...#...#.#.#.......#.....#.......#.....# +#.#.#.#.#.###.#.#.#.###.###.#.###.#.#.#######.#.#####.#.###.###.###.###########.###.#.#.#.###.#.#.###.#.#.#.#.#.#######.#####.#######.####### +#.#...#.....#...#...#...#...#.#...#.#.#.......#.....#...#...#.......#...........#.....#.#.....#.#.#...#...#.#.#.#.....#.....#.#.......#.....# +#####.###.#.#####.###.#.#.#####.#.###.#####.#.#####.###.#.###.#######.###########.#####.#######.###.#######.###.#.###.#.###.#.#.#####.#.##### +#...#.#...........#.....#.....#.#...#.....#.#.......#...#.............#.........#.#.....#...#...#...#.....#...#...#.#.#...#.#...#.....#.....# +#.#.###.#####.#######.#####.#.#.#.#.###.#.#.###############.###########.#######.#.#.#######.#.###.#######.###.###.#.#.#.#.#######.#####.###.# +#.#...#.#...#.#.......#.....#...#.#...#.#.#...#.............#.#...............#.....#.......#.....#...#.....#...#...#.#.#.......#.....#.#...# +#.###.#.#.###.#.#######.###.###.#.###.###.###.###.###########.#.#####################.###.#.#######.#.#.#######.#####.#####.#########.###.### +#...#...#.....#.......#.#...#.#.#...#.#...#.#...#.....#.......#...#...#.#.........#...#...#.........#.#.#.......#...#.#...#.........#...#...# +###.#####.#####.#####.###.#.#.#.###.#.#.###.###.#.###.#.#####.###.#.#.#.#.#######.#####.#.###########.#.#.#######.#.#.#.#.###.###.#.###.#.#.# +#...#.#.........#...#...#.#...#.#...#.#.#.......#.#.#.......#.......#...#.#...#...#...#.#.#...#.........#.#.......#.#.#.#.#.......#.#...#.#.# +#.###.#.###.#####.#####.#.#####.#.###.#.#.#######.#.#.###################.#.#.#.###.#.#.###.#.#.#######.#.#.#######.#.#.#.#.#######.#.###.#.# +#.#.....#.......#...#...#.#.....#.......#...#...#...#.....#...............#...#.....#.#.....#.#.....#.....#.#.....#...#.#...#.....#.#...#.#.# +#.#.###########.#.#.#.###.#.#####.#########.###.#.#######.#.###############.#.#######.#.###.#.#######.#####.#.#.#######.###.#.###.#.###.###.# +#.#.......#.#...#.#.#.#...#...#.#.........#...#...#.....#...#.........#.....#.......#.#...#.......#...#.....#.#.#.....#.....#...#...#.#.....# +#.#######.#.#.#####.#.#.#.###.#.#.#####.#.###.#####.###.#.#.###.#.###.#.#######.###.#.###.#.#.#.#.#.###.#####.#.#.###.#.###.#######.#.#.#.#.# +#.#.......#.....#...#.#.#.....#.#.....#.#.#.#.......#...#.......#...#.#.........#...#.#.#.#.#.#.#...#.....#...#.#...#...#.#.......#.#.#...#.# +#.#.###########.#.###.#######.#.#.###.###.#.#########.###########.#.#.###.#####.#.#.#.#.#.#.###.#####.###.#.#######.#####.###.###.#.#.#####.# +#.#...#.....#...#.#...#.....#...#.#.#.....#.........#...#...#...#.#.#...#...#.#.#.#...#.#.#.....#.....#...#.#.....#.......#.....#.#.....#...# +#.###.###.#.###.#.#.###.###.#####.#.#.#######.#.###.###.#.#.#.#.#.#.###.###.#.#.#.#####.#.#############.###.#.#.#.#######.#.#####.#.###.#.### +#.......#.#...#...#.......#...#...#...#.....#.#.#...#...#.#...#...#...#.....#...#...#...#...#.....#.....#...#.#.........#.#.....#.#.....#...# +###.###.#.###.#####.#########.#.#######.###.###.#.###.###.#####.#####.#######.#####.#.#.###.#.###.#.#####.###.#.###.#####.#####.#.#.#######.# +#...#...#.#.#.#...#.#.........#.........#...#...#.#...#.........#.......#.....#.#...#.#...#.......#.#...#.#...#.#...#.....#...#.#.#.#...#.#.# +#.###.###.#.#.#.#.###.###.###############.###.###.#.#.###.#.#.###.#.###.#.#####.#.###.###.#####.###.#.#.#.#.###.#####.#####.#.#.#.#.#.#.#.#.# +#...#.....#.....#.....#...#.........#...#...#.#.....#.....#...#...#.#.#.#.......#.#.......#...#...#...#.#.#.#.#.......#...............#...#.# +#.#.###########.#######.###.#####.#.###.###.#.#####.#####.###.#.###.#.#.#.#######.###.#####.#.###.#####.#.#.#.#######.#####.#.###.#.###.###.# +#.#...#...#...#.#.............#...#.....#...#.....#.#...#...#.#.#...#...#.#.....#...#.......#...#.......#...#...............#...............# +#.###.#.#.#.#.###.#######.#####.#####.###.#.#.###.###.#.###.#.#.#.###.#####.###.#.#.#######.###.#####.###.#########.#########.#.#.#.###.#.### +#.#.#...#...#...#...........#...#.....#...#.....#...#.#.......#.#...#.......#...#.#.......#.#.....#.............#...#.....#...#.#.#...#.#.#.# +#.#.###########.#########.###.#.#####.#.###.#######.#.#########.###.#########.###########.#.#.#####.#.#.#######.#.###.###.###.#.#.#.#.#.#.#.# +#.#.....#.....#...........#...#.....#.#...#.#...#...#.....#.......#.#...#...#...#.........#.#.#.....#...#.........#...#.#.....#.#.#.#.#.#.#.# +#.#####.#.###.#.###.#.#####.#####.#.#####.#.#.#.#.###.#####.#.#####.#.#.#.#.###.#.#########.#.#.#####.#.###########.###.#####.#.###.#.###.#.# +#...#...#.#...#...#.#.#.....#.....#.#...#.#.#.#.#.....#.....#...#...#.#.#.#...#...#...#.....#...#.....#...#.......#.#.......#.#.....#...#.#.# +#.#.#.#.#.#.#.#.#.#.#.#.###.#.###.#.#.#.#.###.#.#######.#####.#.#.###.#####.#######.#.#.#.#.#####.#######.#.#####.#.#.###.###.#.#######.#.#.# +#...#.#.........#.#.#.#...#.#.#...#...#.#.....#.#.....#.#.....#.#...#.#...#.........#...#.#.......#.......#.#...#...#.#...#...#.#.......#.#.# +#.###.###.#######.#.#.###.###.#.#.#####.###.###.#.###.#.#.###.#####.#.#.#.#.#.#########.#.#########.#.#.###.#.#.#####.#####.#####.#####.#.#.# +#.#.......#...#.#.#.#...#.....#.#.....#.....#...#.#.#...#.........#.#...#.#.#.....#...#...#.....#.....#.#...#.#...#.......#.....#.....#.#...# +#.#####.###.#.#.#.#.###.###########.#.#.###.#.#.#.#.#########.#.###.#####.#.#####.###.#####.#.###.###.#.#.#.#.###.###.###.#####.#.###.#####.# +#.....#...#.#.#.#.#.................#.#.#.#.#.#.#.#.........#.#...#...#...#.#...#...#.......#.#.....#...#.#...#.#...#...........#...#.#.....# +#.###.###.#.#.#.#.###.#####.###########.#.#.#.#.#.#####.#.#.#.###.###.#.###.###.###.#####.###.#.#####.###.#####.###.#####.###########.#.##### +#...#.#.....#...#...........#.....#...#.#...#.#.#.#.......#.#.#.....#.....#.....#...#...#...#.#.#...#.........#...#...............#...#.#...# +#.#.#.#########.#.#########.#.###.#.#.#.#####.#.#.#.#######.###.###.#####.#####.#.###.#.#####.#.#.#.###.#####.###.#####.#########.#.#.#.###.# +#.#.#...#.#...#.#.....#...#.#...#.#.#.#.....#.#.#.#...#.........#.#...#.......#.#.....#.......#.#.#...#.#.....#.......#.#...#.....#.#.#...#.# +#.#####.#.#.#.#.#####.###.#.###.#.#.#.#####.#.###.#.#.###.###.###.###.#.#.#####.###########.#.#.#.###.#.###.###.#.###.#.#.#.#.#####.#.###.#.# +#.......#...#.#.#...#...#...#...#...#.....#.#.....#.#...#.#.....#...#...#.#.....#.........#.#...#...#.#...#.....#...#.#.#.#.#...#...#.#.#.#.# +#.#######.###.#.###.###.#####.#########.###.#.#####.###.###.###.#.#####.###.#########.###.#.#.#####.#.###.###.###.#.###.#.###.#.###.#.#.#.#.# +#...#.......#.#.....#...#...#...#.....#...#.......#...#...#.#.#.#...........#.....#...#...#.#.#...#.#...#...#.#...#.....#...........#...#...# +###.#######.#.#.#.###.###.#.###.#.###.###.#####.###.#####.#.#.#.###.#####.###.#.#.#.###.###.###.#.#.###.###.###.###.#######.###############.# +#.#.#...#...#...#.#...#...#.#...#...#...#.....#...#.#.....#.#.#...#...#.#...#.#.#.#.#.#.#.#.....#...#.#.#.......#...#.....#.#.....#.........# +#.#.#.#.#.###.#.#.#.###.###.#.#####.###.###.#####.#.#.###.#.#.###.###.#.###.#.#.#.#.#.#.#.###########.#.#####.#######.###.#.#.###.#.######### +#.#...#.#.#.....#.#.....#...#.#.....#.#.#.#.....#...#.#...#.#...#.#.......#.#.#.#...#.#.....#.............#.#.#.....#...#.#.#.#.#.#.#.......# +#.#####.#.#.#.#.#.#######.###.#.#.###.#.#.#####.#####.#.###.###.#.#######.#.#.#.#####.#.#####.###.###.###.#.#.#.###.###.#.#.#.#.#.#.#.###.#.# +#.......#.#.#...#.....#...#...#.#.#...#...#...#...#...#.#...#...#.......#.#...#...#.#...#.....#.........#.....#.#.#.....#...#...#.#.#.#...#.# +#.#######.#.#.#.###.#.#.###.#####.###.#.#.#.###.#.#.#####.###.#########.#####.#.#.#.#.###.#####.#.#.###.#.###.#.#.#######.#.#.###.#.###.###.# +#.#.#.....#.....#.#...#...#.#.....#...#...#...#.#.#...#...#...........#.#.....#.#.#...#.........#.....#.#...#.#.......#.#.#...#...#.....#.#.# +#.#.#.#####.#.#.#.###.###.#.#.#####.###.###.#.#.#####.#.###.#########.#.#.#######.#.###.#.#.###.###.#.#####.#########.#.#.#.###.#########.#.# +#.#...#...........#...#.#.#...#...#...#.#...#.#.....#...#...#...#.....#.#.#.......#...#.#...#...#...#.....#.....#.....#.#.#...#.......#.#...# +#.#####.#.###.#####.###.#.#####.#.#.#.#.#####.###.#######.#####.#.###.#.#.#.###.#######.#.#.###.#.#.#####.#####.#.#.#.#.#.###.###.###.#.#.### +#.......#...#.........#.........#...#...#.......#.......#.#.....#...#.#...#...#.#.......#.#...#...#.#.........#.#.......#...#...#.#.....#.#.# +###########.#.#######.#.#####.###.#.#####.#####.#######.#.#.###.###.#######.#.###.#######.###.#####.#.#####.#.#.#.#######.#.#.###.###.#.#.#.# +#.#.......#.......#.#.....#...#...#.#.....#...#.#.......#...#...#...#.......#.......#.....#.#.#.....#.#.......#.....#.....#.#.#...#...#.#...# +#.#.#.#######.###.#.#####.#.###.###.#.###.#.#.###.###.#######.###.#.#.###############.#####.#.#######.###.###########.#####.#.#.###.#.#.#.#.# +#.#.#...#.......#.#.......#.......#.#.#.#.#.#...#.#...#.....#.#.#.#.#.#...#.....#.....#.....#...#...#...#...#.......#.#.....#.#.....#.#.#.#.# +#.#.###.#.###.#.#.#.#.#####.#######.#.#.#.#.###.#.#.###.#.###.#.#.#.#.#.###.#.###.#####.###.###.#.#.###.#####.#####.#.#######.#######.###.#.# +#...#...#...#.#.#.#.#.#...#...#.....#...#.....#.#.#.#...#...#.#.#.....#.....#...#...#...#.#.#...#.#.....#...#...#.#.#.#.....#.#.....#...#...# +#.#.#.#####.#.#.#.#.#.#.#.###.#.###########.###.#.###.#####.#.#.#######.#######.###.###.#.#.#.###.#####.#.#.###.#.#.#.#.###.#.#.###.#.#.###.# +#.#.#...#...#.#.#.#.#.#...#...#...#.......#.#...#...#.#...#...#...........#...#...#...#...#...#...#.....#.#...#.#.....#...#.#...#.#.#.#.....# +#.#.###.#.###.#.#.#.#.#.#.#.#####.#.#####.###.#.###.#.###.###.###########.###.#.#####.###.#####.#.#.###.#.#.#.#.#########.#.#####.#.#.####### +#.#...#...#...#...#...#.#.#.....#...#.#...#...#.#...#.....#...................#.....#...#.......#.#.#.#.#.#...#.........#.#.....#...#.......# +#.#.#.#####.#.###.#.###.#.#####.#####.#.###.#.#.#.#######.###.#########.###.#.#####.###.###########.#.#.#.#.#.#.#####.#.#.#.#####.###.###.### +#.#.................#...#.....#.......#.#...#.#...#.....#...#...#.....#.....#.....#...#...#.....#...#.#.....#.#...#...#.#.#.......#...#.....# +#.#.#.#.###.#########.###.###.#.###.###.#.###.#.#.#.###.###.#.#.#.###.#####.#######.#####.#.###.#.###.#####.#.#.#.#.#####.#.#######.#.#.#.#.# +#...#.#...#.........#.#...#.....#.#.#...#...#.#.....#.#...#.#.#.....#...#.#.......#.....#.#...#.#.#.......#.#.#.#.#.......#.....#...#...#.#.# +###.#.###.#.#######.#.#####.#####.#.#.#####.#.#######.#.###.#.#######.#.#.#######.#.###.#.#.###.#.###.#.###.#.#.#.#############.#.#######.#.# +#.#.#...#.........#.#.....#...#.....#.#.....#.#.#.....#.....#...#...#.#.#...#...#.#.#...#...#...#.....#.#...#...#...............#.#.......#.# +#.#.###.###.#.#####.#.###.###.#######.#.#.###.#.#.###.###########.#.###.###.#.#.#.#.#.#######.#########.#.#.#################.###.#.#.###.#.# +#.#.#.......#...#...#.#...#.#.....#...#.#.#...#.....#.............#...#.#...#.#...#.#.......#.......#...#.#.#...#...#.......#.#...#.#...#.#.# +#.#.#.#####.###.#.###.#.#.#.#####.#.###.#.###.###.#.###.#############.#.#.###.#####.#######.#.#.###.#.###.###.#.#.#.#.###.###.#.###.###.#.#.# +#...#.#.......#.#.#...#.#.......#...#.#.#...#.....#.....#...#.......#...#.#.....#.......#...#.....#.#.#.#.....#...#.#.#.#...#.#.....#...#...# +#.#####.###.#.#.#.#####.#######.#####.#.###.#.###.#.#####.#.###.#.#######.#.###.#.#######.#.###.###.#.#.#######.###.#.#.###.#.#####.#.###.#.# +#.#...#.....#.#.........#...#.#...#...#...#.....#.#.......#...#.#.......#.#...#...#...#...#.................#.....#.#.....#.......#.#.#.....# +#.#.#.#####.#.###.#######.#.#.###.#.#####.#####.#.###########.#.#####.#.#.###.#####.#.#.#.#####.#.#########.#####.#.#####.#####.###.#.#.#.#.# +#.#.#.#.....#...#.........#.#...#.#.........#...#.........#...#...#...#.....#.......#...#.#...#.#.................#.....#.#...#...#...#.#.#.# +#.#.#.#.###.###.#.#########.#.#.#.#.#######.#.###########.#.###.###.###.#########.#######.#.#.#.#################.#.#.#.#.#.###.#.###.#.#.#.# +#...#...#.....#.#.......#.#.#.#...#.......#...#.........#.#.#...#...#...#.....#...#.....#...#.#.....#.....#.........#.#.....#...#...#.#.#...# +###########.#.#.#.#####.#.#.#.###########.#.###.#.###.###.#.#.###.#.#####.#.#.#.###.###.#####.#####.#.###.#########.#.#######.#.###.#.#.#.### +#.#.......#.#.#.#.#.....#.#.#.......#...#.#.#.....#.#.#.....#...#.#.......#...#...#.#.#.....#.......#.......#.....#.#.......#.#...#...#.#.#.# +#.#.###.#.#.#.#.#.#.#####.#.#######.#.#.#.#.#.#.#.#.#.#.#########.###.#####.#####.#.#.#####.#.#####.#.#.###.#.###.#.#######.#.#.#######.#.#.# +#...#.#.#.#.#.#.#.#.#.....#.......#.#.#.#.#...#.#...#...#.......#.......#.#...............#.#.#.#.....#.......................#...#.......#.# +#.###.#.#.###.#.###.#.#.#########.#.#.#.###.###.#########.#####.#######.#.#.#######.#.#.###.#.#.#.#.#.#.###.#.#.###.#.#.#.#####.#.#.#####.#.# +#.#.............................................#.........#...#.....#.....#.....#...#.#...#.#...#.#.....#...#.#.#.....#.#.......#.#.#...#...# +#.#.###.#####.#######.#####.#.#.###########.#####.#########.#######.#######.###.#.#######.#.###.#.#.#.#.#.###.#.#######.#####.#.#.#.#.#####.# +#.#.#...#...#...#.....#.#...#.#.#.......#...#.....#.......#...#...#.#...........................#.#.#...#.....#.......#...#.......#.#.#...#.# +#.#.#.###.#.#####.#####.#.###.#.#.#####.###.#.#.###.#####.#.#.#.#.#.#.#####.#.###.#.#####.###.#.#.#.###.#############.###.#.#.#.###.#.#.#.#.# +#.#.#...#.#.....#...#...#.#...#.#...#.#.#.....#...#.#.....#.#...............#.....#.#.....#...#.#.#...#...#.......#...#...............#.#...# +#.#.###.#.#####.###.###.#.###.#.###.#.#.#.#####.#.#.#.###.#.#####.#######.#.#######.#.###.#.#####.###.#.#.#.#####.#.#.#.#####.#.#.###.#.#.### +#...#...#.#...#...#...#.#...#.#...#.#.#...#...#.#...#...#.#...#...#.......#.......#...#...#.....#...#...#...#...#...#.........#.#...#.#...#.# +###.#.###.#.#.###.###.#.###.#####.#.#.#######.#.#######.#####.#.###.###.###.###.###.###.#.#####.###.###.#######.###.#########.#.###.#.###.#.# +#...#...#.#.#...#...#.#...#.#...#.#.#.........#.#...#.#.......#.#...#...#...#.#.#...#.#.#.......#...#.#.#.....#...#.....#...#...#...#...#...# +#.#####.#.#.###.#.###.#.#.#.#.#.#.#.#.#.#######.#.#.#.#########.#.###.###.#.#.#.#.###.#.#.#######.###.#.###.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.# +#S....#.....#...#.......#.............#...........#...........#.....#.........#.......#...........#.........#...#.....#...#...#...#...#.....# +############################################################################################################################################# diff --git a/src/day-16.lisp b/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))) diff --git a/src/utils.lisp b/src/utils.lisp @@ -12,6 +12,7 @@ #:make-map #:make-empty-map #:print-map + #:map-find #:input-map #:input-map-width #:input-map-height @@ -141,6 +142,13 @@ 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)) diff --git a/t/day-16.lisp b/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)))