Advent of Code 2024 - Day 21: Keypad Conundrum

:: programming, python, puzzle

 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
 
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:

029A
980A
179A
456A
379A

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:

   +---+---+
    | ^ | A |
+---+---+---+
| < | v | > |
+---+---+---+

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
 
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:

  1. Get lists of paths between each pair of buttons in a sequence.
  2. Translate each path into the directional buttons necessary to navigate the path.
  3. Form the cartesian product to get a list of all the paths from start to end.
1
2
3
4
5
6
 
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:

1
2
3
4
5
6
7
8
 
@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:

1
2
3
4
5
6
7
 
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