As you teleport onto Santa's Reindeer-class starship, The Historians begin to panic: someone from their search party is missing. A quick life-form scan by the ship's computer reveals that when the missing Historian teleported, he arrived in another part of the ship.

The door to that area is locked, but the computer can't open it; it can only be opened by physically typing the door codes (your puzzle input) on the numeric keypad on the door.

Visit the website for the full story and full puzzle description.

This is the problem that sets casual players apart competitors. I had a hard time solving it. I think I was on track, but I just couldn't visualize the whole idea of robots controlling robots controlling robots. I love recursion, but just cannot mentally follow multiple layers of indirection. Anyway. I could solve it in the evening hours, so I'm still on track with Advent of Code 2024.

It was clear from the exponential growth demonstrated by part 1 that I wont be able to generate the final string to be entered. Luckily the problem asked only for the length of it. (Which makes it really artifical: how would the elves enter such a long key?)

I created a function called EncodeKeys which takes a sequence of keys to be pressed and an array of keypads, and returns the length of the shortest sequence needed to enter the given keys. An empty keypad array means that the sequence is simply entered by a human and no further encoding is needed. Otherwise, the sequence is entered by a robot that needs to be programmed using its keypad. In this case the keys are encoded using the first keypad in the array (the robot's keypad), character by character using EncodeKey which will recursively call back to EncodeKeys with the rest of the keypads.

The _EncodeKey_ helper function is used to move the robot from position A to position B on the keypad and press the button. Usually, A and B are not in the same row and column, so the movement has both a horizontal and a vertical part. We could go both ways: horizontal first then vertical, or the other way around, and we need to check which movement results in fewer key presses. Lastly, we should not forget that the robot's hand should never move over the empty space ' '.

Since every key sequence we need to enter ends with a button press 'A', we can always be sure that the robot will stay over the 'A' button at the end. Since it initially starts over the 'A' key as well, we have an invariant: at the beginning and the end of EncodeKeys, the robot is over the 'A' key. It can move around while entering the keys, but the invariant holds when it finishes.

This is great because we don't have to keep track of it! The Cache used by EncodeKey doesn't need to care about the robot's position recursively. All it depends on is the current robot's position, the position of the next key to be entered, and the number of keypads left in the recursion. This reduces the problem space quite a bit and gives us a well-performing algorithm.

namespace AdventOfCode.Y2024.Day21;

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

using Cache = System.Collections.Concurrent.ConcurrentDictionary<(char currentKey, char nextKey, int depth), long>;
using Keypad = System.Collections.Generic.Dictionary<Vec2, char>;
record struct Vec2(int x, int y);

[ProblemName("Keypad Conundrum")]
class Solution : Solver {

    public object PartOne(string input) => Solve(input, 2);

    public object PartTwo(string input) => Solve(input, 25);
    
    long Solve(string input, int depth) {
        var keypad1 = ParseKeypad("789\n456\n123\n 0A");
        var keypad2 = ParseKeypad(" ^A\n<v>");
        var keypads = Enumerable.Repeat(keypad2, depth).Prepend(keypad1).ToArray();

        var cache = new Cache();
        var res = 0L;

        foreach (var line in input.Split("\n")) {
            var num = int.Parse(line[..^1]);
            res += num * EncodeKeys(line, keypads, cache);
        }
        return res;
    }

    // Determines the length of the shortest sequence that is needed to enter the given 
    // keys. An empty keypad array means that the sequence is simply entered by a human 
    // and no further encoding is needed. Otherwise the sequence is entered by a robot
    // which needs to be programmed. In practice this means that the keys are encoded 
    // using the robots keypad (the first keypad), generating an other sequence of keys.
    // This other sequence is then recursively encoded using the rest of the keypads.
    long EncodeKeys(string keys, Keypad[] keypads, Cache cache) {
        if (keypads.Length == 0) {
            return keys.Length;
        } else {
            // invariant: the robot starts and finishes by pointing at the 'A' key
            var currentKey = 'A';
            var length = 0L;

            foreach (var nextKey in keys) {
                length += EncodeKey(currentKey, nextKey, keypads, cache);
                // while the sequence is entered the current key changes accordingly
                currentKey = nextKey;
            }

            // at the end the current key should be reset to 'A'
            Debug.Assert(currentKey == 'A', "The robot should point at the 'A' key");
            return length;
        }
    }
    long EncodeKey(char currentKey, char nextKey, Keypad[] keypads, Cache cache) =>
       cache.GetOrAdd((currentKey, nextKey, keypads.Length), _ => {
           var keypad = keypads[0];

           var currentPos = keypad.Single(kvp => kvp.Value == currentKey).Key;
           var nextPos = keypad.Single(kvp => kvp.Value == nextKey).Key;

           var dy = nextPos.y - currentPos.y;
           var vert = new string(dy < 0 ? 'v' : '^', Math.Abs(dy));

           var dx = nextPos.x - currentPos.x;
           var horiz = new string(dx < 0 ? '<' : '>', Math.Abs(dx));

           var cost = long.MaxValue;
           // we can usually go vertical first then horizontal or vica versa,
           // but we should check for the extra condition and don't position
           // the robot over the ' ' key:
           if (keypad[new Vec2(currentPos.x, nextPos.y)] != ' ') {
               cost = Math.Min(cost, EncodeKeys($"{vert}{horiz}A", keypads[1..], cache));
           }

           if (keypad[new Vec2(nextPos.x, currentPos.y)] != ' ') {
               cost = Math.Min(cost, EncodeKeys($"{horiz}{vert}A", keypads[1..], cache));
           }
           return cost;
       });

    Keypad ParseKeypad(string keypad) {
        var lines = keypad.Split("\n");
        return (
            from y in Enumerable.Range(0, lines.Length)
            from x in Enumerable.Range(0, lines[0].Length)
            select new KeyValuePair<Vec2, char>(new Vec2(x, -y), lines[y][x])
        ).ToDictionary();
    }
}

Please ☆ my repo if you like it!