Advent of Code 2024 - Day 21, in Kotlin - Keypad Conundrum • Todd Ginsberg

Wooooo that was confusing. I read the puzzle description a few times and it just did not click with me this time. Most times it does, but I really had a hard time visualizing what was happening. Now that I’ve solved it, it is clear, but this morning it sure wasn’t! I had some help from the /r/AdventOfCode Reddit to help understand what was being asked.

Once I understood the point of the puzzle, I came up with a solution that worked, thankfully! Recursion and memoization to the rescue!

If you’d rather just view the code, my GitHub Repository is here.

Puzzle Input

We will take our input as a List<String> we’ll call codes because they represent the codes we’re trying to punch into the keypads.

We will also define two keypad Maps. The key to the map is a Point2D and the value is the Char that is at that spot. I’ve laid these out below like the example so we can more clearly see where the gaps are. We’ll call these numericPad and directionalPad.

class Day21(private val codes: List<String>) {

    private val numericPad: Map<Point2D, Char> = mapOf(
        Point2D(0,0) to '7', Point2D(1,0) to '8', Point2D(2,0) to '9',
        Point2D(0,1) to '4', Point2D(1,1) to '5', Point2D(2,1) to '6',
        Point2D(0,2) to '1', Point2D(1,2) to '2', Point2D(2,2) to '3',
                             Point2D(1,3) to '0', Point2D(2,3) to 'A'
    )

    private val directionalPad: Map<Point2D, Char> = mapOf(
                             Point2D(1,0) to '^', Point2D(2,0) to 'A',
        Point2D(0,1) to '<', Point2D(1,1) to 'v', Point2D(2,1) to '>'
    )

}

Strategy and Shared Code

First, we need to know all of the shortest paths from every source to every destination on each keypad. Meaning, if there are 2 paths from Point-A to Point-B and they’re tied for shortest, we want to see them both. To do this, we’ll define an allPoints extension on the Map<Point, Char> that returns a Map<Pair<Point2D, Point2D>, List<String>> where the key is a from/to pair and the List<String> are all the paths expressed with characters (so, “»»A” means “move four spaces east and press the button”).

We will define these path structures as numericPaths and directionalPaths. I suppose if I had made the Point2D objects in directionalPad not overlap with those in numericPad, we could have a single map for all of the paths, but we don’t.

// In Day21

private val numericPaths: Map<Pair<Char, Char>, List<String>> = numericPad.allPaths()

private val directionalPaths: Map<Pair<Char, Char>, List<String>> = directionalPad.allPaths()

The to create the paths, we define an extension function that pairs up all of the keys in the map with every other key in the map, and then calls findLowestCostPaths on the pair. We associate all of this together into a map.

// In Day21

private fun Map<Point2D, Char>.allPaths(): Map<Pair<Char, Char>, List<String>> =
    keys.allPairs()
        .associate {
            (getValue(it.first) to getValue(it.second)) to findLowestCostPaths(it.first, it.second)
        }

Our allPairs function does a flatMap/map to get all pairs, including pairs that reference themselves. This is critical for later!

// In Day21

private fun <T> Collection<T>.allPairs(): List<Pair<T, T>> =
    flatMap { left ->
        map { right -> left to right }
    }

The findLowestCostPaths function should look similar to the one we wrote the other day on Day 16 to find all of the lowest cost paths through the maze. This code is mostly a copy and paste of that with the turning and costing functions removed.

Basically, we traverse from start to end and when we’ve found the end, we record the entire path. We make sure we’ve captured all of the lowest cost paths from start to end and then we convert the from a List<Point2D> to a String. This conversion done via zipWithNext to pair all of the Point2D object up, and then mapping with diffToChar to take two Point2D objects and determine which Char represents that transition.

It is important to note that each of these transitions must end with an A for the button press. I neglected to put this on when I first wrote this and spent a little while trying to figure out why something that seemed right didn’t work.

// In Day21

