year2024/
day06.rs

1use utils::grid;
2use utils::point::Point2D;
3use utils::prelude::*;
4
5/// Finding obstructions to cause infinite loops.
6#[derive(Clone, Debug)]
7pub struct Day06 {
8    pub rows: usize,
9    pub cols: usize,
10    pub grid: Vec<u8>,
11    pub start: Point2D<usize>,
12}
13
14const DIRECTIONS: [Point2D<isize>; 4] = [Point2D::DOWN, Point2D::RIGHT, Point2D::UP, Point2D::LEFT];
15
16impl Day06 {
17    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
18        let (rows, cols, mut grid) = grid::from_str(input, |b| match b {
19            b'.' | b'#' | b'^' => Some(b),
20            _ => None,
21        })?;
22
23        let start_index = grid.iter().position(|&c| c == b'^').unwrap();
24        let start = Point2D::new(start_index % cols, start_index / cols);
25        grid[start_index] = b'.';
26
27        Ok(Self {
28            rows,
29            cols,
30            grid,
31            start,
32        })
33    }
34
35    #[must_use]
36    pub fn part1(&self) -> usize {
37        let mut pos = self.start;
38        let mut dir = 0;
39        let mut visited = vec![false; self.grid.len()];
40        loop {
41            visited[pos.y * self.cols + pos.x] = true;
42
43            let next = pos.wrapping_add_signed(DIRECTIONS[dir]);
44            if next.x >= self.cols || next.y >= self.rows {
45                break;
46            }
47            if self.grid[next.y * self.cols + next.x] == b'#' {
48                dir = (dir + 1) % 4;
49            } else {
50                pos = next;
51            }
52        }
53        visited.iter().filter(|&&c| c).count()
54    }
55
56    #[must_use]
57    pub fn part2(&self) -> usize {
58        let mut pos = self.start;
59        let mut dir = 0;
60        let mut visited = vec![0u8; self.grid.len()];
61        let mut obstructions = vec![false; self.grid.len()];
62        let mut cached_step_counts = vec![[0; 4]; self.grid.len()];
63        loop {
64            visited[pos.y * self.cols + pos.x] |= 1 << dir;
65
66            let next = pos.wrapping_add_signed(DIRECTIONS[dir]);
67            if next.x >= self.cols || next.y >= self.rows {
68                break;
69            }
70
71            if self.grid[next.y * self.cols + next.x] == b'#' {
72                dir = (dir + 1) % 4;
73            } else {
74                if !obstructions[next.y * self.cols + next.x]
75                    && visited[next.y * self.cols + next.x] == 0
76                    && self.check_cycle(next, pos, dir, &visited, &mut cached_step_counts)
77                {
78                    obstructions[next.y * self.cols + next.x] = true;
79                }
80
81                pos = next;
82            }
83        }
84        obstructions.iter().filter(|&&c| c).count()
85    }
86
87    // Combination of two algorithms starting from the current position:
88    // 1) Checking against previously visited states/if position leaves grid
89    // 2) The start of Brent's algorithm for cycle detection as used in 2017 day 6
90    // This also avoids allocating/zeroing/copying a new visited vec
91    fn check_cycle(
92        &self,
93        obstruction: Point2D<usize>,
94        pos: Point2D<usize>,
95        dir: usize,
96        visited: &[u8],
97        cache: &mut [[isize; 4]],
98    ) -> bool {
99        let (mut power, mut lambda) = (1, 1);
100        let (mut tortoise_pos, mut tortoise_dir) = (pos, dir);
101        let (mut hare_pos, mut hare_dir) = (pos, dir);
102
103        loop {
104            if power == lambda {
105                tortoise_pos = hare_pos;
106                tortoise_dir = hare_dir;
107                power *= 2;
108                lambda = 0;
109            }
110            lambda += 1;
111
112            // Advance to the next obstruction
113            if hare_pos.x == obstruction.x || hare_pos.y == obstruction.y {
114                // On the same X or Y line as the temporary obstruction, loop without caching
115                loop {
116                    let next = hare_pos.wrapping_add_signed(DIRECTIONS[hare_dir]);
117                    if next.x >= self.cols || next.y >= self.rows {
118                        // No cycle, hare has left the grid
119                        return false;
120                    }
121                    if self.grid[next.y * self.cols + next.x] == b'#' || next == obstruction {
122                        break;
123                    }
124                    hare_pos = next;
125                }
126            } else {
127                // Temporary obstruction can be ignored as not on the same X or Y line as it
128                let cached_count = &mut cache[hare_pos.y * self.cols + hare_pos.x][hare_dir];
129                if *cached_count > 0 {
130                    // Advanced by the previously cached count
131                    hare_pos = hare_pos.wrapping_add_signed(DIRECTIONS[hare_dir] * *cached_count);
132                    if hare_pos.x >= self.cols || hare_pos.y >= self.rows {
133                        // No cycle, hare has left the grid
134                        return false;
135                    }
136                } else {
137                    // Loop, caching the step count until the next obstruction
138                    loop {
139                        let next = hare_pos.wrapping_add_signed(DIRECTIONS[hare_dir]);
140                        if next.x >= self.cols || next.y >= self.rows {
141                            // No cycle, hare has left the grid
142                            *cached_count += 1;
143                            return false;
144                        }
145                        if self.grid[next.y * self.cols + next.x] == b'#' {
146                            break;
147                        }
148                        hare_pos = next;
149                        *cached_count += 1;
150                    }
151                }
152            }
153
154            hare_dir = (hare_dir + 1) % 4;
155
156            if visited[hare_pos.y * self.cols + hare_pos.x] & (1 << hare_dir) != 0 {
157                // Cycle, hare has reached a previous state from before adding the obstacle
158                return true;
159            }
160            if hare_pos == tortoise_pos && hare_dir == tortoise_dir {
161                // Cycle, hare and tortoise are in the same state
162                return true;
163            }
164        }
165    }
166}
167
168examples!(Day06 -> (usize, usize) [
169    {file: "day06_example0.txt", part1: 41, part2: 6},
170]);
year2024/day06.rs

year2024/
day06.rs
