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

aoc/year2024/
day16.rs
