year2024/
day18.rs

1use std::collections::VecDeque;
2use std::ops::ControlFlow;
3use utils::point::Point2D;
4use utils::prelude::*;
5
6/// Finding when the path through a grid is blocked.
7#[derive(Clone, Debug)]
8pub struct Day18 {
9    blocked_at: Vec<u16>,
10    size: usize,
11    start_idx: usize,
12    end_idx: usize,
13    part1_fallen: u16,
14    total_fallen: u16,
15}
16
17impl Day18 {
18    pub fn new(input: &str, input_type: InputType) -> Result<Self, InputError> {
19        let (max_coord, part1_fallen) = match input_type {
20            InputType::Example => (6, 12),
21            InputType::Real => (70, 1024),
22        };
23        // +1 as max_coord is inclusive, +2 for padding on each side
24        let size = max_coord + 3;
25
26        let mut blocked_at = vec![u16::MAX; size * size];
27        for i in 0..size {
28            blocked_at[i] = 0; // Top
29            blocked_at[(size - 1) * size + i] = 0; // Bottom
30            blocked_at[i * size] = 0; // Left
31            blocked_at[i * size + (size - 1)] = 0; // Right
32        }
33
34        let mut fallen = 0;
35        for item in parser::number_range(0..=max_coord)
36            .then(parser::number_range(0..=max_coord).with_prefix(b','))
37            .map(|(x, y)| Point2D { x, y })
38            .with_consumed()
39            .with_suffix(parser::eol())
40            .parse_iterator(input)
41        {
42            let (pos, line) = item?;
43            if blocked_at[(pos.y + 1) * size + (pos.x + 1)] == u16::MAX {
44                blocked_at[(pos.y + 1) * size + (pos.x + 1)] = fallen;
45                fallen += 1;
46            } else {
47                return Err(InputError::new(input, line, "duplicate position in input"));
48            }
49        }
50
51        Ok(Self {
52            blocked_at,
53            size,
54            start_idx: size + 1,
55            end_idx: (max_coord + 1) * size + (max_coord + 1),
56            part1_fallen,
57            total_fallen: fallen,
58        })
59    }
60
61    #[must_use]
62    pub fn part1(&self) -> u32 {
63        let mut blocked_at = self.blocked_at.clone();
64        let mut queue = VecDeque::new();
65        queue.push_back((self.start_idx, 0));
66
67        while let Some((pos, steps)) = queue.pop_front() {
68            if pos == self.end_idx {
69                return steps;
70            }
71
72            for next in [pos - self.size, pos + 1, pos + self.size, pos - 1] {
73                if blocked_at[next] >= self.part1_fallen {
74                    queue.push_back((next, steps + 1));
75                    blocked_at[next] = 0;
76                }
77            }
78        }
79
80        panic!("no solution found")
81    }
82
83    #[must_use]
84    pub fn part2(&self) -> String {
85        let mut blocked_at = self.blocked_at.clone();
86        let mut reachable = vec![None; self.total_fallen as usize];
87        let mut fallen = self.total_fallen;
88        let mut next = self.start_idx;
89        loop {
90            // Recursively flood fill the reachable grid spaces, tracking which grid spaces would
91            // be reachable at a lower number of fallen bytes.
92            if self
93                .fill(next, fallen, &mut blocked_at, &mut reachable)
94                .is_break()
95            {
96                if fallen == self.total_fallen {
97                    panic!("path is never blocked");
98                }
99                return format!("{},{}", (next % self.size) - 1, (next / self.size) - 1);
100            }
101
102            // No path to the end. Decrease fallen to the value blocking the highest reachable grid
103            // space and try again.
104            fallen = reachable[..fallen as usize]
105                .iter()
106                .rposition(Option::is_some)
107                .expect("no solution found") as u16;
108            next = reachable[fallen as usize].unwrap();
109        }
110    }
111
112    fn fill(
113        &self,
114        pos: usize,
115        fallen: u16,
116        blocked_at: &mut [u16],
117        reachable: &mut [Option<usize>],
118    ) -> ControlFlow<()> {
119        if pos == self.end_idx {
120            return ControlFlow::Break(());
121        }
122
123        for next in [pos - self.size, pos + 1, pos + self.size, pos - 1] {
124            if blocked_at[next] >= fallen {
125                blocked_at[next] = 0;
126                self.fill(next, fallen, blocked_at, reachable)?;
127            } else if blocked_at[next] > 0 {
128                reachable[blocked_at[next] as usize] = Some(next);
129            }
130        }
131
132        ControlFlow::Continue(())
133    }
134}
135
136examples!(Day18 -> (u32, &'static str) [
137    {file: "day18_example0.txt", part1: 22, part2: "6,1"},
138]);
year2024/day18.rs

year2024/
day18.rs
