aoc/year2024/
day16.rs

1//! # Reindeer Maze
2//!
3//! Solves part one and part two simultaneously.
4//!
5//! Part one is a normal [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
6//! search from start to end.
7//!
8//! Part two is a a BFS *backwards* from the end to the finish, tracing the cost exactly
9//! to find all possible paths. This reuses the cost information from the Dijkstra without
10//! requiring any extra state keeping for the paths.
11use crate::util::grid::*;
12use crate::util::point::*;
13use std::collections::VecDeque;
14
15type Input = (i32, usize);
16
17/// Clockwise order starting with facing right.
18const DIRECTIONS: [Point; 4] = [RIGHT, DOWN, LEFT, UP];
19
20pub fn parse(input: &str) -> Input {
21    let grid = Grid::parse(input);
22    let start = grid.find(b'S').unwrap();
23    let end = grid.find(b'E').unwrap();
24
25    // Forwards Dijkstra. Since turns are so much more expensive than moving forward, we can
26    // treat this as a glorified BFS using two priority queues. This is much faster than using
27    // an actual min heap.
28    let mut todo_first = VecDeque::new();
29    let mut todo_second = VecDeque::new();
30    // State is `(position, direction)`.
31    let mut seen = grid.same_size_with([i32::MAX; 4]);
32    let mut lowest = i32::MAX;
33
34    todo_first.push_back((start, 0, 0));
35    seen[start][0] = 0;
36
37    while !todo_first.is_empty() {
38        while let Some((position, direction, cost)) = todo_first.pop_front() {
39            if cost >= lowest {
40                continue;
41            }
42            if position == end {
43                lowest = cost;
44                continue;
45            }
46
47            // -1.rem_euclid(4) = 3
48            let left = (direction + 3) % 4;
49            let right = (direction + 1) % 4;
50            let next = [
51                (position + DIRECTIONS[direction], direction, cost + 1),
52                (position, left, cost + 1000),
53                (position, right, cost + 1000),
54            ];
55
56            for tuple @ (next_position, next_direction, next_cost) in next {
57                if grid[next_position] != b'#' && next_cost < seen[next_position][next_direction] {
58                    // Find the next bucket.
59                    if next_direction == direction {
60                        todo_first.push_back(tuple);
61                    } else {
62                        todo_second.push_back(tuple);
63                    }
64                    seen[next_position][next_direction] = next_cost;
65                }
66            }
67        }
68
69        (todo_first, todo_second) = (todo_second, todo_first);
70    }
71
72    // Backwards BFS
73    let mut todo = VecDeque::new();
74    let mut path = grid.same_size_with(false);
75
76    // Lowest paths can arrive at end node in multiple directions.
77    for direction in 0..4 {
78        if seen[end][direction] == lowest {
79            todo.push_back((end, direction, lowest));
80        }
81    }
82
83    while let Some((position, direction, cost)) = todo.pop_front() {
84        path[position] = true;
85        if position == start {
86            continue;
87        }
88
89        // Reverse direction and subtract cost.
90        let left = (direction + 3) % 4;
91        let right = (direction + 1) % 4;
92        let next = [
93            (position - DIRECTIONS[direction], direction, cost - 1),
94            (position, left, cost - 1000),
95            (position, right, cost - 1000),
96        ];
97
98        for (next_position, next_direction, next_cost) in next {
99            // Trace our cost step by step so it will exactly match possible paths.
100            if next_cost == seen[next_position][next_direction] {
101                todo.push_back((next_position, next_direction, next_cost));
102                // Set cost back to `i32::MAX` to prevent redundant path explorations.
103                seen[next_position][next_direction] = i32::MAX;
104            }
105        }
106    }
107
108    (lowest, path.bytes.iter().filter(|&&b| b).count())
109}
110
111pub fn part1(input: &Input) -> i32 {
112    input.0
113}
114
115pub fn part2(input: &Input) -> usize {
116    input.1
117}
aoc/year2024/day16.rs

aoc/year2024/
day16.rs
