Advent of Code 2024: Recursive Robotics

What is Advent of Code?

Two years ago, I was introduced to Advent of Code, a series of daily programming challenges released during the month of December.
The puzzles are released every day at 6am CET from December 1st to December 25th. They vary a lot in both complexity and difficulty, though the general trend is, that they get more difficult the closer Christmas is. You can choose any programming language you want to solve them, and there are also no time restrictions. Anyone with basic knowledge about Data Structures, Algorithms and equipped with some skills in any programming language can participate.
The puzzles consist of two parts: In the first part, a description along with some examples are provided. After implementing an algorithm to solve part 1, part 2 usually introduces a slight modification of the problem which often creates the necessity for some heavy optimisation of the algorithm. This is where the challenge mostly lies.

It has become a December tradition for me to check the daily puzzle shortly after waking up. The easy problems can be solved before work, but I won't lie: I have spent quite some hours in the evenings of December to come up with clever algorithms or to find bugs in my existing code.
In December 2024, the day 21 problem stuck out: To me, it felt like the hardest, but also the most enjoyable problem this year. In the following, I want to present my approach to solving it.

Understanding the Problem

Since I am a bit too lazy to give a full description of the problem, I am just going to leave a link to it here: Aoc 2024: Day 21

                    
            +---+---+---+
            | 7 | 8 | 9 |       
            +---+---+---+           +---+---+           +---+---+           +---+---+
            | 4 | 5 | 6 |           | ^ | A |           | ^ | A |           | ^ | A |
            +---+---+---+       +---+---+---+       +---+---+---+       +---+---+---+
            | 1 | 2 | 3 |       | < | v | > |       | < | v | > |       | < | v | > |
            +---+---+---+       +---+---+---+       +---+---+---+       +---+---+---+
                | 0 | A |                   
                +---+---+

               robot 1             robot 2             robot 3              human
                    
                

The different types of keyboards used by the robots. Robot 1 operates on a numeric keyboard, robot 2, 3 as well as the human operate on a directional keyboard.

The structure of such a problem immediately suggests some kind of recursive solution. In my experience, coming up with a recursive algorithm can be just as tough as it is enjoyable.
Before such a solution can be implemented though, one first has to gain an understanding of how a sequence of button presses for one keyboard can be transformed into the corresponding sequence of button presses for the next keyboard.
To break the problem down even further, let's examine first, how a single move from one button to another one on the numeric keyboard is translated into a sequence of button presses on the first directional keyboard.

Suppose, the sequence to be typed on the numeric keyboard is "83A" and the robot is initially pointing at the A-key. Therefore, the first robots arm has to perform three subsequent moves, each ending by pressing the current button:
A->8, 8->3 and 3->A
We will call these moves subsequences.
For now, consider only the first subsequence A->8:
There exist many ways for the first robot to move along its numeric keyboard in order to reach key 8 from key A.
A few such sequences would be:

• A->0->2->5->8
• A->3->6->9->8
• A->0->2->3->6->5->8

For each of these sequences, the robot on the directional keyboard has to press:

• <^^^A
• ^^^<A
• <^>^<^A

The sequences always end with A, since the second robot has to press its A-key in order for the first robot to press the key it is currently pointing at.

Now, the recursive aspect of the problem comes into play: The second robot can't just simply press these keys on its keyboard since it is controlled by a third robot operating on another directional keyboard. Therefore, we have to repeat the operation of figuring out, what buttons the third robot has to press on its directional keyboard for a given sequence of button presses of the second robot.
Considering the first sequence above, <^^^A, and that the third robot also initially points at its keyboards A-key, one sequence of button presses it could perform are <v<A>^AAA>A.
<v<A to move the second roboters pointer from A to < and press it, >^A to continue moving it from < to ^ and press it, AA to press the ^ button another two times, >A to move from ^ to A and press it.

Ok, we have reached the third robot and figured out, what buttons it needs to press to make the second robot press some more buttons to make the first robot press the first sequence of the desired lock combination on the numerical keyboard. Unfortunately, this is not nearly enough to solve the problem, since we have to perform one final recursive step: The human (You or Me!) operates another directional keyboard controlling the third robots arm. Ugh...
I am not going to go through the entire process of button presses, subsequences and robotic arms once more.
Instead, I will just give a brief summary of the chain of actions that we just discussed:

