year2024/
day20.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
use std::collections::VecDeque;
use utils::grid;
use utils::prelude::*;

/// Finding shortcuts phasing through walls in a maze.
#[derive(Clone, Debug)]
pub struct Day20 {
    distances: Vec<u16>,
    cols: usize,
}

impl Day20 {
    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
        let (_, cols, mut grid) = grid::from_str_padded(input, 20, b'#', |b| match b {
            b'.' | b'#' | b'S' | b'E' => Some(b),
            _ => None,
        })?;

        let mut starts = grid.iter().enumerate().filter(|&(_, &b)| b == b'S');
        let Some((start, _)) = starts.next() else {
            return Err(InputError::new(input, 0, "expected one start"));
        };
        if starts.count() > 0 {
            return Err(InputError::new(input, 0, "expected one start"));
        }
        grid[start] = b'.';

        let mut ends = grid.iter().enumerate().filter(|&(_, &b)| b == b'E');
        let Some((end, _)) = ends.next() else {
            return Err(InputError::new(input, 0, "expected one end"));
        };
        if ends.count() > 0 {
            return Err(InputError::new(input, 0, "expected one end"));
        }
        grid[end] = b'.';

        let mut distances = vec![u16::MAX; grid.len()];
        distances[start] = 0;
        let mut queue = VecDeque::new();
        queue.push_back(start);
        while let Some(index) = queue.pop_front() {
            if index == end {
                break;
            }

            let Some(next_distance) = distances[index].checked_add(1) else {
                return Err(InputError::new(input, 0, "path too long"));
            };

            for offset in [1, cols as isize, -1, -(cols as isize)] {
                let next = index.wrapping_add_signed(offset);
                if grid[next] == b'.' && distances[next] == u16::MAX {
                    distances[next] = next_distance;
                    queue.push_back(next);
                }
            }
        }

        Ok(Self { distances, cols })
    }

    #[must_use]
    pub fn part1(&self) -> u32 {
        [(0, -2), (2, 0), (0, 2), (-2, 0)]
            .into_iter()
            .map(|(x, y)| self.cheat_count(x, y))
            .sum()
    }

    #[must_use]
    pub fn part2(&self) -> u32 {
        let mut total = 0;
        for x_offset in -20isize..=20 {
            let y_limit = 20 - x_offset.abs();
            for y_offset in -y_limit..=y_limit {
                total += self.cheat_count(x_offset, y_offset);
            }
        }
        total
    }

    fn cheat_count(&self, x_offset: isize, y_offset: isize) -> u32 {
        let cheat_length = (x_offset.unsigned_abs() + y_offset.unsigned_abs()) as u16;
        let threshold = 101 + cheat_length;
        if cheat_length == 0 {
            return 0;
        }

        let start_index = self.cols * 20 + 20;
        let end_index = self.distances.len() - start_index;
        let offset = y_offset * (self.cols as isize) + x_offset;

        self.distances[start_index..end_index]
            .iter()
            .zip(self.distances[start_index.wrapping_add_signed(offset)..].iter())
            .map(|(&current, &target)| {
                u16::from(target.wrapping_add(1).saturating_sub(current) >= threshold)
            })
            .sum::<u16>() as u32
    }
}

examples!(Day20 -> (u32, u32) []);