Advent of Code

After a small break, I’ve finally got around to finishing day 21. This was a though one for me. It took me a lot of time to really understand how to properly frame the problem. Still not entirely satisfied with my solution, and I don’t want to spend more time on it.

Part 1: robots^3

The puzzle

The inputs are very simple: it’s a list of codes, such as 179A, which are number to press on a numerical keypad which looks like this

The trick is that the code needs to be typed in by a robot, which is itself controlled through a directional keyboard like this:

Where we use the arrows to move the position on the numerical keypad, and the A to press a button. The robot “starts” on the A, so to type in 179A we have to go – for instance – ^<<<A (to go to the 1 from the A and press it), then ^^A for the 7, >>A to press the 9, and finally vvvA to press the A. So far, so good. But then we start stacking robots, so that the first robot (operating the numerical keypad) is operated by a second robot (on a directional keypad) operated by a third robot (on a directional keypad) operated by us (on a directional keypad). So if we want the first robot to press 179A, we have this possible succession (aligning the keypress with the As from the next-in-line):

Unfortunately, there are sometimes different possible paths. The rules specify that we can never go through the “empty cell” in each grid, which limits a little bit the possibities, but every time we go from ^ to > or from A to v (and vice-versa), we can either start with the vertical or with the horizontal move.

The question of the puzzle is: for each code, what is the smallest possible number of moves that we have to input in order to make the first robot enter the code. To answer the puzzle, we need to compute the sum of the number of moves multiplied by the numerical value of each code (e.g. 179 for 179A).

The not-very-good solution

Since I had a fairly hard time understanding what was going on in this problem, I initially tried to just “simulate” the whole thing so that I could observe it. This led to my way-too-long-to-go-through code for part 1 (Gitlab link) which, to summarize, has a Keypad class which basically sees the keypad as a 2D grid (using some of the code from the previous puzzles to handle such things). The most important piece of code in it is what determines how to “expand” a key to press into a sequence of steps for the next robot in the line:

class Keypad:
    ...
    def get_paths(self, to: str) -> set[str]:
        target = self.value_to_position[to]
        if target == self.current:
            return [""]
        
        dh = target.column - self.current.column
        dv = target.row - self.current.row

        seqh = ""
        if dh > 0:
            seqh += ">"*dh
        else:
            seqh += "<"*(-dh)
        seqv = ""
        if dv > 0:
            seqv += "v"*dv
        else:
            seqv += "^"*(-dv)

        paths = set([seqh+seqv, seqv+seqh])
        return [path for path in paths if self.is_possible(path)]

Where value_to_position encodes the position (as a row, column namedtuple) on the keypad of every key. So we look at our current position on the keypad, at where we want to go, and determine the number of horizontal and vertical moves we need to do. We always group the horizontal and vertical steps (as it will always lead to a smaller sequence in the end, since the next robot will be able to press A a few times in a row instead of moving back and forth between keys), so we have a maximum of two different paths: horizontal-then-vertical, or vertical-then-horizontal. We also have an is_possible method which checks if we are going over the forbidden spot on the grid.

With that, we can simulate the whole process – and get the right result for part 1 – even though it is wildly inefficient. But it was a necessary step for me to better understand the problem, which was absolutely necessary for part 2…

Part 2 : robots^25

For part 2, we now have twenty-five robots on the directional keypads (instead of two), plus the single robot on the numerical keypad, and us. The question is the same, but if we try to run our little simulation it completely freezes somewhere around robot number 15 (on my not particularly powerful computer at least). I’m sure there is some way to optimize a little bit, parallelize it or whatever to still make the simulation reach the end, but the point of a puzzle – for me – is to think it through at least a little bit.

The thing that took me a really long time to notice but finally led me to a better solution is that, for the successive directional keypad, we actually only have a relatively small number of possible moves, and that we can look at pairs of moves as somewhat “independent” elements in a sequence. If we go back to our example:

And really start from ROBOT 2, the first move is from A (always the starting point) to ^, so we now that the next robot will have to do “move from A to ^, then press A. Then we go from ^ to < and press A. Then from < to < and press A. Etc., etc. Whatever the sequence of move, we can always split it in these pairs of moves, with a”transition + A” pattern.

The way my simulation code was made really didn’t lend itself to this kind of problem formulation, so I started a new file. The still ugly part is a method that computes a matrix of all possible moves in a keypad, so that moves[a][b] is a list of possible sequences of moves from a to b. For instance, moves['^']['>'] on the directional keyboard should be ['>v', 'v>'].

First, we remake the process from part 1, but this time using this idea of pairwise transitions:

def expand(sequence, moves):
    paths = ['']
    for a,b in pairwise('A'+sequence):
        paths = [p+m+'A' for p in paths for m in moves[a][b]]
    return paths

This code takes a sequence, decomposes it in successive pairs (so 179A is (A, 1), (1, 7), (7, 9), (9, A), always adding an extra A at the front as it’s the starting position of the robot) and expand the pair based on the list of moves, adding an A after the transition to actually press the button. If there are multiple possible paths, they are all returned.

The code is already a bit better, but this is still not helping us go further than about 15 iterations. For that, we need to go recursive:

def rexpand(sequence: str, n: int):
    if n == 0:
        return len(sequence)
    total = 0
    for a,b in pairwise('A'+sequence):
        total += min(rexpand(m + 'A', n-1) for m in directional_moves[a][b])
    return total

The first thing to note here is that we no longer care about actually getting the final sequence. We just keep track of its length. When we reach the end of the recursion, we return the current length of the sequence. Before that, we sum the lengths of the recursively expanded pairs of moves, only keeping the minimum length when several possibilities are present. This alone isn’t enough to go to the solution, but now we have put ourselve in a position where we can use functools.cache. This is a very useful function that stores the result of any call to a given function, so that if we call it again with the same parameters we can just lookup the answer rather than re-computing it. Here, since we have a very limited number of possible moves, we only need to compute each expansion once for each level of the recursion, then in all other possible paths we’ll just have to look-up the answer. To make this magic happen, we just need to import functools.cache, which is a decorator, so we add @cache just before our method definition:

@cache
def rexpand(sequence: str, n: int):
    if n == 0:
        return len(sequence)
    total = 0
    for a,b in pairwise('A'+sequence):
        total += min(rexpand(m + 'A', n-1) for m in directional_moves[a][b])
    return total

complexity = 0
for code in codes:
    paths = expand(code, numerical_moves)
    seqlen = min(rexpand(sequence, 25) for sequence in paths)
    complexity += int(code[:-1])*seqlen
print(complexity)

For the numerical keypad, we still use the simple expand. Then, for the directional keypads, we find the minimum sequence length with a 25-deep recursion. The result is almost instantaneous, despite the sequence length being in the \(10^15\) scale.

I generally don’t like using cache in these puzzles, as I prefer to find a more “handmade” way of bypassing the scaling complexity of the problem (day 11 is a prime example, where cache would have been a lot easier – and to be clear I just hadn’t thought about it before I saw others’ solutions – but I still like my solution better in the end). But in this case putting the problem in such a way that cache became possible was hard enough for me that I don’t mind too much. And it is a very useful tool to keep in my coding arsenal, so practicing it a little bit is nice.