Day 16: Reindeer Maze

2024-12-16

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 (marked E). They can move forward one tile at a time (increasing their score by 1 point), but never into a wall (#). They can also rotate clockwise or counterclockwise 90 degrees at a time (increasing their score by 1000 points).

To figure out the best place to sit, you start by grabbing a map (your puzzle input) from a nearby kiosk. For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
###############
#.......#....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 of 36 steps forward and turning 90 degrees a total of 7 times:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
###############
#.......#....E#
#.#.###.#.###^#
#.....#.#...#^#
#.###.#####.#^#
#.#.#.......#^#
#.#.#####.###^#
#..>>>>>>>>v#^#
###^#.#####v#^#
#>>^#.....#v#^#
#^#.#.###.#v#^#
#^....#...#v#^#
#^###.#.#.#v#^#
#S..#.....#>>^#
###############

Here's a second example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#################
#...#...#...#..E#
#.#.#.#.#.#.#.#.#
#.#.#.#...#...#.#
#.#.#.#.###.#.#.#
#...#.#.#.....#.#
#.#.#.#.#.#####.#
#.#...#.#.#.....#
#.#.#####.#.###.#
#.#.#.......#...#
#.#.###.#####.###
#.#.#...#.....#.#
#.#.#.#####.###.#
#.#.#.........#.#
#.#.#.#########.#
#S#.............#
#################

In this maze, the best paths cost 11048 points; following one such path would look like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#################
#...#...#...#..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?

Steps: 0

Score: 0

The code is fairly messy, but does complete in a reaonably-quick time (~1s).

Previous positions are kept track of as we iterate through the maze. This consumes quite a bit of memory, but makes retrieval of the path trivial.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
interface Position {
    y: number;
    x: number;
}

type Direction = "up" | "down" | "left" | "right";

type StrPosition = `${string},${string}`;

interface NextPosition extends Position {
    prevScore: number;
    direction: Direction;
    prevPositions: Set<StrPosition>;
}

interface ScoredPositions {
    score: number;
    positions: Array<Position>;
}

class Map {
    start: Position;
    end: Position;

    matrix: Array<Array<string>>;
    scoredMatrix: Array<Array<Record<Direction, ScoredPositions>>>;

    finalScore: number | null;
    searching: boolean;
    bestPositions: Set<StrPosition>;

    positionsToCheck: Array<NextPosition>;

    constructor() {
        this.matrix = JSON.parse(JSON.stringify(values));
        this.scoredMatrix = values.map((row) => {
            return row.map(() => {
                return {
                    up: { score: Infinity, positions: [] },
                    down: { score: Infinity, positions: [] },
                    left: { score: Infinity, positions: [] },
                    right: { score: Infinity, positions: [] },
                };
            });
        });

        this.start = { y: -1, x: -1 };
        this.end = { y: -1, x: -1 };

        this.matrix.forEach((row, y) => {
            row.forEach((character, x) => {
                if (character === "S") {
                    this.start = { y, x };
                }

                if (character === "S") {
                    this.end = { y, x };
                }
            });
        });

        this.finalScore = null;
        this.searching = true;
        this.bestPositions = new Set();

        // Start with the start position
        this.positionsToCheck = [
            {
                // Up
                y: this.start.y - 1,
                x: this.start.x,
                prevScore: 1001,
                direction: "up",
                prevPositions: new Set(),
            },
            {
                // Down
                y: this.start.y + 1,
                x: this.start.x,
                prevScore: 1001,
                direction: "down",
                prevPositions: new Set(),
            },
            {
                // Right
                y: this.start.y,
                x: this.start.x + 1,
                prevScore: 1,
                direction: "right",
                prevPositions: new Set(),
            },
        ];
    }

    at({ y, x }: Position) {
        const tile = this.matrix[y]?.[x];

        if (tile === undefined) {
            throw new Error(`Bad position: ${y},${x}`);
        }

        return tile;
    }

    addPositionToCheck(position: NextPosition) {
        // Skip walls
        if (this.at(position) === "#") return;

        const { y, x, direction, prevScore } = position;

        // Add score
        const score = this.scoredMatrix[y]![x]![direction].score;

        if (prevScore < score) {
            // Prune paths
            this.scoredMatrix[y]![x]![direction].score = prevScore;
            this.scoredMatrix[y]![x]![direction].positions = [];
            this.scoredMatrix[y]![x]![direction].positions.push({ y, x });

            this.positionsToCheck.push(position);
        }
    }

    step() {
        // Get a position to check
        const position = this.positionsToCheck.shift();

        if (!position) {
            throw new Error("No positions left to check");
        }

        const tile = this.at(position);

        // Hit a wall, early exit
        if (tile === "#") return;

        if (tile === "E") {
            // Hit the end
            this.finalScore = position.prevScore;

            position.prevPositions.forEach((prevPosition) => {
                this.bestPositions.add(prevPosition);
            });

            this.searching = false;

            return;
        }

        // this.exploreMatrix[position.y]![position.x] = directionCode[position.direction];
        const strPosition: StrPosition = `${position.y},${position.x}`;

        // We've got a valid tile to move to
        // Push into our positions to check
        if (position.direction === "up") {
            // Go in the same direction
            this.addPositionToCheck({
                y: position.y - 1,
                x: position.x,
                prevScore: position.prevScore + 1,
                direction: "up",
                prevPositions: new Set([...position.prevPositions]).add(strPosition),
            });

            // 90 degree turns
            this.addPositionToCheck({
                y: position.y,
                x: position.x - 1,
                prevScore: position.prevScore + 1001,
                direction: "left",
                prevPositions: new Set([...position.prevPositions]).add(strPosition),
            });
            this.addPositionToCheck({
                y: position.y,
                x: position.x + 1,
                prevScore: position.prevScore + 1001,
                direction: "right",
                prevPositions: new Set([...position.prevPositions]).add(strPosition),
            });
        }

        if (position.direction === "down") {
            // Go in the same direction
            this.addPositionToCheck({
                y: position.y + 1,
                x: position.x,
                prevScore: position.prevScore + 1,
                direction: "down",
                prevPositions: new Set([...position.prevPositions]).add(strPosition),
            });

            // 90 degree turns
            this.addPositionToCheck({
                y: position.y,
                x: position.x - 1,
                prevScore: position.prevScore + 1001,
                direction: "left",
                prevPositions: new Set([...position.prevPositions]).add(strPosition),
            });
            this.addPositionToCheck({
                y: position.y,
                x: position.x + 1,
                prevScore: position.prevScore + 1001,
                direction: "right",
                prevPositions: new Set([...position.prevPositions]).add(strPosition),
            });
        }

        if (position.direction === "left") {
            // Go in the same direction
            this.addPositionToCheck({
                y: position.y,
                x: position.x - 1,
                prevScore: position.prevScore + 1,
                direction: "left",
                prevPositions: new Set([...position.prevPositions]).add(strPosition),
            });

            // 90 degree turns
            this.addPositionToCheck({
                y: position.y - 1,
                x: position.x,
                prevScore: position.prevScore + 1001,
                direction: "up",
                prevPositions: new Set([...position.prevPositions]).add(strPosition),
            });
            this.addPositionToCheck({
                y: position.y + 1,
                x: position.x,
                prevScore: position.prevScore + 1001,
                direction: "down",
                prevPositions: new Set([...position.prevPositions]).add(strPosition),
            });
        }

        if (position.direction === "right") {
            // Go in the same direction
            this.addPositionToCheck({
                y: position.y,
                x: position.x + 1,
                prevScore: position.prevScore + 1,
                direction: "right",
                prevPositions: new Set([...position.prevPositions]).add(strPosition),
            });

            // 90 degree turns
            this.addPositionToCheck({
                y: position.y - 1,
                x: position.x,
                prevScore: position.prevScore + 1001,
                direction: "up",
                prevPositions: new Set([...position.prevPositions]).add(strPosition),
            });
            this.addPositionToCheck({
                y: position.y + 1,
                x: position.x,
                prevScore: position.prevScore + 1001,
                direction: "down",
                prevPositions: new Set([...position.prevPositions]).add(strPosition),
            });
        }

        // Resort the positions by lowest score
        this.positionsToCheck.sort((a, b) => a.prevScore - b.prevScore);
    }

    get score() {
        if (this.bestPositions.size === 0) return 0;

        // +2 to include start and end
        return this.bestPositions.size + 2;
    }
}

Now that you know what the best paths look like, you can figure out the best spot to sit.

Every non-wall tile (S, ., or E) 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 S and E tiles.

In the first example, there are 45 tiles (marked O) that are part of at least one of the various best paths through the maze:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
###############
#.......#....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 64 tiles that are part of at least one of the best paths:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#################
#...#...#...#..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?

Steps: 0

Score: 0

The code is nearly identical to Part 1, with some small (but important) changes:

We don't prune paths that have the same score as our best-scoring path on that tile
Once we complete the maze, continue building up paths until we no longer have positions to check in our queue that have a score lower than our best final score

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Map {
    ...
    
    addPositionToCheck(position: NextPosition) {
        // Skip walls
        if (this.at(position) === "#") return;

        const { y, x, direction, prevScore } = position;

        // Add score
        const score = this.scoredMatrix[y]![x]![direction].score;

        if (prevScore < score) {
            // Prune paths
            this.scoredMatrix[y]![x]![direction].score = prevScore;
            this.scoredMatrix[y]![x]![direction].positions = [];
            this.scoredMatrix[y]![x]![direction].positions.push({ y, x });

            this.positionsToCheck.push(position);
        } else if (prevScore === score) {
            // Don't prune paths that have the same score
            this.scoredMatrix[y]![x]![direction].positions.push({ y, x });

            this.positionsToCheck.push(position);
        }
    }

    step() {
        // Get a position to check
        const position = this.positionsToCheck.shift();

        if (!position) {
            throw new Error("No positions left to check");
        }

        const tile = this.at(position);

        // Hit a wall, early exit
        if (tile === "#") return;

        if (this.finalScore && position.prevScore > this.finalScore) {
            // Out of relevant positions to check
            this.searching = false;
            return;
        }

        if (tile === "E") {
            // Hit the end
            this.finalScore = position.prevScore;

            position.prevPositions.forEach((prevPosition) => {
                this.bestPositions.add(prevPosition);
            });

            return;
        }
        
        ...
    }
}

Part 1 Time	Part 1 Rank	Part 2 Time	Part 2 Rank
01:00:26	3,787	23:23:38	17,941

Part 1 was pretty easy! I reworked the code to be much closer to what I've got in Part 2, but my original solution wasn't very different from the end result.

After spending ~4 consecutive hours on Part 2, I decided to call it for the night. It just wasn't clicking for me. I've used Dijkstra's algorithm before, but I just couldn't figure out how to use it here.

I ended up keeping track of the previous positions of the path inside of the lead node. While this isn't very memory-efficient (I'm storing LOTS of sets in memory), it does make the retracing part very straightforward.

Fletcher Easton

Day 16: Reindeer Maze

Part 1 – Prompt #

Part 1 – Solution #

Part 2 – Prompt #

Part 2 – Solution #

Recap #