aoc/year2024/
day06.rs

1//! # Guard Gallivant
2//!
3//! Part two is sped up by pre-computing the next obstacle in each direction from any point in
4//! the grid. If there is nothing left in the way then coordinates outside the grid are used.
5//! One dimensional example:
6//!
7//! ```none
8//!     .#...
9//!     Left: (-1, 2, 2, 2, 2)
10//!     Right: (1, 1, 5, 5, 5)
11//! ```
12//!
13//! This allows us to "shortcut" to each obstacle when looking for cycles. The remaining tricky
14//! part is including the extra obstacle which is different for each point on the guard's path.
15//!
16//! The search can be parallelized across multiple threads as each position is independent.
17use crate::util::grid::*;
18use crate::util::hash::*;
19use crate::util::point::*;
20use crate::util::thread::*;
21
22pub fn parse(input: &str) -> Grid<u8> {
23    Grid::parse(input)
24}
25
26/// Count distinct positions in the guard's path, which will eventually leave the grid.
27pub fn part1(grid: &Grid<u8>) -> usize {
28    let mut grid = grid.clone();
29    let mut position = grid.find(b'^').unwrap();
30    let mut direction = UP;
31    let mut result = 1;
32
33    while grid.contains(position + direction) {
34        if grid[position + direction] == b'#' {
35            direction = direction.clockwise();
36            continue;
37        }
38
39        let next = position + direction;
40
41        // Avoid double counting when the path crosses itself.
42        if grid[next] == b'.' {
43            result += 1;
44            grid[next] = b'^';
45        }
46
47        position = next;
48    }
49
50    result
51}
52
53/// Follow the guard's path, checking every step for a potential cycle.
54pub fn part2(grid: &Grid<u8>) -> usize {
55    let mut grid = grid.clone();
56    let mut position = grid.find(b'^').unwrap();
57    let mut direction = UP;
58    let mut path = Vec::with_capacity(5_000);
59
60    while grid.contains(position + direction) {
61        if grid[position + direction] == b'#' {
62            direction = direction.clockwise();
63        }
64
65        let next = position + direction;
66
67        // Avoid double counting when the path crosses itself.
68        if grid[next] == b'.' {
69            path.push((position, direction));
70            grid[next] = b'^';
71        }
72
73        position = next;
74    }
75
76    // Use as many cores as possible to parallelize the remaining search.
77    let shortcut = Shortcut::from(&grid);
78    let result = spawn_parallel_iterator(&path, |iter| worker(&shortcut, iter));
79    result.into_iter().sum()
80}
81
82fn worker(shortcut: &Shortcut, iter: ParIter<'_, (Point, Point)>) -> usize {
83    let mut seen = FastSet::new();
84    iter.filter(|&&(position, direction)| {
85        seen.clear();
86        is_cycle(shortcut, &mut seen, position, direction)
87    })
88    .count()
89}
90
91fn is_cycle(
92    shortcut: &Shortcut,
93    seen: &mut FastSet<(Point, Point)>,
94    mut position: Point,
95    mut direction: Point,
96) -> bool {
97    let obstacle = position + direction;
98
99    while shortcut.up.contains(position) {
100        // Reaching the same position in the same direction is a cycle.
101        if !seen.insert((position, direction)) {
102            return true;
103        }
104
105        // The tricky part is checking for the new time travelling instigated obstacle.
106        position = match direction {
107            UP => {
108                let next = shortcut.up[position];
109                if position.x == obstacle.x && position.y > obstacle.y && obstacle.y >= next.y {
110                    obstacle - UP
111                } else {
112                    next
113                }
114            }
115            DOWN => {
116                let next = shortcut.down[position];
117                if position.x == obstacle.x && position.y < obstacle.y && obstacle.y <= next.y {
118                    obstacle - DOWN
119                } else {
120                    next
121                }
122            }
123            LEFT => {
124                let next = shortcut.left[position];
125                if position.y == obstacle.y && position.x > obstacle.x && obstacle.x >= next.x {
126                    obstacle - LEFT
127                } else {
128                    next
129                }
130            }
131            RIGHT => {
132                let next = shortcut.right[position];
133                if position.y == obstacle.y && position.x < obstacle.x && obstacle.x <= next.x {
134                    obstacle - RIGHT
135                } else {
136                    next
137                }
138            }
139            _ => unreachable!(),
140        };
141
142        direction = direction.clockwise();
143    }
144
145    false
146}
147
148struct Shortcut {
149    up: Grid<Point>,
150    down: Grid<Point>,
151    left: Grid<Point>,
152    right: Grid<Point>,
153}
154
155impl Shortcut {
156    fn from(grid: &Grid<u8>) -> Self {
157        let mut up = grid.same_size_with(ORIGIN);
158        let mut down = grid.same_size_with(ORIGIN);
159        let mut left = grid.same_size_with(ORIGIN);
160        let mut right = grid.same_size_with(ORIGIN);
161
162        for x in 0..grid.width {
163            let mut last = Point::new(x, -1);
164
165            for y in 0..grid.height {
166                let point = Point::new(x, y);
167                if grid[point] == b'#' {
168                    last = Point::new(x, y + 1);
169                }
170                up[point] = last;
171            }
172        }
173
174        for x in 0..grid.width {
175            let mut last = Point::new(x, grid.height);
176
177            for y in (0..grid.height).rev() {
178                let point = Point::new(x, y);
179                if grid[point] == b'#' {
180                    last = Point::new(x, y - 1);
181                }
182                down[point] = last;
183            }
184        }
185
186        for y in 0..grid.height {
187            let mut last = Point::new(-1, y);
188
189            for x in 0..grid.width {
190                let point = Point::new(x, y);
191                if grid[point] == b'#' {
192                    last = Point::new(x + 1, y);
193                }
194                left[point] = last;
195            }
196        }
197
198        for y in 0..grid.height {
199            let mut last = Point::new(grid.width, y);
200
201            for x in (0..grid.width).rev() {
202                let point = Point::new(x, y);
203                if grid[point] == b'#' {
204                    last = Point::new(x - 1, y);
205                }
206                right[point] = last;
207            }
208        }
209
210        Shortcut { up, down, left, right }
211    }
212}