commit 40d0e7fa0bd499411078dea1a651ddb2d286e9a0 parent 178cf0b10bd07c4f0b2303b5ee9fc67eea3b40aa Author: Lukas Henkel <lh@entf.net> Date: Fri, 20 Dec 2024 07:24:58 +0100 Day 20 Diffstat:
| A | input/20.txt | | | 141 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/day-20.lisp | | | 67 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | t/day-20.lisp | | | 8 | ++++++++ |
3 files changed, 216 insertions(+), 0 deletions(-)
diff --git a/input/20.txt b/input/20.txt @@ -0,0 +1,141 @@ +############################################################################################################################################# +#...#...#.....#...#.......#.....#...#...#...#...............#.......#.....#...#...###...#...#.......#...#...#.......#...#.......#...###...### +#.#.#.#.#.###.#.#.#.#####.#.###.#.#.#.#.#.#.#.#############.#.#####.#.###.#.#.#.#.###.#.#.#.#.#####.#.#.#.#.#.#####.#.#.#.#####.#.#.###.#.### +#.#.#.#.#...#...#...#.....#.#...#.#.#.#.#.#.#.......#...#...#...#...#...#...#...#...#.#.#.#.#.....#...#.#.#...#.....#.#.#.#.....#.#...#.#...# +#.#.#.#.###.#########.#####.#.###.#.#.#.#.#.#######.#.#.#.#####.#.#####.###########.#.#.#.#.#####.#####.#.#####.#####.#.#.#.#####.###.#.###.# +#.#...#...#.........#...#...#...#.#.#.#.#.#.#...###...#.#.#...#.#...#...#...........#.#.#.#.#...#...#...#...#...#...#.#.#.#.#...#.#...#...#.# +#.#######.#########.###.#.#####.#.#.#.#.#.#.#.#.#######.#.#.#.#.###.#.###.###########.#.#.#.#.#.###.#.#####.#.###.#.#.#.#.#.#.#.#.#.#####.#.# +#.#.....#.###...#...#...#.#.....#.#.#.#.#.#...#...#.....#...#...#...#...#.......#...#.#...#.#.#.#...#.#...#.#.....#.#.#.#.#...#.#.#.#...#.#.# +#.#.###.#.###.#.#.###.###.#.#####.#.#.#.#.#######.#.#############.#####.#######.#.#.#.#####.#.#.#.###.#.#.#.#######.#.#.#.#####.#.#.#.#.#.#.# +#.#.#...#.#...#...#...###.#...#...#.#.#.#.......#.#.....#.........#####.......#...#.#.....#.#.#.#...#...#...#.......#.#.#.#.....#.#.#.#.#.#.# +#.#.#.###.#.#######.#####.###.#.###.#.#.#######.#.#####.#.###################.#####.#####.#.#.#.###.#########.#######.#.#.#.#####.#.#.#.#.#.# +#...#...#.#.#.....#.....#.#...#.#...#.#.###.....#.....#.#...#.......#.......#.....#.###...#.#.#.###...#.......#.....#.#.#.#.......#...#...#.# +#######.#.#.#.###.#####.#.#.###.#.###.#.###.#########.#.###.#.#####.#.#####.#####.#.###.###.#.#.#####.#.#######.###.#.#.#.#################.# +###...#.#.#...###.....#.#.#...#.#...#.#...#.........#.#.#...#.#.....#.....#.#...#.#.#...#...#.#.#...#.#.....###...#.#.#...#...........#.....# +###.#.#.#.###########.#.#.###.#.###.#.###.#########.#.#.#.###.#.#########.#.#.#.#.#.#.###.###.#.#.#.#.#####.#####.#.#.#####.#########.#.##### +#...#.#.#...#...#.....#...#...#...#...#...#.......#.#...#...#.#...###...#.#.#.#.#.#.#...#.#...#.#.#.#.#.....#...#.#.#...#...###.....#.#.....# +#.###.#.###.#.#.#.#########.#####.#####.###.#####.#.#######.#.###.###.#.#.#.#.#.#.#.###.#.#.###.#.#.#.#.#####.#.#.#.###.#.#####.###.#.#####.# +#...#.#...#.#.#.#.......#...###...#...#.###.....#.#...#...#...#...#...#...#.#.#.#.#.#...#.#...#...#.#.#.#...#.#.#.#.....#.......#...#.#...#.# +###.#.###.#.#.#.#######.#.#####.###.#.#.#######.#.###.#.#.#####.###.#######.#.#.#.#.#.###.###.#####.#.#.#.#.#.#.#.###############.###.#.#.#.# +#...#...#.#...#.........#.#...#.#...#...#...#...#...#...#...#...###.#.....#.#.#.#.#.#...#.###.....#...#.#.#...#...#.....#.........###...#.#.# +#.#####.#.###############.#.#.#.#.#######.#.#.#####.#######.#.#####.#.###.#.#.#.#.#.###.#.#######.#####.#.#########.###.#.###############.#.# +#.....#...#.....#.......#.#.#.#.#.....#...#.#.....#.#...#...#.....#...#...#.#.#.#.#.....#...#...#.#.....#.....#.....###.#...............#.#.# +#####.#####.###.#.#####.#.#.#.#.#####.#.###.#####.#.#.#.#.#######.#####.###.#.#.#.#########.#.#.#.#.#########.#.#######.###############.#.#.# +#.....#...#.#...#.#.....#...#.#...#...#.#...#...#.#...#.#.#...#...#...#...#.#.#.#.......#...#.#.#.#.#...###...#.......#.#.....#.....#...#.#.# +#.#####.#.#.#.###.#.#########.###.#.###.#.###.#.#.#####.#.#.#.#.###.#.###.#.#.#.#######.#.###.#.#.#.#.#.###.#########.#.#.###.#.###.#.###.#.# +#.....#.#.#.#.#...#.........#.#...#.#...#...#.#.#.....#.#.#.#...#...#.#...#.#.#.###.....#.....#...#...#.....#.........#...###...###...###...# +#####.#.#.#.#.#.###########.#.#.###.#.#####.#.#.#####.#.#.#.#####.###.#.###.#.#.###.#########################.############################### +#...#...#...#.#.###...#.....#.#...#.#...#...#.#.#.....#...#.#...#...#.#...#.#.#.#...#...#.....#...............###...#...#...#.........#.....# +#.#.#########.#.###.#.#.#####.###.#.###.#.###.#.#.#########.#.#.###.#.###.#.#.#.#.###.#.#.###.#.#################.#.#.#.#.#.#.#######.#.###.# +#.#.#...#...#...#...#...#...#.....#.....#...#.#.#.......#...#.#...#.#.###.#...#S#...#.#...###.#.#...###.....#...#.#.#.#.#.#.#.#...#...#.#...# +#.#.#.#.#.#.#####.#######.#.###############.#.#.#######.#.###.###.#.#.###.#########.#.#######.#.#.#.###.###.#.#.#.#.#.#.#.#.#.#.#.#.###.#.### +#.#...#.#.#.#...#.........#...#.........#...#.#...#...#.#.###...#.#.#.....#########...###...#.#.#.#...#...#.#.#.#.#...#.#.#...#.#...#...#...# +#.#####.#.#.#.#.#############.#.#######.#.###.###.#.#.#.#.#####.#.#.#####################.#.#.#.#.###.###.#.#.#.#.#####.#.#####.#####.#####.# +#.....#...#...#.###...#...###...#.....#.#.###.#...#.#.#.#.#...#.#.#.....#####...#####...#.#.#.#.#...#.#...#...#...#...#...#.....#...#...#...# +#####.#########.###.#.#.#.#######.###.#.#.###.#.###.#.#.#.#.#.#.#.#####.#####.#.#####.#.#.#.#.#.###.#.#.###########.#.#####.#####.#.###.#.### +#...#...#.....#.....#...#...#...#...#.#.#.#...#...#.#.#.#.#.#.#.#...#...###...#...#...#.#.#.#.#...#.#.#.#.......#...#...#...###...#...#.#...# +#.#.###.#.###.#############.#.#.###.#.#.#.#.#####.#.#.#.#.#.#.#.###.#.#####.#####.#.###.#.#.#.###.#.#.#.#.#####.#.#####.#.#####.#####.#.###.# +#.#.###...###...#.....#...#.#.#.....#...#...#.....#.#.#.#.#.#.#...#.#.#####.#...#.#.#...#.#.#.#...#.#.#.#.#...#.#.#...#...#...#...#...#.#...# +#.#.###########.#.###.#.#.#.#.###############.#####.#.#.#.#.#.###.#.#.#####.#.#.#.#.#.###.#.#.#.###.#.#.#.#.#.#.#.#.#.#####.#.###.#.###.#.### +#.#...###.....#...###...#.#.#...............#.......#.#.#.#.#.#...#...#####.#.#.#...#...#.#...#.....#...#...#.#.#...#.....#.#...#.#...#.#...# +#.###.###.###.###########.#.###############.#########.#.#.#.#.#.###########.#.#.#######.#.###################.#.#########.#.###.#.###.#.###.# +#...#.....#...#...#...#...#.....#.........#.........#.#.#.#.#.#...#########...#...#.....#.....#...............#...#.......#...#.#.#...#.#...# +###.#######.###.#.#.#.#.#######.#.#######.#########.#.#.#.#.#.###.###############.#.#########.#.#################.#.#########.#.#.#.###.#.### +###.......#.#...#.#.#...#.....#.#.....###.......#...#...#...#...#.#########.......#.....#...#.#.................#...#.......#.#.#.#.#...#...# +#########.#.#.###.#.#####.###.#.#####.#########.#.#############.#.#########.###########.#.#.#.#################.#####.#####.#.#.#.#.#.#####.# +#.........#.#.#...#...#...###.#.......#.......#.#.............#.#.#########.........#...#.#...#...#...#.....#...###...#.....#.#...#...#...#.# +#.#########.#.#.#####.#.#####.#########.#####.#.#############.#.#.#################.#.###.#####.#.#.#.#.###.#.#####.###.#####.#########.#.#.# +#.........#...#.....#...#.....#.........#.....#...............#...###########...#...#...#...#...#.#.#.#...#...#...#...#.#...#.#.........#...# +#########.#########.#####.#####.#########.###################################.#.#.#####.###.#.###.#.#.###.#####.#.###.#.#.#.#.#.############# +#.........#...#...#.......#...#.#.........###...........#####################.#...#...#.#...#...#...#.....#.....#.....#...#...#...#...#.....# +#.#########.#.#.#.#########.#.#.#.###########.#########.#####################.#####.#.#.#.#####.###########.#####################.#.#.#.###.# +#.#...#...#.#...#...........#...#...#...###...#.........#####################...###.#...#.#...#.#...........#...#...#...#...#...#...#...#...# +#.#.#.#.#.#.#######################.#.#.###.###.###############################.###.#####.#.#.#.#.###########.#.#.#.#.#.#.#.#.#.#########.### +#...#...#...#.................#...#...#.....#...#...#...###################E....#...#.....#.#.#...#.....#.....#...#.#.#.#.#.#.#...#.......### +#############.###############.#.#.###########.###.#.#.#.#########################.###.#####.#.#####.###.#.#########.#.#.#.#.#.###.#.######### +###...#.......#.....#...#...#...#.......#...#.....#...#.....###############.......#...#.....#.......#...#.........#.#.#.#.#...#...#.........# +###.#.#.#######.###.#.#.#.#.###########.#.#.###############.###############.#######.###.#############.###########.#.#.#.#.#####.###########.# +#...#...#.......###...#...#...........#.#.#.#...............###############.......#.###.............#.............#...#.#...###...#...#...#.# +#.#######.###########################.#.#.#.#.###################################.#.###############.###################.###.#####.#.#.#.#.#.# +#...#.....#.....###...#...............#...#.#.#...###.........#############.......#.#...............#...............###.....#...#...#...#...# +###.#.#####.###.###.#.#.###################.#.#.#.###.#######.#############.#######.#.###############.#############.#########.#.############# +###...#.....#...#...#.#...................#...#.#.....#.......#...#########...#.....#...#...#...#.....#.....#.....#...........#.............# +#######.#####.###.###.###################.#####.#######.#######.#.###########.#.#######.#.#.#.#.#.#####.###.#.###.#########################.# +#...#...#...#.....#...#.......#...#.......#...#.#.......#...###.#.#####...###...#.......#.#...#...#...#...#...###.#.......#...#.............# +#.#.#.###.#.#######.###.#####.#.#.#.#######.#.#.#.#######.#.###.#.#####.#.#######.#######.#########.#.###.#######.#.#####.#.#.#.############# +#.#.#.....#.#.....#...#.....#.#.#.#.........#...#.#.......#...#.#.#...#.#.#...###.....#...#.........#.....#.....#...###...#.#.#.............# +#.#.#######.#.###.###.#####.#.#.#.###############.#.#########.#.#.#.#.#.#.#.#.#######.#.###.###############.###.#######.###.#.#############.# +#.#...#...#.#.###...#.###...#...#...........#...#...#...#.....#.#...#.#.#.#.#.#...#...#...#...#...#...#...#...#.......#.#...#.#.....#...#...# +#.###.#.#.#.#.#####.#.###.#################.#.#.#####.#.#.#####.#####.#.#.#.#.#.#.#.#####.###.#.#.#.#.#.#.###.#######.#.#.###.#.###.#.#.#.### +#...#...#.#...#.....#.....#.....#...#.....#.#.#.#.....#.#.......#.....#.#...#.#.#.#.#...#.###...#...#...#...#.#.......#...###...###.#.#...### +###.#####.#####.###########.###.#.#.#.###.#.#.#.#.#####.#########.#####.#####.#.#.#.#.#.#.#################.#.#.###################.#.####### +###.....#.....#.............###...#...#...#.#.#.#.....#.#...#...#.#...#.#...#...#.#.#.#.#.#.................#.#.#...#...#...###...#.#.#.....# +#######.#####.#########################.###.#.#.#####.#.#.#.#.#.#.#.#.#.#.#.#####.#.#.#.#.#.#################.#.#.#.#.#.#.#.###.#.#.#.#.###.# +#.....#.#...#.#...............#...#.....#...#.#.#...#.#...#...#...#.#.#.#.#.#.....#...#.#.#.#.............#...#...#...#...#.....#.#...#.#...# +#.###.#.#.#.#.#.#############.#.#.#.#####.###.#.#.#.#.#############.#.#.#.#.#.#########.#.#.#.###########.#.#####################.#####.#.### +#...#...#.#.#...#...........#...#...#...#.....#...#...###...###...#.#.#...#.#.......###...#...###...#...#...#.......#.............#...#.#.### +###.#####.#.#####.#########.#########.#.#################.#.###.#.#.#.#####.#######.#############.#.#.#.#####.#####.#.#############.#.#.#.### +###...#...#...#...###.......#.........#.......#...........#...#.#.#.#...#...#.......#...#...###...#...#.......#...#...#...#...#...#.#.#.#...# +#####.#.#####.#.#####.#######.###############.#.#############.#.#.#.###.#.###.#######.#.#.#.###.###############.#.#####.#.#.#.#.#.#.#.#.###.# +#...#...#.....#.#.....#.......#...............#.#.............#.#.#.#...#...#.#...#...#.#.#.#...#...............#.#...#.#.#.#.#.#.#.#.#.#...# +#.#.#####.#####.#.#####.#######.###############.#.#############.#.#.#.#####.#.#.#.#.###.#.#.#.###.###############.#.#.#.#.#.#.#.#.#.#.#.#.### +#.#.#...#.......#.......#...###.................#...........###.#...#.###...#.#.#.#...#...#...#...#.............#...#...#...#...#...#...#.### +#.#.#.#.#################.#.###############################.###.#####.###.###.#.#.###.#########.###.###########.#########################.### +#.#...#.###...#...#.......#.......................#.....#...#...#...#...#...#...#...#.#...#.....###...........#...#.....#.........#.....#...# +#.#####.###.#.#.#.#.#############################.#.###.#.###.###.#.###.###.#######.#.#.#.#.#################.###.#.###.#.#######.#.###.###.# +#...#...#...#...#...#...#...#...#...........#...#...###...###...#.#...#.....#...#...#...#...#.................###.#.###.#.#...###.#...#.....# +###.#.###.###########.#.#.#.#.#.#.#########.#.#.###############.#.###.#######.#.#.###########.###################.#.###.#.#.#.###.###.####### +#...#.....#...#...#...#.#.#.#.#...#...#...#...#...#####...#...#...###.#.......#...###.....###.....#.............#.#...#.#...#...#...#.......# +#.#########.#.#.#.#.###.#.#.#.#####.#.#.#.#######.#####.#.#.#.#######.#.#############.###.#######.#.###########.#.###.#.#######.###.#######.# +#...#...#...#...#.#.###.#.#...#.....#...#.......#...#...#...#.#.....#.#.........#...#...#.#...###...#.........#.#.....#.........###...#...#.# +###.#.#.#.#######.#.###.#.#####.###############.###.#.#######.#.###.#.#########.#.#.###.#.#.#.#######.#######.#.#####################.#.#.#.# +#...#.#.#.#...#...#.#...#.#...#.........#.....#.#...#.#.......#...#.#...#.......#.#.###.#.#.#.#...###.......#.#.....#...#.......#...#.#.#.#.# +#.###.#.#.#.#.#.###.#.###.#.#.#########.#.###.#.#.###.#.#########.#.###.#.#######.#.###.#.#.#.#.#.#########.#.#####.#.#.#.#####.#.#.#.#.#.#.# +#.#...#.#...#.#.#...#.....#.#...........#.#...#...###.#.....#.....#...#.#.......#.#.#...#...#...#...#.......#.......#.#.#...#...#.#.#...#...# +#.#.###.#####.#.#.#########.#############.#.#########.#####.#.#######.#.#######.#.#.#.#############.#.###############.#.###.#.###.#.######### +#.#.###.#.....#...#...#...#...........###.#.....#...#.#.....#.......#.#.#.......#.#.#.............#.#.........#.....#.#.#...#.....#...#...### +#.#.###.#.#########.#.#.#.###########.###.#####.#.#.#.#.###########.#.#.#.#######.#.#############.#.#########.#.###.#.#.#.###########.#.#.### +#.#.#...#.###...#...#...#.#...#...#...#...#.....#.#.#.#.....#.......#...#.#.......#.#...#.....###.#.#.........#...#...#.#.#.....#...#...#...# +#.#.#.###.###.#.#.#######.#.#.#.#.#.###.###.#####.#.#.#####.#.###########.#.#######.#.#.#.###.###.#.#.###########.#####.#.#.###.#.#.#######.# +#.#.#...#.#...#.#.......#.#.#.#.#.#...#...#.......#.#...#...#...........#.#.#.......#.#...#...#...#.#.#.......###.#.....#.#...#.#.#.........# +#.#.###.#.#.###.#######.#.#.#.#.#.###.###.#########.###.#.#############.#.#.#.#######.#####.###.###.#.#.#####.###.#.#####.###.#.#.########### +#.#.###...#...#.#.......#...#...#.....#...#.........#...#.#...#...#...#.#.#.#...#...#.....#.#...#...#...#...#.....#.......#...#.#...........# +#.#.#########.#.#.#####################.###.#########.###.#.#.#.#.#.#.#.#.#.###.#.#.#####.#.#.###.#######.#.###############.###.###########.# +#.#.#.........#...#...#...#...#.....###...#.#...#...#.#...#.#.#.#.#.#.#.#.#.#...#.#.#...#.#.#...#.#...###.#.#...#.........#...#.#...#.......# +#.#.#.#############.#.#.#.#.#.#.###.#####.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.###.#.#.#.#.#.###.#.#.#.###.#.#.#.#.#######.###.#.#.#.#.####### +#...#...............#...#...#.#.###.#...#.#.#.#.#.#.#.#...#.#.#.#...#.#.#.#.#.#...#.#.#.#.#.....#.#.#...#.#...#...#...###.....#...#...###...# +#############################.#.###.#.#.#.#.#.#.#.#.#.###.#.#.#.#####.#.#.#.#.#.###.#.#.#.#######.#.###.#.#########.#.###################.#.# +#...#...#...#.................#...#.#.#.#.#.#.#.#.#...###.#.#...#...#.#.#.#.#.#.#...#.#.#.......#.#.#...#...........#...#...#...#...#...#.#.# +#.#.#.#.#.#.#.###################.#.#.#.#.#.#.#.#.#######.#.#####.#.#.#.#.#.#.#.#.###.#.#######.#.#.#.#################.#.#.#.#.#.#.#.#.#.#.# +#.#...#...#.#.......#.....#.....#.#.#.#.#.#.#.#...###...#.#.....#.#...#.#.#.#...#.#...#.#...#...#.#.#...#...#.....#...#...#...#...#...#...#.# +#.#########.#######.#.###.#.###.#.#.#.#.#.#.#.#######.#.#.#####.#.#####.#.#.#####.#.###.#.#.#.###.#.###.#.#.#.###.#.#.#####################.# +#.........#.........#...#...#...#.#.#.#.#.#.#.#.......#...#.....#...#...#.#.....#.#.#...#.#.#...#.#.#...#.#.#...#...#.....#.....#.........#.# +#########.#############.#####.###.#.#.#.#.#.#.#.###########.#######.#.###.#####.#.#.#.###.#.###.#.#.#.###.#.###.#########.#.###.#.#######.#.# +#...#...#.#...#...#...#.#.....#...#.#.#.#.#...#...#...#...#.......#.#...#...#...#.#.#.#...#.#...#.#.#.....#.#...#.....#...#.###...###...#...# +#.#.#.#.#.#.#.#.#.#.#.#.#.#####.###.#.#.#.#######.#.#.#.#.#######.#.###.###.#.###.#.#.#.###.#.###.#.#######.#.###.###.#.###.#########.#.##### +#.#...#...#.#.#.#...#...#.....#.###.#.#.#.......#.#.#.#.#.#...#...#...#.#...#...#.#.#.#.#...#.#...#...#.....#.....#...#...#.......#...#.#...# +#.#########.#.#.#############.#.###.#.#.#######.#.#.#.#.#.#.#.#.#####.#.#.#####.#.#.#.#.#.###.#.#####.#.###########.#####.#######.#.###.#.#.# +#.........#.#...###...........#...#...#.#.......#...#...#.#.#.#.#.....#.#...#...#...#...#...#.#...#...#.#...#.....#.....#.#...#...#.#...#.#.# +#########.#.#######.#############.#####.#.###############.#.#.#.#.#####.###.#.#############.#.###.#.###.#.#.#.###.#####.#.#.#.#.###.#.###.#.# +#.........#.....#...#.....#...#...###...#.........#...#...#.#.#.#.....#.#...#.....###.......#...#...###.#.#.#...#.#...#.#.#.#.#.....#.....#.# +#.#############.#.###.###.#.#.#.#####.###########.#.#.#.###.#.#.#####.#.#.#######.###.#########.#######.#.#.###.#.#.#.#.#.#.#.#############.# +#...........#...#...#...#...#.#...#...#...#.....#.#.#...#...#.#.....#.#.#...#...#...#...#...#...#.......#.#.#...#...#.#.#...#.#.........#...# +###########.#.#####.###.#####.###.#.###.#.#.###.#.#.#####.###.#####.#.#.###.#.#.###.###.#.#.#.###.#######.#.#.#######.#.#####.#.#######.#.### +#...........#.#...#.....#.....#...#...#.#.#...#.#.#.#...#...#...#...#...#...#.#.#...###.#.#.#.###...#...#.#.#.......#.#.#.....#.......#...### +#.###########.#.#.#######.#####.#####.#.#.###.#.#.#.#.#.###.###.#.#######.###.#.#.#####.#.#.#.#####.#.#.#.#.#######.#.#.#.###########.####### +#...#...#...#.#.#.......#.....#.....#.#.#...#.#...#.#.#.#...#...#...#.....#...#.#.....#.#.#.#.#.....#.#...#.#...#...#.#.#.#...#.....#.......# +###.#.#.#.#.#.#.#######.#####.#####.#.#.###.#.#####.#.#.#.###.#####.#.#####.###.#####.#.#.#.#.#.#####.#####.#.#.#.###.#.#.#.#.#.###.#######.# +#...#.#.#.#.#.#...#...#.......#...#.#.#...#.#...#...#.#.#...#.....#.#.#...#...#...#...#.#.#...#...#...#.....#.#...###.#.#...#.#...#.#...#...# +#.###.#.#.#.#.###.#.#.#########.#.#.#.###.#.###.#.###.#.###.#####.#.#.#.#.###.###.#.###.#.#######.#.###.#####.#######.#.#####.###.#.#.#.#.### +#.....#...#...###...#.......#...#.#.#.#...#.#...#.#...#.#...###...#.#.#.#.#...###.#.###.#.#.......#.###.....#.......#...#.....#...#.#.#...### +###########################.#.###.#.#.#.###.#.###.#.###.#.#####.###.#.#.#.#.#####.#.###.#.#.#######.#######.#######.#####.#####.###.#.####### +###...#...###...#...#.......#.###.#.#.#...#.#...#...###.#.....#...#.#.#.#.#.###...#...#.#.#.#.....#.....#...#.....#...###.#...#...#.#.......# +###.#.#.#.###.#.#.#.#.#######.###.#.#.###.#.###.#######.#####.###.#.#.#.#.#.###.#####.#.#.#.#.###.#####.#.###.###.###.###.#.#.###.#.#######.# +#...#...#.....#...#...#.....#...#...#...#.#.#...#.......#...#.#...#.#.#.#.#...#.#.....#.#.#...#...#.....#...#...#...#...#.#.#.#...#.#.....#.# +#.#####################.###.###.#######.#.#.#.###.#######.#.#.#.###.#.#.#.###.#.#.#####.#.#####.###.#######.###.###.###.#.#.#.#.###.#.###.#.# +#...#...#...#...#.....#...#...#.......#.#.#.#.#...#...#...#...#.....#.#.#.#...#...#.....#.#.....#...#...###...#...#.#...#.#.#.#.#...#...#.#.# +###.#.#.#.#.#.#.#.###.###.###.#######.#.#.#.#.#.###.#.#.#############.#.#.#.#######.#####.#.#####.###.#.#####.###.#.#.###.#.#.#.#.#####.#.#.# +#...#.#.#.#.#.#.#...#.#...###...#...#.#.#.#.#.#...#.#.#.........#.....#.#.#.......#.#...#.#.#...#...#.#.......#...#.#.#...#.#.#.#.#...#.#.#.# +#.###.#.#.#.#.#.###.#.#.#######.#.#.#.#.#.#.#.###.#.#.#########.#.#####.#.#######.#.#.#.#.#.#.#.###.#.#########.###.#.#.###.#.#.#.#.#.#.#.#.# +#.....#...#...#.....#...#######...#...#...#...###...#...........#.......#.........#...#...#...#.....#...........###...#.....#...#...#...#...# +############################################################################################################################################# diff --git a/src/day-20.lisp b/src/day-20.lisp @@ -0,0 +1,67 @@ +(defpackage #:aoc/day-20 + (:use #:cl #:aoc/utils) + (:export #:day-20)) +(in-package #:aoc/day-20) + +(defparameter *directions* '((1 . 0) (-1 . 0) + (0 . 1) (0 . -1))) + +(defun find-start-end (map) + (loop with start = nil + with end = nil + for y from 0 below (input-map-height map) + thereis (loop for x from 0 below (input-map-width map) + for pos = (cons x y) + for cell = (map-cell map pos) + when (char= #\S cell) + do (setf start pos) + when (char= #\E cell) + do (setf end pos)) + finally (return (values start end)))) + +(defun bfs (map start end) + (loop with width = (input-map-width map) + with height = (input-map-height map) + with queue = (make-queue :simple-queue) + with visited = (make-hash-table :test #'equal) + initially (qpush queue (list start (list start))) + (setf (gethash start visited) t) + for (pos steps) = (qpop queue) + when (null pos) + do (return nil) + when (equal pos end) + do (return (nreverse steps)) + do (loop for dir in *directions* + for next = (point+ pos dir) + when (and (point-in-bounds-p next width height) + (not (gethash next visited)) + (char/= (map-cell map next) #\#)) + do (qpush queue (list next (cons next steps))) + (setf (gethash next visited) t)))) + +(defun count-cheats (steps threshold) + (let ((cache (make-hash-table :test #'equal))) + (loop for remaining-picoseconds downfrom (1- (length steps)) + for step in steps + do (setf (gethash step cache) remaining-picoseconds)) + (loop with task-1 = 0 + with task-2 = 0 + for node on steps + for step-1 = (car node) + for rps-1 = (gethash step-1 cache) + do (loop for step-2 in (cdr node) + for dist = (manhattan-distance step-1 step-2) + for rps-2 = (gethash step-2 cache) + for saved = (- rps-1 (+ rps-2 dist)) + do (when (>= saved threshold) + (when (<= dist 2) + (incf task-1)) + (when (<= dist 20) + (incf task-2)))) + finally (return (values task-1 task-2))))) + +(defun day-20 (input) + (let ((map (make-map input))) + (multiple-value-bind (start end) + (find-start-end map) + (count-cheats (bfs map start end) 100)))) diff --git a/t/day-20.lisp b/t/day-20.lisp @@ -0,0 +1,8 @@ +(defpackage #:aoc-test/day-20 + (:use #:cl #:lisp-unit2) + (:import-from #:aoc/day-20)) +(in-package #:aoc-test/day-20) + +(define-test test-day-20 + () + )