--- Day 16: Reindeer Maze ---
It's time again for the Reindeer Olympics! This year, the big event is the Reindeer Maze, where the Reindeer compete for the lowest score.
You and The Historians arrive to search for the Chief right as the event is about to start. It wouldn't hurt to watch a little, right?
The Reindeer start on the Start Tile (marked
S) facing East and need to reach the End Tile (markedE). They can move forward one tile at a time (increasing their score by1point), but never into a wall (#). They can also rotate clockwise or counterclockwise 90 degrees at a time (increasing their score by1000points).To figure out the best place to sit, you start by grabbing a map (your puzzle input) from a nearby kiosk. For example:
############### #.......#....E# #.#.###.#.###.# #.....#.#...#.# #.###.#####.#.# #.#.#.......#.# #.#.#####.###.# #...........#.# ###.#.#####.#.# #...#.....#.#.# #.#.#.###.#.#.# #.....#...#.#.# #.###.#.#.#.#.# #S..#.....#...# ###############There are many paths through this maze, but taking any of the best paths would incur a score of only
7036. This can be achieved by taking a total of36steps forward and turning 90 degrees a total of7times:############### #.......#....E# #.#.###.#.###^# #.....#.#...#^# #.###.#####.#^# #.#.#.......#^# #.#.#####.###^# #..>>>>>>>>v#^# ###^#.#####v#^# #>>^#.....#v#^# #^#.#.###.#v#^# #^....#...#v#^# #^###.#.#.#v#^# #S..#.....#>>^# ###############Here's a second example:
################# #...#...#...#..E# #.#.#.#.#.#.#.#.# #.#.#.#...#...#.# #.#.#.#.###.#.#.# #...#.#.#.....#.# #.#.#.#.#.#####.# #.#...#.#.#.....# #.#.#####.#.###.# #.#.#.......#...# #.#.###.#####.### #.#.#...#.....#.# #.#.#.#####.###.# #.#.#.........#.# #.#.#.#########.# #S#.............# #################In this maze, the best paths cost
11048points; following one such path would look like this:################# #...#...#...#..E# #.#.#.#.#.#.#.#^# #.#.#.#...#...#^# #.#.#.#.###.#.#^# #>>v#.#.#.....#^# #^#v#.#.#.#####^# #^#v..#.#.#>>>>^# #^#v#####.#^###.# #^#v#..>>>>^#...# #^#v###^#####.### #^#v#>>^#.....#.# #^#v#^#####.###.# #^#v#^........#.# #^#v#^#########.# #S#>>^..........# #################Note that the path shown above includes one 90 degree turn as the very first move, rotating the Reindeer from facing East to facing North.
Analyze your map carefully. What is the lowest score a Reindeer could possibly get?
First of all, read the input, store the size, and flatten it.
n:count i:read0 `16.txt; show f:raze i "################.......#....E##.#.###.#.###.##.....#.#...#.##.###.#####.#.##..
We now define a variable for the 4 directions, and the start and end positions.
d: (1; n; -1; 0-n); show (S;E):f?"SE" 196 28
Now, we need to find the shortest path from the start to the end, with the added constraint that rotation has a higher "cost".
There are lots of ways to approach this, but the simplest method is to store a 4 by n grid of distances representing the shortest paths so far for each rotation, and update them until it converges.
Firstly, initialise it with a high placeholder value in all positions, other than 0 cost to get to the start, facing east as specified.
show D:.[(4,n*n)#K:99999999;0,S;:;0] 99999999 99999999 99999999 99999999 99999999 99999999 99999999 99999999 99999.. 99999999 99999999 99999999 99999999 99999999 99999999 99999999 99999999 99999.. 99999999 99999999 99999999 99999999 99999999 99999999 99999999 99999999 99999.. 99999999 99999999 99999999 99999999 99999999 99999999 99999999 99999999 99999..
Now, to update our distances, we have several options.
We can perform a rotation, with the cost of 1000, or move in a direction, only costing 1.
The rotations correspond to 1000+1 3 rotate\:D, and the moves are (1+D@'d+\:til count f).
We then take the minimum of this, add our placeholder large value to any wall positions, and fill any null values as well.
SP:{K^(K*f="#")+/:x&(1+x@'d+\:til count f)&/1000+1 3 rotate\:x}
Let's apply this to our distance matrix, and check the end column.
(D:SP over D)[;E] 8036 7036 8036 9036
We see 4 costs, corresponding to 4 rotations.
Let's store the index of the correct rotation, and the minimum cost. This is the answer for part 1.
show M:first de idx: where de=min de: D[;E] 7036
--- Part Two ---
Now that you know what the best paths look like, you can figure out the best spot to sit.
Every non-wall tile (
S,., orE) is equipped with places to sit along the edges of the tile. While determining which of these tiles would be the best spot to sit depends on a whole bunch of factors (how comfortable the seats are, how far away the bathrooms are, whether there's a pillar blocking your view, etc.), the most important factor is whether the tile is on one of the best paths through the maze. If you sit somewhere else, you'd miss all the action!So, you'll need to determine which tiles are part of any best path through the maze, including the
SandEtiles.In the first example, there are
45tiles (markedO) that are part of at least one of the various best paths through the maze:############### #.......#....O# #.#.###.#.###O# #.....#.#...#O# #.###.#####.#O# #.#.#.......#O# #.#.#####.###O# #..OOOOOOOOO#O# ###O#O#####O#O# #OOO#O....#O#O# #O#O#O###.#O#O# #OOOOO#...#O#O# #O###.#.#.#O#O# #O..#.....#OOO# ###############In the second example, there are
64tiles that are part of at least one of the best paths:################# #...#...#...#..O# #.#.#.#.#.#.#.#O# #.#.#.#...#...#O# #.#.#.#.###.#.#O# #OOO#.#.#.....#O# #O#O#.#.#.#####O# #O#O..#.#.#OOOOO# #O#O#####.#O###O# #O#O#..OOOOO#OOO# #O#O###O#####O### #O#O#OOO#..OOO#.# #O#O#O#####O###.# #O#O#OOOOOOO..#.# #O#O#O#########.# #O#OOO..........# #################Analyze your map further. How many tiles are part of at least one of the best paths through the maze?
Now we need to all possible positions on a shortest path.
We don't need to find the paths themselves, but we can check if a position is possible if the distance to the start plus the distance to the end is the minimal distance.
Start by repeating part 1, but now to find distances from the end. The directions will also need to be "reversed" to account for travelling "backwards".
D2:SP over .[(4,n*n)#K;((idx+2)mod 4;E);:;0]
Now, we can count where the distance to the start, D plus the distance from the end (travelling back the other direction) D2 2 3 0 1 is M.
sum any M=D+D2 2 3 0 1 45i
n:count i:read0 `16.txt; f:raze i
d: (1; n; -1; 0-n); (S;E):f?"SE"
D:.[(4,n*n)#K:99999999;0,S;:;0]
SP:{K^(K*f="#")+/:x&(1+x@'d+\:til count f)&/1000+1 3 rotate\:x}
D:SP over D
show M:first de idx: where de=min de: D[;E]
D2:SP over .[(4,n*n)#K;((idx+2)mod 4;E);:;0]
sum any M=D+D2 2 3 0 1