Advent of Code 2024 – Part 2 (Day 21)

As previously mentioned I finished 2024’s Advent of Code. But I wasn’t sure that I really understood the solution to Day 21, so the purpose of this post is explain it to myself!

Fair warning: This is a long and technical post!

Day 21

Day 21 was a beautiful problem, but an absolute stinker in terms of brain strain. The description below is all lifted off the problem page on AoC, minus the prose.

The problem

There is a numeric keypad

+---+---+---+
| 7 | 8 | 9 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
    | 0 | A |
    +---+---+

Which needs a provided code – say 029A – to be entered.

This keypad is operated by a remote control robot (Robot 1), which is controlled by a directional keypad. The direction keys move the robot’s arm, and A makes it press whatever button it’s over.

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

The robot starts on A, so one way of getting the robot to enter the code 029A would be to press

• < to move the arm from A (its initial position) to 0.
• A to push the 0 button.
• ^A to move the arm to the 2 button and push it.
• >^^A to move the arm to the 9 button and push it.
• vvvA to move the arm to the A button and push it.

Obviously there are an infinite number of sequences that could be entered on the remote control keypad, so this puzzle is just concerned with the shortest sequences (i.e. fewest number of key presses).

There are 3 shortest sequences of keypresses for 029A:

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

BUT Robot 1’s remote control is operated by a second robot (Robot 2), which has its own independent directional control pad. So in order to get the Robot 2 to enter <A^A>^^AvvvA (so that Robot 1 enters 029A) you need to enter a sequence on its keypad such as v<<A>>^A<A>AvA<^AA>A<vAAA>^A.

• Move Robot 1 0 and press [029A]
  • Move Robot 2 to < and press [<A^A>^^AvvvA]
    • You press v<<A
  • Move Robot 2 from 2 to A and press [<A^A>^^AvvvA]
    • You press >>^A
• Move Robot 1 from 0 to 2 and press
  • etc…

BUT Robot 2’s directional control pad is operated by a third robot (Robot 3), which again has a remote controlled direction pad.

SO

1. Robot 1 has to enter 029A on the door keypad
2. Robot 2 has to enter (say) <A^A>^^AvvvA on Robot 1’s remote control pad to make Robot 1 enter 029A
3. Robot 3 has to enter (say) v<<A>>^A<A>AvA<^AA>A<vAAA>^A on Robot 2’s remote control pad to make Robot 2 enter <A^A>^^AvvvA on Robot 1’s control pad, which make Robot 1 enter the code on the door keypad
4. I, operating Robot’s 3 remote control, need to press (say)
   <vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A to make Robot 3 enter v<<A>>^A<A>AvA<^AA>A<vAAA>^A on Robot 2’s remote control pad, which make Robot 2 enter <A^A>^^AvvvA on Robot 1’s control pad, which will make Robot 1 press 029A

It was at this point my brain ran out of steam. Actually it kind of ran out at Robot 2.

For Part 1 of the problem this was the setup, and you had to determine the smallest number of keypresses needed on Robot 3’s remote control pad to get Robot 1 to enter the code.

Solving part 1

The first gotcha is that once you get more than a couple of robots, the keypress order matters.

So, if I need to go left 1 and up 2 there are 3 equal length ways to do it:

• <^^
• ^<^
• ^^<

BUT, if I add extra robots, suddenly ^<^ becomes much a much longer sequence than <^^.

• <^^ = Move finger to left, activate, move finger up, activate, activate
• ^<^ = Move finger to up, activate, move finger left, activate, move finger to up, activate

There is a whole extra sequence of keypresses in the second. It turns out to be even more subtle than this, and analytically beyond my brain – but that’s ok because we can just try them all out and choose the shortest – fine for part 1.

So my solution for this part was essentially brute force.

Treating each digit of the door code independently (which it is):

1. Calculate all the (sensible) sequences which can be entered on the Robot 1’s control pad to move it from the current and next digit in the code (e.g. A to 0), and keep only the shortest. So in the first case that’s just <.
2. Calculate all the (sensible) sequences which can be entered on the Robot 2’s control pad to make it enter each sequence identified in step (1), with a A at the end of each, and again keep only the shortest. For instance v<<A>>^A
3. Calculate all the (sensible) sequences which can be entered on Robot 3’s control pad to make it enter each of sequences in Step (2). Again keep only the shortest.

Calculating the sequences is pretty straightforward – for any pair of keys, we either move up or down zero or more times, and either left or right zero or more times. But we never need to move up and down, or left and right within one sequence. So it’s just a case of recursing the options, at each step adding “having moved up/down” and “having moved left/right” as two possible sub-sequences.

It all hangs on the fact it is essentially a recursive problem – working out the sequence to enter <A^A>^^AvvvA is no different to the calculation for <vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A

So my main solving code ended up as

public static List CalculateSequences(char[][] keypad, string sequence)
{
  List options = [""];
  for (int i = 0; i < sequence.Length; i++)
  {
    List newOptions = [];
    // Navigate returns all the ways of getting from 'n1' to 'n2'
    var currentKey = i == 0 ? 'A' : sequence[i - 1];
    var nextKey = sequence[i];
    foreach (var option in Navigate(keypad, currentKey, nextKey ))
    {
      newOptions.AddRange(options.Select(o => o + option));
    }
    options = newOptions;
  }

  return options;
}