1. The human presses the buttons v<<A>A<A>>^A on his directional keyboard
2. The third robot presses the buttons <v<A on his directional keyboard
3. The second robot presses the buttons < on his directional keyboard
4. The first moves his pointer from key A to key 0 on his numerical keyboard

Now, we just have to implement a solution to traverse through every possible combination of button presses for each robot and find the one leading to the least amount of work for the human.

Implementation

First, we need to implement an algorithm to find the shortest paths between each pair of keys on the numerical and the directional keyboards. A standard BFS algorithm with the addition of storing the chosen paths in a list will do the job. The keyboards will be implemented as dictionaries, with the keys being row-column coordinates and the values being the keyboard buttons.

def get_numeric_keyboard():
    d = {}
    d[(0,0)], d[(0,1)], d[(0,2)], d[(1,0)], d[(1,1)], d[(1,2)], d[(2,0)], d[(2,1)], d[(2,2)], d[(3,1)], d[(3,2)] = "7", "8", "9", "4", "5", "6", "1", "2", "3", "0", "A"
    return d

def get_directional_keyboard():
    d = {}
    d[(0,1)], d[(0,2)], d[(1,0)], d[(1,1)], d[(1,2)] = "^", "A", "<", "v", ">"
    return d

def bfs(start, end, d):
    q = [(start, 0, [], [])]
    min_length = m.inf
    paths = []

    while (q):
        cur_pos, cur_dist, visited, directions = q.pop(0)

        if (cur_pos == end):
            if (cur_dist <= min_length):
                min_length = cur_dist
                paths.append("".join(directions) + "A")
        
        if (cur_pos in visited or cur_dist >= min_length):
            continue

        for n in [(1,0), (-1,0), (0,1), (0,-1)]:
            np = (cur_pos[0]+n[0], cur_pos[1]+n[1])
            if (np in d and np not in visited):
                q.append((np, cur_dist+1, visited + [cur_pos], directions + [dir_dict[n]]))

    return paths
                            

The nice thing about bfs ist, that it will be called only once for each combination of keys for the numerical and directional keyboards at the start of runtime. The resulting paths will be stored in a dictionary so that they can be accessed in the recursive function.
The function get_keyboard_dict takes either the directional or the numeric keyboard as an input and returns a dictionary. Its keys are tuples of keyboard keys and its value is a list of shortest paths between these keys.

def get_keyboard_dict(d):
    return {(k,k_):bfs(k,k_,d) for k in d.keys() for k_ in d.keys()}

numeric_keyboard = get_numeric_keyboard()
directional_keyboard = get_directional_keyboard()
numeric_keyboard_reversed = {v:k for k,v in numeric_keyboard.items()}
directional_keyboard_reversed = {v:k for k,v in directional_keyboard.items()}
directional_keyboard_dict = get_keyboard_dict(directional_keyboard)
numeric_keyboard_dict = get_keyboard_dict(numeric_keyboard)
                    

The core part of the implementation consists of a recursive function, find_combo which calculates the smallest possible number of button presses the human needs to perform on his directional keyboard in order for the first robot with the numeric keyboard to move from one key in its given sequence to another and press it. Summing up the return values of the recursive function for each subsequence of the first robot yields the desired result.
find_combo has three arguments:

• combo is the currently examined subsequence
• c is a counter variable, that tells us the robot that is currently being examined. 1 is the first robot, 2 and 3 are the directional robots.
• c_max is the total number of robots in the chain. It is needed for the exit condition of the recursive function.

