aoc/year2024/
day21.rs

1//! # Keypad Conundrum
2//!
3//! Each key sequence always ends in `A`. This means that we can consider each group of button
4//! presses between `A`s independently using a recursive approach with memoization to efficiently
5//! compute the minimum presses needed for any depth of chained robots.
6use std::iter::{once, repeat_n};
7
8use crate::util::hash::*;
9use crate::util::parse::*;
10use crate::util::point::*;
11
12type Input<'a> = (Vec<(&'a str, usize)>, Combinations);
13type Combinations = FastMap<(char, char), Vec<String>>;
14type Cache = FastMap<(char, char, usize), usize>;
15
16/// Convert codes to pairs of the sequence itself with the numeric part.
17/// The pad combinations are the same between both parts so only need to be computed once.
18pub fn parse(input: &str) -> Input<'_> {
19    let pairs = input.lines().zip(input.iter_unsigned()).collect();
20    (pairs, pad_combinations())
21}
22
23pub fn part1(input: &Input<'_>) -> usize {
24    chain(input, 3)
25}
26
27pub fn part2(input: &Input<'_>) -> usize {
28    chain(input, 26)
29}
30
31fn chain(input: &Input<'_>, depth: usize) -> usize {
32    let (pairs, combinations) = input;
33    let cache = &mut FastMap::with_capacity(500);
34    pairs.iter().map(|(code, numeric)| dfs(cache, combinations, code, depth) * numeric).sum()
35}
36
37fn dfs(cache: &mut Cache, combinations: &Combinations, code: &str, depth: usize) -> usize {
38    // Number of presses for the last keypad is just the length of the sequence.
39    if depth == 0 {
40        return code.len();
41    }
42
43    // All keypads start with `A`, either the initial position of the keypad or the trailing `A`
44    // from the previous sequence at this level.
45    let mut previous = 'A';
46    let mut result = 0;
47
48    for current in code.chars() {
49        // Check each pair of characters, memoizing results.
50        let key = (previous, current, depth);
51
52        result += cache.get(&key).copied().unwrap_or_else(|| {
53            // Each transition has either 1 or 2 possibilities.
54            // Pick the sequence that results in the minimum keypresses.
55            let presses = combinations[&(previous, current)]
56                .iter()
57                .map(|next| dfs(cache, combinations, next, depth - 1))
58                .min()
59                .unwrap();
60            cache.insert(key, presses);
61            presses
62        });
63
64        previous = current;
65    }
66
67    result
68}
69
70/// Compute keypresses needed for all possible transitions for both numeric and directional
71/// keypads. There are no distinct pairs shared between the keypads so they can use the same map
72/// without conflict.
73fn pad_combinations() -> Combinations {
74    let numeric_gap = Point::new(0, 3);
75    let numeric_keys = [
76        ('7', Point::new(0, 0)),
77        ('8', Point::new(1, 0)),
78        ('9', Point::new(2, 0)),
79        ('4', Point::new(0, 1)),
80        ('5', Point::new(1, 1)),
81        ('6', Point::new(2, 1)),
82        ('1', Point::new(0, 2)),
83        ('2', Point::new(1, 2)),
84        ('3', Point::new(2, 2)),
85        ('0', Point::new(1, 3)),
86        ('A', Point::new(2, 3)),
87    ];
88
89    let directional_gap = Point::new(0, 0);
90    let directional_keys = [
91        ('^', Point::new(1, 0)),
92        ('A', Point::new(2, 0)),
93        ('<', Point::new(0, 1)),
94        ('v', Point::new(1, 1)),
95        ('>', Point::new(2, 1)),
96    ];
97
98    let mut combinations = FastMap::with_capacity(145);
99    pad_routes(&mut combinations, &numeric_keys, numeric_gap);
100    pad_routes(&mut combinations, &directional_keys, directional_gap);
101    combinations
102}
103
104/// Each route between two keys has 2 possibilities, horizontal first or vertical first.
105/// We skip any route that would cross the gap and also avoid adding the same route twice
106/// when a key is in a straight line (e.g. directly above/below or left/right). For example:
107///
108/// * `7 => A` is only `>>vvv`.
109/// * `1 => 5` is `^>` and `>^`.
110///
111/// We don't consider routes that change direction more than once as these are always longer,
112/// for example `5 => A` ignores the path `v>v`.
113fn pad_routes(combinations: &mut Combinations, pad: &[(char, Point)], gap: Point) {
114    for &(first, from) in pad {
115        for &(second, to) in pad {
116            let horizontal = || move_sequence(from.x, to.x, '>', '<');
117            let vertical = || move_sequence(from.y, to.y, 'v', '^');
118            let routes = combinations.entry((first, second)).or_default();
119
120            if Point::new(from.x, to.y) != gap {
121                routes.push(vertical().chain(horizontal()).chain(once('A')).collect());
122            }
123
124            if from.x != to.x && from.y != to.y && Point::new(to.x, from.y) != gap {
125                routes.push(horizontal().chain(vertical()).chain(once('A')).collect());
126            }
127        }
128    }
129}
130
131fn move_sequence(from: i32, to: i32, positive: char, negative: char) -> impl Iterator<Item = char> {
132    let element = if from < to { positive } else { negative };
133    let count = from.abs_diff(to) as usize;
134    repeat_n(element, count)
135}
aoc/year2024/day21.rs

aoc/year2024/
day21.rs