public static string CalculateShortestSequence(string sequence)
{
  StringBuilder shortest = new StringBuilder();
  // Do one key at a time.
  for (int i = 0; i < sequence.Length; i++)
  {
    var currentKey = i == 0 ? 'A' : sequence[i - 1];
    var nextKey = sequence[i];
    // Calculate the potential key presses for R1's control to
    // move from current to next
    var keypadOptions = Navigate(NumericKeyPad, currentKey, nextKey);

    // Calculate the presses on R2's control for each
    // of the R1 potential sequences
    var kp2Options = keypadOptions
           .SelectMany(seq => CalculateSequences(DirectionKeyPad, seq));
    kp2Options = kp2Options
           .Where(seq => seq.Length <= kp2Options.Min(seq => seq.Length))
           .ToList();

    // Calculate the presses on R3's control for each of
    // R2 potential sequences.
    var kp3Options = kp2Options
         .SelectMany(seq => CalculateSequences(DirectionKeyPad, seq));
    kp3Options = kp3Options
         .Where(seq => seq.Length <= kp3Options.Min(seq => seq.Length))
         .ToList();

    // Take shortest of these R3 sequences as our candidate.
    shortest.Append(kp3Options.OrderBy(seq => seq.Length).First());
  }

  return shortest.ToString();
}

Even with just only 3 robots, I was running into runtime issues with the number of sequences calculated, hence having to discard all the non-shortest sequences at each level of recursion.

Part 2

As usual Part 2 upped the ante considerably, in this case having 25 interim robots instead of just 2!!

Clearly the approach for part 1 was never going to work.

My solution (with help from Reddit) hinges on 4 critical observations:

1. You don’t need to know the actual sequences to solve the puzzle, just the length of the shortest sequence
2. Each digit press is independent. That is to say, it doesn’t matter what keypresses have gone before – the only relevant factors are the start position and end position.
3. When a key is pressed on a certain keypad, every robot on every keypad ‘above’ it in the chain must be on A. This means there is a sort of “reset” up the chain on every button press.
4. The shortest sequence between any 2 pairs of keys therefore only needs to be calculated once for each level of the chain, and can thereafter be re-used (memoized/cached).

The final point here is critical. Once you’ve worked out the cost of moving Robot 2 from (say) A to < and pressing it, the lowest cost sequence for this move for this robot will be the same every time!. This isn’t very interesting for Robot 2, but for robot 3 we move from A to < 3 times – and only need to calculate it once. It also turns out there is a pretty small set of key pairs for any given robot – just 20, so even with 25 robots we only need to calculate and store a maximum of 500 entries. But we can also calculate them “on demand” – hence the memoization.

And in case it isn’t already clear, this is a recursive problem:

• I need Robot 1 to enter 029A
  • So I first need to move Robot 1 from A to 0 and press it.
    • Ah, so I need Robot 2 to enter <A
      • So I first need move Robot 2 from A to < and press it
        • Ah, so I need Robot 3 to enter v<<A
          • So I need to move Robot 3 from A to v and press it
            • Ah, so I need Robot 4 to enter v<
            • …
            • …
          • Finally, move Robot 3 from < to A and press it
      • Now Robot 2 needs to move from < to A and press it
        • …
  • Yay – we entered 0 – next step move Robot 1 from 0 to 2 and press it.

Remember, when Robot 1 presses a digit, all the other robots will be on A

Our recursion therefore works by asking the question “How many key presses are required to cause ‘me’ to press a key (given I’m starting on a key) if there are n robots above me?”:

• The sequence required is <
  • How many key presses are required to achieve A⇒<♦, with 25 robots above?
    • The sequence on my control pad is v<<A^*
      • So how many keypresses are required to achieve A⇒v♦ with 24 robots above?
      • And how many keypresses are required to achieve v⇒<♦ with 24 robots above?
      • And how many keypresses are required to achieve <⇒<♦ with 24 robots above?
      • And how many keypresses are required to achieve <⇒A♦ with 24 robots above?
    • Add these up, and that’s the cost

^* For simplicity we’re ignoring the fact multiple sequences exist – in the real thing we have to test them all.

The base case of the recursion is the human at the top – the final robot will always have a count of 1 (as the button is directly pressed).

So far so Part 1 – but now the magic kicks in.

I worked out the cost of [A⇒v♦ with 24 robots], and I can store that, so next time I’m asked [A⇒v♦ with 24 robots] I can return the cost without having to traverse the whole chain again. This is not desperately useful for a Robot so near the bottom, which may only be asked this question once – but higher up the tree the twenty questions like:

• [A⇒v♦ with 5 robots]
• [A⇒^♦ with 5 robots]
• [A⇒<♦ with 5 robots]
• [A⇒>♦ with 5 robots]
• [v⇒A♦ with 5 robots]
• …

Are going to be asked a lot. And once calculated the result is, in effect, instant.

So – the resulting recursion code is about 20 lines long, I’ve tweaked a little to try and remove some obscurity. The Navigate is the same as for Part 1 – it returns every sensible sequence for navigating from key 1 to 2 on the specified pad.

private long Cost(char a, char b, int robots)
{
  // Check the cache
  if (cache.TryGetValue((a, b, robots), out long inCache))
  {
    return inCache;
  }

  var lowestCost = long.MaxValue;
  
  // Determine All ways of moving from a to b
  var options = Navigate(DirectionKeyPad, a, b);
  foreach (var option in options)
  {
    long cost = 0;
    if (robots == 1)
      cost = option.Length; // just the direct button presses, and an 'A'
    else
    {
      for (int i = 0; i < option.Length; i++)
      {
        char nextA = i == 0 ? 'A' : option[i - 1];
        char nextB = option[i];
          cost += Cost(nextA, nextB, robots - 1);
      }
    }
    if (cost < lowestCost)
      lowestCost = cost;
  }
  cache[a, b, robots)] = lowestCost;
  return lowestCost;
}

It just needs an extra function on top to calculate all possible sequences for Robot 1, and kick off the recursion with robotCount = 25. There's also a bit of guff to read the puzzle input and generate the output in the format required.

You can look at the Full listing on GitHub - SolveB is the entry point.