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, mut grid) = grid::from_str_padded(input, 20, b'#', |b| match b {
15            b'.' | b'#' | b'S' | b'E' => Some(b),
16            _ => None,
17        })?;
18
19        let mut starts = grid.iter().enumerate().filter(|&(_, &b)| b == b'S');
20        let Some((start, _)) = starts.next() else {
21            return Err(InputError::new(input, 0, "expected one start"));
22        };
23        if starts.count() > 0 {
24            return Err(InputError::new(input, 0, "expected one start"));
25        }
26        grid[start] = b'.';
27
28        let mut ends = grid.iter().enumerate().filter(|&(_, &b)| b == b'E');
29        let Some((end, _)) = ends.next() else {
30            return Err(InputError::new(input, 0, "expected one end"));
31        };
32        if ends.count() > 0 {
33            return Err(InputError::new(input, 0, "expected one end"));
34        }
35        grid[end] = b'.';
36
37        let mut distances = vec![u16::MAX; grid.len()];
38        distances[start] = 0;
39        let mut queue = VecDeque::new();
40        queue.push_back(start);
41        while let Some(index) = queue.pop_front()
42            && index != end
43        {
44            let Some(next_distance) = distances[index].checked_add(1) else {
45                return Err(InputError::new(input, 0, "path too long"));
46            };
47
48            for offset in [1, cols as isize, -1, -(cols as isize)] {
49                let next = index.wrapping_add_signed(offset);
50                if grid[next] == b'.' && distances[next] == u16::MAX {
51                    distances[next] = next_distance;
52                    queue.push_back(next);
53                }
54            }
55        }
56
57        Ok(Self { distances, cols })
58    }
59
60    #[must_use]
61    pub fn part1(&self) -> u32 {
62        [(0, -2), (2, 0), (0, 2), (-2, 0)]
63            .into_iter()
64            .map(|(x, y)| self.cheat_count(x, y))
65            .sum()
66    }
67
68    #[must_use]
69    pub fn part2(&self) -> u32 {
70        let mut total = 0;
71        for x_offset in -20isize..=20 {
72            let y_limit = 20 - x_offset.abs();
73            for y_offset in -y_limit..=y_limit {
74                total += self.cheat_count(x_offset, y_offset);
75            }
76        }
77        total
78    }
79
80    fn cheat_count(&self, x_offset: isize, y_offset: isize) -> u32 {
81        let cheat_length = (x_offset.unsigned_abs() + y_offset.unsigned_abs()) as u16;
82        let threshold = 101 + cheat_length;
83        if cheat_length == 0 {
84            return 0;
85        }
86
87        let start_index = self.cols * 20 + 20;
88        let end_index = self.distances.len() - start_index;
89        let offset = y_offset * (self.cols as isize) + x_offset;
90
91        self.distances[start_index..end_index]
92            .iter()
93            .zip(self.distances[start_index.wrapping_add_signed(offset)..].iter())
94            .map(|(&current, &target)| {
95                u16::from(target.wrapping_add(1).saturating_sub(current) >= threshold)
96            })
97            .sum::<u16>() as u32
98    }
99}
100
101examples!(Day20 -> (u32, u32) []);
year2024/day20.rs

year2024/
day20.rs