@functools.lru_cache(maxsize=None)
def find_combo(combo, c, c_max):                    
    s, e = combo
    if (c == 1):
        s, e = numeric_keyboard_reversed[s], numeric_keyboard_reversed[e]
        p = numeric_keyboard_dict[(s,e)]
    else:
        s, e = directional_keyboard_reversed[s], directional_keyboard_reversed[e]
        p = directional_keyboard_dict[(s,e)]
                            
    # If we are at the last robot, take shortest path
    if (c == c_max):
        return sorted([len(p_) for p_ in p])[0]
    else:
        # The sequences in p need to be formed by yet another robot
        # First, add an "A" to the beginning of each sequence, since the new robot starts at A
        # This A is only needed, becuase the robot needs a first A to form the first combo to the actual first position e.g "<^^". the robot gets to the first < starting from A
        # sum the result for each new combo in the sequence
        # EACH sequence is always finished with A!! thats why we always start from A
        min_val = m.inf
        for p_ in p:
            p__ = list("A"+p_)
            new_combos = list(zip(p__,p__[1:]))
            res = sum(find_combo(nc, c+1, c_max) for nc in new_combos)
            min_val = min(min_val, res)
            return min_val
                                            

In the first part of the recursive function, we examine the current subsequence and determine all possible shortest sequences of button pushes, that the next robot needs to perform in order for the current robot to press the next key. This is done by accessing the dictionaries, which store the results of the calls to the bfs functions.
If c==1, we observe the first roboter by accessing the bfs results fot he numerical keyboard, otherwise we access the results for the directional keyboards.

Next, we check the exit condition of the recursive function: That is, whether we are currently examining the last robot in the chain. If it is indeed the last robot, then the required button presses for the next robot can immediately be pressed by the human and we just have to return the length of the smallest such sequence.

However, if we are at some robot in the middle of the chain, the result sequence needs to be transformed into its subsequences and subsequently be handled by the next robot. The creation of the subsequences is done with the zip function, a nice Python utility.
In other words, for each sequence, we construct its subsequences, call the recursive function for all subsequences with a counter increased by 1, meaning its passed on to the next robot in the chain, and then sum the results. For each set of sequences, we return the sequence with yields the shortest required number of presses for the human.
Take some time to wrap your head around this, it took me a couple of hours to come up with anything remotely reasonable that does the job!

For computational reasons we import the functools module and add the decorator lru_cache to our recursive function. That way, we store intermediate results in a dictionary and can simply access them without having to recompute the same recursive calls multiple times. This significantly reduces the runtime of the program. The initial call to the recursive function is performed based on the input data provided by the puzzle.

And that's pretty much it!

Summing up the the least possible number of button presses for the human for each line in my input data gives me the answer 154208, which turned out to be correct!

For part 2, an interesting twist is introduced to the puzzle. Suddenly, instead of just three robots, there are now far more robots within the chain controlling each other than before. In total, there is still one robot with a numerical keyboard, 25 robots with directional keyboards and finally one human.
The situation now looks like this with 2 robots in between:

                        
                +---+---+---+
                | 7 | 8 | 9 |       
                +---+---+---+           +---+---+                   +---+---+           +---+---+
                | 4 | 5 | 6 |           | ^ | A |                   | ^ | A |           | ^ | A |
                +---+---+---+       +---+---+---+       ...     +---+---+---+       +---+---+---+
                | 1 | 2 | 3 |       | < | v | > |               | < | v | > |       | < | v | > |
                +---+---+---+       +---+---+---+               +---+---+---+       +---+---+---+
                    | 0 | A |                   
                    +---+---+
    
                   robot 1             robot 2                     robot 26              human
                        
                    

If you were brave enough to code a brute force non recursive solution for part 1 (I salute you, since this was my initial approach as well), you most certainly have to change this approach for part 2. Since I aready developed a recursive solution for the first part, part 2 can easily be solved by calling the recursive function with the value c_max = 26.

Below, the code to iterate over my input data can be seen. I am calling the find_combo for part 1 with c_max=3 and for part 2 with c_max=26.

res2 = 0
res1 = 0
for l in lines:
    num = int(re.search("[0-9]+", l).group())
    test = list("A" + l)
    combos = list(zip(test,test[1:]))
    res2 += num*sum(find_combo(c,1,26) for c in combos)
    res1 += num*sum(find_combo(c,1,3) for c in combos)
    print(res1, res2)

Verifying my solution 188000493837892 for part 2 made me very happy!
Unfortunately, there was no time to celebrate since it was already late at night and next day's problem would go online only a few hours later...