year2024/
day21.rs

1use utils::point::Point2D;
2use utils::prelude::*;
3
4/// Counting recursive keypad presses.
5#[derive(Clone, Debug)]
6pub struct Day21 {
7    codes: Vec<u16>,
8}
9
10#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
11#[rustfmt::skip]
12enum NumericKeypad {
13    Key7 = 7, Key8 = 8, Key9 = 9,
14    Key4 = 4, Key5 = 5, Key6 = 6,
15    Key1 = 1, Key2 = 2, Key3 = 3,
16              Key0 = 0, Activate = 10,
17}
18
19#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
20#[rustfmt::skip]
21enum DirectionalKeypad {
22              Up   = 0, Activate = 4,
23    Left = 1, Down = 2, Right = 3,
24}
25
26#[cfg(feature = "const_lut")]
27static PART1_MATRIX: [[u64; 11]; 11] = num_matrix(2);
28#[cfg(feature = "const_lut")]
29static PART2_MATRIX: [[u64; 11]; 11] = num_matrix(25);
30
31impl Day21 {
32    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
33        Ok(Self {
34            codes: parser::number_range(0..=999)
35                .with_suffix(b'A')
36                .parse_lines(input)?,
37        })
38    }
39
40    #[must_use]
41    pub fn part1(&self) -> u64 {
42        #[cfg(feature = "const_lut")]
43        return self.complexity(&PART1_MATRIX);
44
45        #[cfg(not(feature = "const_lut"))]
46        return self.complexity(&num_matrix(2));
47    }
48
49    #[must_use]
50    pub fn part2(&self) -> u64 {
51        #[cfg(feature = "const_lut")]
52        return self.complexity(&PART2_MATRIX);
53
54        #[cfg(not(feature = "const_lut"))]
55        return self.complexity(&num_matrix(25));
56    }
57
58    fn complexity(&self, matrix: &[[u64; 11]; 11]) -> u64 {
59        self.codes
60            .iter()
61            .map(|&code| {
62                let digits = [(code % 1000) / 100, (code % 100) / 10, code % 10];
63                let length = matrix[NumericKeypad::Activate as usize][digits[0] as usize]
64                    + matrix[digits[0] as usize][digits[1] as usize]
65                    + matrix[digits[1] as usize][digits[2] as usize]
66                    + matrix[digits[2] as usize][NumericKeypad::Activate as usize];
67                length * code as u64
68            })
69            .sum()
70    }
71}
72
73const fn num_matrix(robots: u32) -> [[u64; NumericKeypad::LEN]; NumericKeypad::LEN] {
74    let mut dir_matrix = [[1; 5]; 5];
75    let mut i = 0;
76    while i < robots {
77        dir_matrix = DirectionalKeypad::cost_matrix(dir_matrix);
78        i += 1;
79    }
80    NumericKeypad::cost_matrix(dir_matrix)
81}
82
83// Use a macro for common functions as trait functions cannot be marked as const
84macro_rules! cost_matrix_functions {
85    () => {
86        const fn cost_matrix(
87            dir_matrix: [[u64; DirectionalKeypad::LEN]; DirectionalKeypad::LEN],
88        ) -> [[u64; Self::LEN]; Self::LEN] {
89            let mut result = [[u64::MAX; Self::LEN]; Self::LEN];
90            let mut i = 0;
91            while i < Self::LEN {
92                result[i][i] = 1;
93                Self::visit(
94                    0,
95                    Self::ALL[i],
96                    DirectionalKeypad::Activate,
97                    Self::ALL[i],
98                    dir_matrix,
99                    &mut result,
100                );
101                i += 1;
102            }
103            result
104        }
105
106        const fn visit(
107            cost: u64,
108            current: Self,
109            parent: DirectionalKeypad,
110            start: Self,
111            dir_matrix: [[u64; DirectionalKeypad::LEN]; DirectionalKeypad::LEN],
112            result: &mut [[u64; Self::LEN]; Self::LEN],
113        ) {
114            let cost_with_activate =
115                cost + dir_matrix[parent as usize][DirectionalKeypad::Activate as usize];
116            if cost_with_activate < result[start as usize][current as usize] {
117                result[start as usize][current as usize] = cost_with_activate;
118            }
119
120            let start_coords = start.coords();
121            let current_coords = current.coords();
122            let current_distance = current_coords.x.abs_diff(start_coords.x)
123                + current_coords.y.abs_diff(start_coords.y);
124
125            let neighbours = current.neighbours();
126            let mut i = 0;
127            while i < neighbours.len() {
128                let (next_parent, next) = neighbours[i];
129                let next_point = next.coords();
130                let next_distance =
131                    next_point.x.abs_diff(start_coords.x) + next_point.y.abs_diff(start_coords.y);
132                if next_distance > current_distance {
133                    Self::visit(
134                        cost + dir_matrix[parent as usize][next_parent as usize],
135                        next,
136                        next_parent,
137                        start,
138                        dir_matrix,
139                        result,
140                    );
141                }
142                i += 1;
143            }
144        }
145    };
146}
147
148impl DirectionalKeypad {
149    const ALL: [Self; 5] = [
150        DirectionalKeypad::Up,
151        DirectionalKeypad::Activate,
152        DirectionalKeypad::Left,
153        DirectionalKeypad::Down,
154        DirectionalKeypad::Right,
155    ];
156    const LEN: usize = 5;
157
158    const fn neighbours(self) -> &'static [(DirectionalKeypad, Self)] {
159        use DirectionalKeypad::*;
160        match self {
161            Up => &[(Right, Activate), (Down, Down)],
162            Activate => &[(Left, Up), (Down, Right)],
163            Left => &[(Right, Down)],
164            Down => &[(Up, Up), (Left, Left), (Right, Right)],
165            Right => &[(Up, Activate), (Left, Down)],
166        }
167    }
168
169    const fn coords(self) -> Point2D<u32> {
170        use DirectionalKeypad::*;
171        match self {
172            Up => Point2D::new(1, 0),
173            Activate => Point2D::new(2, 0),
174            Left => Point2D::new(0, 1),
175            Down => Point2D::new(1, 1),
176            Right => Point2D::new(2, 1),
177        }
178    }
179
180    cost_matrix_functions!();
181}
182
183impl NumericKeypad {
184    const ALL: [Self; 11] = [
185        NumericKeypad::Key7,
186        NumericKeypad::Key8,
187        NumericKeypad::Key9,
188        NumericKeypad::Key4,
189        NumericKeypad::Key5,
190        NumericKeypad::Key6,
191        NumericKeypad::Key1,
192        NumericKeypad::Key2,
193        NumericKeypad::Key3,
194        NumericKeypad::Key0,
195        NumericKeypad::Activate,
196    ];
197    const LEN: usize = 11;
198
199    const fn neighbours(self) -> &'static [(DirectionalKeypad, Self)] {
200        use DirectionalKeypad::{Down, Left, Right, Up};
201        use NumericKeypad::*;
202        match self {
203            Key7 => &[(Right, Key8), (Down, Key4)],
204            Key8 => &[(Left, Key7), (Right, Key9), (Down, Key5)],
205            Key9 => &[(Left, Key8), (Down, Key6)],
206            Key4 => &[(Up, Key7), (Right, Key5), (Down, Key1)],
207            Key5 => &[(Up, Key8), (Left, Key4), (Right, Key6), (Down, Key2)],
208            Key6 => &[(Up, Key9), (Left, Key5), (Down, Key3)],
209            Key1 => &[(Up, Key4), (Right, Key2)],
210            Key2 => &[(Up, Key5), (Left, Key1), (Right, Key3), (Down, Key0)],
211            Key3 => &[(Up, Key6), (Left, Key2), (Down, Activate)],
212            Key0 => &[(Up, Key2), (Right, Activate)],
213            Activate => &[(Up, Key3), (Left, Key0)],
214        }
215    }
216
217    const fn coords(self) -> Point2D<u32> {
218        use NumericKeypad::*;
219        match self {
220            Key7 => Point2D::new(0, 0),
221            Key8 => Point2D::new(1, 0),
222            Key9 => Point2D::new(2, 0),
223            Key4 => Point2D::new(0, 1),
224            Key5 => Point2D::new(1, 1),
225            Key6 => Point2D::new(2, 1),
226            Key1 => Point2D::new(0, 2),
227            Key2 => Point2D::new(1, 2),
228            Key3 => Point2D::new(2, 2),
229            Key0 => Point2D::new(1, 3),
230            Activate => Point2D::new(2, 3),
231        }
232    }
233
234    cost_matrix_functions!();
235}
236
237examples!(Day21 -> (u64, u64) [
238    {input: "029A\n980A\n179A\n456A\n379A", part1: 126384},
239]);
year2024/day21.rs

year2024/
day21.rs
