aoc/year2024/
day21.rs

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

aoc/year2024/
day21.rs
