Advent of Code 2024-Day 21: Keypad Conundrum
from advent import parse, nx, cross_product, cache, re
# Parse and preprocess graphs -----------------------------------------------------------------
codes = parse(21, list)
ng = nx.DiGraph()
ng.add_edges_from([ (s, d, { 'btn' : c }) for (s, d, c) in [ ('7', '8', '>'), ('7', '4', 'v'),
('8', '9', '>'), ('8', '5', 'v'), ('8', '7', '<'), ('9', '6', 'v'), ('9', '8', '<'), ('4', '5', '>'), ('4', '1', 'v'),
('4', '7', '^'), ('5', '6', '>'), ('5', '2', 'v'), ('5', '4', '<'), ('5', '8', '^'), ('6', '3', 'v'), ('6', '5', '<'),
('6', '9', '^'), ('1', '2', '>'), ('1', '4', '^'), ('2', '3', '>'), ('2', '0', 'v'), ('2', '1', '<'), ('2', '5', '^'),
('3', 'A', 'v'), ('3', '2', '<'), ('3', '6', '^'), ('0', 'A', '>'), ('0', '2', '^'), ('A', '0', '<'), ('A', '3', '^') ] ])
numeric_shortest_paths = dict(nx.all_pairs_all_shortest_paths(ng))
dg = nx.DiGraph()
dg.add_edges_from([ (s, d, { 'btn' : c }) for (s, d, c) in [ ('^', 'A', '>'), ('^', 'v', 'v'), ('A', '>', 'v'), ('A', '^', '<'),
('<', 'v', '>'), ('v', '>', '>'), ('v', '<', '<'), ('v', '^', '^'), ('>', 'v', '<'), ('>', 'A', '^') ]])
directional_shortest_paths = dict(nx.all_pairs_all_shortest_paths(dg))
# ---------------------------------------------------------------------------------------------
def compile_code(g, shortest, code):
translate = lambda g, p: [ g.edges[src, dst]['btn'] for src, dst in zip(p, p[1:]) ] + [ 'A' ]
multi_paths = [ shortest[src][dst] for src, dst in zip(['A']+code, code) ]
buttons = [ [translate(g, path) for path in multi_path] for multi_path in multi_paths ]
return [ [ x for xs in cp for x in xs ] for cp in cross_product(*buttons) ]
@cache
def get_shortest(n, s):
if n == 0:
return len(s)
else:
return min(sum(get_shortest(n-1, phrase)
for phrase in re.findall(r"[>v<^]*?A", "".join(code)))
for code in compile_code(dg, directional_shortest_paths, list(s)))
def solve(n):
numeric_value = lambda code: int("".join(code[0:3]))
shortest_sequence = lambda code: min(get_shortest(n, "".join(compiled))
for compiled in compile_code(ng, numeric_shortest_paths, code))
complexity = lambda code: numeric_value(code) * shortest_sequence(code)
return sum(complexity(code) for code in codes)
# ---------------------------------------------------------------------------------------------
assert solve(2) == 152942
assert solve(25) == 189235298434780
Parsing
Our main input consists of a list of 4 character codes such as:
We're also given a numeric keypad for a door lock as follows:
+---+---+---+
| 7 | 8 | 9 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 0 | A |
+---+---+
and a directional keypad for controlling a robot arm as follows:
We'll parse the codes from a file, but to represent the two keypads, I created directed graphs manually. To speed things up, I precompute all the shortest paths between buttons on the keypad:
codes = parse(21, list)
ng = nx.DiGraph()
ng.add_edges_from([ (s, d, { 'btn' : c }) for (s, d, c) in [ ('7', '8', '>'), ('7', '4', 'v'),
('8', '9', '>'), ('8', '5', 'v'), ('8', '7', '<'), ('9', '6', 'v'), ('9', '8', '<'), ('4', '5', '>'), ('4', '1', 'v'),
('4', '7', '^'), ('5', '6', '>'), ('5', '2', 'v'), ('5', '4', '<'), ('5', '8', '^'), ('6', '3', 'v'), ('6', '5', '<'),
('6', '9', '^'), ('1', '2', '>'), ('1', '4', '^'), ('2', '3', '>'), ('2', '0', 'v'), ('2', '1', '<'), ('2', '5', '^'),
('3', 'A', 'v'), ('3', '2', '<'), ('3', '6', '^'), ('0', 'A', '>'), ('0', '2', '^'), ('A', '0', '<'), ('A', '3', '^') ] ])
numeric_shortest_paths = dict(nx.all_pairs_all_shortest_paths(ng))
dg = nx.DiGraph()
dg.add_edges_from([ (s, d, { 'btn' : c }) for (s, d, c) in [ ('^', 'A', '>'), ('^', 'v', 'v'), ('A', '>', 'v'), ('A', '^', '<'),
('<', 'v', '>'), ('v', '>', '>'), ('v', '<', '<'), ('v', '^', '^'), ('>', 'v', '<'), ('>', 'A', '^') ]])
directional_shortest_paths = dict(nx.all_pairs_all_shortest_paths(dg))
Solution
Our first helper function will be to compile a code. A code is either a list of door keypad buttons, or a list of directional keypad buttons. The idea is to compile this code into the proper sequence of directional keypad buttons. We do this as follows:
- Get lists of paths between each pair of buttons in a sequence.
- Translate each path into the directional buttons necessary to navigate the path.
- Form the cartesian product to get a list of all the paths from start to end.
def compile_code(g, shortest, code):
translate = lambda g, p: [ g.edges[src, dst]['btn'] for src, dst in zip(p, p[1:]) ] + [ 'A' ]
multi_paths = [ shortest[src][dst] for src, dst in zip(['A']+code, code) ]
buttons = [ [translate(g, path) for path in multi_path] for multi_path in multi_paths ]
return [ [ x for xs in cp for x in xs ] for cp in cross_product(*buttons) ]
The meat of the solution is in the function to get the shortest initial sequence for a particular door code. We do
this recursively since there are 2 robots operating directional keypads in part 1 and 25 robots in part 2! We'll
use a memoized function for this, so a key insight I had was that these long sequences of codes are composed of
many small phrases of directional buttons ending with an A (activate) button., so by computing the shortest
sequence computation on these small phrases, we'll have a high percentage of them in the cache:
@cache
def get_shortest(n, s):
if n == 0:
return len(s)
else:
return min(sum(get_shortest(n-1, phrase)
for phrase in re.findall(r"[>v<^]*?A", "".join(code)))
for code in compile_code(dg, directional_shortest_paths, list(s)))
With the above in place, the solve() function simply returns the sum of all the complexity values for
all of the codes:
def solve(n):
numeric_value = lambda code: int("".join(code[0:3]))
shortest_sequence = lambda code: min(get_shortest(n, "".join(compiled))
for compiled in compile_code(ng, numeric_shortest_paths, code))
complexity = lambda code: numeric_value(code) * shortest_sequence(code)
return sum(complexity(code) for code in codes)
New Python Concepts
nx.all_pairs_all_shortest_paths()- Nested list comprehensions e.g.
[ [ x for xs in cp for x in xs ] for cp in cross_product(*buttons) ]
Conclusion
This one took a lot of thought for me! Simply comprehending the task was confusing. I have a pretty good grasp on recursive computing since I use it frequently in Racket, but robots controlling other robots which eventually control the last robot operating the door keypad took some thinking :) It was gratifying to have the "aha!" moment in recognizing the small, cacheable phrases.
I think this solution is very fast, considering it's in Python! The timings are as follows (note: microseconds, not milliseconds!):
- 724 μs create/process numeric keypad graph
- 109 μs create/process directional keypad graph
- 80 μs Part 1
- 82 μs Part 2