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            if index == end {
43                break;
44            }
45
46            let Some(next_distance) = distances[index].checked_add(1) else {
47                return Err(InputError::new(input, 0, "path too long"));
48            };
49
50            for offset in [1, cols as isize, -1, -(cols as isize)] {
51                let next = index.wrapping_add_signed(offset);
52                if grid[next] == b'.' && distances[next] == u16::MAX {
53                    distances[next] = next_distance;
54                    queue.push_back(next);
55                }
56            }
57        }
58
59        Ok(Self { distances, cols })
60    }
61
62    #[must_use]
63    pub fn part1(&self) -> u32 {
64        [(0, -2), (2, 0), (0, 2), (-2, 0)]
65            .into_iter()
66            .map(|(x, y)| self.cheat_count(x, y))
67            .sum()
68    }
69
70    #[must_use]
71    pub fn part2(&self) -> u32 {
72        let mut total = 0;
73        for x_offset in -20isize..=20 {
74            let y_limit = 20 - x_offset.abs();
75            for y_offset in -y_limit..=y_limit {
76                total += self.cheat_count(x_offset, y_offset);
77            }
78        }
79        total
80    }
81
82    fn cheat_count(&self, x_offset: isize, y_offset: isize) -> u32 {
83        let cheat_length = (x_offset.unsigned_abs() + y_offset.unsigned_abs()) as u16;
84        let threshold = 101 + cheat_length;
85        if cheat_length == 0 {
86            return 0;
87        }
88
89        let start_index = self.cols * 20 + 20;
90        let end_index = self.distances.len() - start_index;
91        let offset = y_offset * (self.cols as isize) + x_offset;
92
93        self.distances[start_index..end_index]
94            .iter()
95            .zip(self.distances[start_index.wrapping_add_signed(offset)..].iter())
96            .map(|(&current, &target)| {
97                u16::from(target.wrapping_add(1).saturating_sub(current) >= threshold)
98            })
99            .sum::<u16>() as u32
100    }
101}
102
103examples!(Day20 -> (u32, u32) []);
year2024/day20.rs

year2024/
day20.rs
