year2018/
day22.rs

1use utils::prelude::*;
2use utils::queue::BucketQueue;
3
4/// Searching a cave with different tools.
5#[derive(Clone, Debug)]
6pub struct Day22 {
7    depth: u32,
8    target_x: usize,
9    target_y: usize,
10}
11
12impl Day22 {
13    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
14        let (depth, target_x, target_y) = parser::u32()
15            .with_prefix("depth: ")
16            .with_eol()
17            .then(parser::number_range(0..=31).with_prefix("target: "))
18            .then(parser::number_range(0..=1021).with_prefix(b','))
19            .parse_complete(input)?;
20
21        Ok(Self {
22            depth,
23            target_x,
24            target_y,
25        })
26    }
27
28    #[must_use]
29    pub fn part1(&self) -> u32 {
30        self.scan::<0>(self.target_x + 1, self.target_y + 1)
31            .iter()
32            .sum()
33    }
34
35    #[must_use]
36    pub fn part2(&self) -> u32 {
37        let width = self.target_x + 75;
38        let height = self.target_y + 75;
39
40        // Pad the edges of the grid with [0; 3] to avoid needing bounds checks (as 0 is always less
41        // than next_time)
42        let mut grid = vec![[u32::MAX; 3]; width * height];
43        for x in 0..width {
44            grid[x] = [0; 3];
45            grid[(height - 1) * width + x] = [0; 3];
46        }
47        for y in 0..height {
48            grid[y * width] = [0; 3];
49            grid[(y + 1) * width - 1] = [0; 3];
50        }
51
52        // Tool indices match the region type where they're invalid (torch = 1 = wet).
53        // Set invalid tools for each region to 0.
54        let scan = self.scan::<1>(width, height);
55        for (times, &region_type) in grid.iter_mut().zip(scan.iter()) {
56            times[region_type as usize] = 0;
57        }
58
59        let start_index = width + 1;
60        let target_index = (self.target_y + 1) * width + self.target_x + 1;
61
62        let mut queue = BucketQueue::<_, 8>::with_capacity(256);
63        // Pack the tool into the bottom 2 bits in the queue entry
64        queue.push(0, start_index << 2 | 1);
65        grid[start_index][1] = 0;
66
67        while let Some((time, packed)) = queue.pop_entry() {
68            let (time, index, tool) = (time as u32, packed >> 2, packed & 3);
69
70            if index == target_index && tool == 1 {
71                return time;
72            }
73
74            if grid[index][tool] != time {
75                continue;
76            }
77
78            let region_type = scan[index] as usize;
79            let other_tool = 3 - tool - region_type;
80
81            for (next_index, next_tool, next_time) in [
82                (index - 1, tool, time + 1),
83                (index + 1, tool, time + 1),
84                (index - width, tool, time + 1),
85                (index + width, tool, time + 1),
86                (index, other_tool, time + 7),
87            ] {
88                if grid[next_index][next_tool] > next_time {
89                    grid[next_index][next_tool] = next_time;
90                    queue.push(next_time as usize, next_index << 2 | next_tool);
91                }
92            }
93        }
94
95        panic!("no solution found")
96    }
97
98    fn scan<const PADDING: usize>(&self, width: usize, height: usize) -> Vec<u32> {
99        // Padding is used by part2 to avoid bounds checks in the main time grid. Also padding
100        // the scan grid keeps indexes consistent between the two grids.
101        let inner_width = width - 2 * PADDING;
102        let inner_height = height - 2 * PADDING;
103        let target_index = (self.target_y + PADDING) * width + self.target_x + PADDING;
104
105        let mut erosion = vec![0u32; width * height];
106
107        let base = PADDING * width + PADDING;
108        for (x, e) in erosion[base..base + inner_width].iter_mut().enumerate() {
109            *e = ((x as u32 * 16807) + self.depth) % 20183;
110        }
111
112        for y in 1..inner_height {
113            let base = (y + PADDING) * width + PADDING;
114
115            let mut prev = ((y as u32 * 48271) + self.depth) % 20183;
116            erosion[base] = prev;
117
118            for index in base + 1..base + inner_width {
119                if index == target_index {
120                    prev = self.depth % 20183;
121                } else {
122                    prev = ((prev * erosion[index - width]) + self.depth) % 20183;
123                }
124                erosion[index] = prev;
125            }
126        }
127
128        erosion.into_iter().map(|x| x % 3).collect()
129    }
130}
131
132examples!(Day22 -> (u32, u32) [
133    {input: "depth: 510\ntarget: 10,10", part1: 114, part2: 45},
134]);
year2018/day22.rs

year2018/
day22.rs