private fun Map<Point2D, Char>.findLowestCostPaths(start: Point2D, end: Point2D): List<String> {
    val queue = PriorityQueue<Pair<List<Point2D>, Int>>(compareBy { it.second })
        .apply { add(listOf(start) to 0) }
    val seen = mutableMapOf<Point2D, Int>()
    var costAtGoal: Int? = null
    val allPaths: MutableList<String> = mutableListOf()

    while (queue.isNotEmpty()) {
        val (path, cost) = queue.poll()
        val location = path.last()

        if (costAtGoal != null && cost > costAtGoal) {
            return allPaths
        } else if (path.last() == end) {
            costAtGoal = cost
            allPaths.add(path.zipWithNext().map { (from, to) -> from.diffToChar(to) }.joinToString("") + "A")
        } else if (seen.getOrDefault(location, Int.MAX_VALUE) >= cost) {
            seen[location] = cost
            location
                .cardinalNeighbors()
                .filter { it in keys }
                .forEach { queue.add(path + it to cost + 1) }
        }
    }
    return allPaths
}

The diffToChar function only works on cardinal directions as we don’t allow a diagonal traversal of the keypads.

// In Day21

private fun Point2D.diffToChar(other: Point2D): Char =
    when (val result = other - this) {
        Point2D.NORTH -> '^'
        Point2D.EAST -> '>'
        Point2D.SOUTH -> 'v'
        Point2D.WEST -> '<'
        else -> throw IllegalArgumentException("Invalid direction $result")
    }

Alright, finally! Now that we know all of the best paths between any two points on each of the keypads, we have what we need to write our findCost function, which will implement the core logic of this solution.

Let’s suppose the number we’re trying to find is 12. The path between them would be >. Given a >, we need to look on the directionalPaths keypad to find out how to make that transition, and so on. Our findCost function will take a code to look for, the depth in the call chain we are (which counts down), a transitions map which defaults to the numericPaths, and a cache which will store intermediate results (which defaults to an empty map).

We will key our cache by the code and its depth in the call tree. If we have seen the code and depth, we return it directly from the cache (this will save us mountains of time).

In the event we don’t find what we need in the cache, we’ll have to calculate it. The way we do this is to get the sumOf all of the minimum paths between all of the points in the code. So if our code is “012”, we’ll find the smallest cost of 0 to 1, and then the smallest cost of 1 to 2. Oh, and the same note with “A” applies here, every sequence starts and ends with “A”, so we manually add it to the code here.

If we’re not at the lowest depth, we need to recursively call ourselves with the path given as a new code, and a depth one level down the chain. Since we only need the numericPaths the first time we call findCost, we always pass idrectionalPath, and we always pass the cache.

// In Day21

private fun findCost(
    code: String,
    depth: Int,
    transitions: Map<Pair<Char, Char>, List<String>> = numericPaths,
    cache: MutableMap<Pair<String, Int>, Long> = mutableMapOf()
): Long =
    cache.getOrPut(code to depth) {
        "A$code".zipWithNext().sumOf { transition ->
            val paths: List<String> = transitions.getValue(transition)
            if (depth == 0) {
                paths.minOf { it.length }.toLong()
            } else {
                paths.minOf { path -> findCost(path, depth - 1, directionalPaths, cache) }
            }
        }
    }

All that’s left is to write a solve function which gets the sumOf all of the scores of each code. We have to multiply the result from findCost and the number part of the code, which we can get by dropping the last element (which, by necessity, is always an “A”, the only non-number in the code). These numbers also get huge for Part 2, so we’ll make them Long.

// In Day21

private fun solve(depth: Int): Long =
    codes.sumOf { findCost(it, depth) * it.dropLast(1).toLong() }

OK, now we have everything we need to solve both parts of the puzzle.

⭐ Day 21, Part 1

The puzzle text can be found here.

We can now solve part 1 by setting the depth on our solve function to 2.

// In Day21

fun solvePart1(): Long =
    solve(2)

Star earned! Onward!

⭐ Day 21, Part 2

The puzzle text can be found here.

We can solve part 2 by increasing the depth to 25. Thanks to our memoizing cache, we don’t have to make any change or worry about runtime.

// In Day21

fun solvePart2(): Long =
    solve(25)

Star earned! See you tomorrow!

Puzzle Input

Strategy and Shared Code

⭐ Day 21, Part 1

⭐ Day 21, Part 2

Further Reading