year2024/
day20.rs

1use std::collections::VecDeque;
2use utils::grid;
3use utils::prelude::*;
4
5/// Finding shortcuts phasing through walls in a maze.
6#[derive(Clone, Debug)]
7pub struct Day20 {
8    distances: Vec<u16>,
9    cols: usize,
10}
11
12impl Day20 {
13    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
14        let ((_, cols, grid), start, end) = grid::parse_maze(input, 20)?;
15
16        let mut distances = vec![u16::MAX; grid.len()];
17        distances[start] = 0;
18        let mut queue = VecDeque::new();
19        queue.push_back(start);
20        while let Some(index) = queue.pop_front()
21            && index != end
22        {
23            let Some(next_distance) = distances[index].checked_add(1) else {
24                return Err(InputError::new(input, 0, "path too long"));
25            };
26
27            for offset in [1, cols as isize, -1, -(cols as isize)] {
28                let next = index.wrapping_add_signed(offset);
29                if grid[next] == b'.' && distances[next] == u16::MAX {
30                    distances[next] = next_distance;
31                    queue.push_back(next);
32                }
33            }
34        }
35
36        Ok(Self { distances, cols })
37    }
38
39    #[must_use]
40    pub fn part1(&self) -> u32 {
41        [(0, -2), (2, 0), (0, 2), (-2, 0)]
42            .into_iter()
43            .map(|(x, y)| self.cheat_count(x, y))
44            .sum()
45    }
46
47    #[must_use]
48    pub fn part2(&self) -> u32 {
49        let mut total = 0;
50        for x_offset in -20isize..=20 {
51            let y_limit = 20 - x_offset.abs();
52            for y_offset in -y_limit..=y_limit {
53                total += self.cheat_count(x_offset, y_offset);
54            }
55        }
56        total
57    }
58
59    fn cheat_count(&self, x_offset: isize, y_offset: isize) -> u32 {
60        let cheat_length = (x_offset.unsigned_abs() + y_offset.unsigned_abs()) as u16;
61        let threshold = 101 + cheat_length;
62        if cheat_length == 0 {
63            return 0;
64        }
65
66        let start_index = self.cols * 20 + 20;
67        let end_index = self.distances.len() - start_index;
68        let offset = y_offset * (self.cols as isize) + x_offset;
69
70        self.distances[start_index..end_index]
71            .iter()
72            .zip(self.distances[start_index.wrapping_add_signed(offset)..].iter())
73            .map(|(&current, &target)| {
74                u16::from(target.wrapping_add(1).saturating_sub(current) >= threshold)
75            })
76            .sum::<u16>() as u32
77    }
78}
79
80examples!(Day20 -> (u32, u32) []);
year2024/day20.rs

year2024/
day20.rs
