Advent of Code 2019 - Day 18, in Kotlin • Todd Ginsberg

A maze traversal with a twist! I had a lot of fun trying to figure this one out. Truth be told, I was traveling on the day this puzzle came out and it took me a while to get back to it - it’s the final one I finished for Advent of Code 2019.

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

Problem Input

We’re going to take in the maze as a List<String> and convert it into a class called Maze. This class will hold everything we need to describe the map and explore it. This is not a data class because we don’t need the extras they come with. We’ll assign this new Maze to a private value in our Day18 class.

class Day18(input: List<String>) {

    private val maze = Maze.from(input)

    class Maze(
        private val starts: Set<Point2D>, 
        private val keys: Map<Point2D, Char>, 
        private val doors: Map<Point2D, Char>, 
        private val openSpaces: Set<Point2D>) {

        companion object {
            fun from(input: List<String>): Maze {
                val starts = mutableSetOf<Point2D>()
                val keys = mutableMapOf<Point2D, Char>()
                val doors = mutableMapOf<Point2D, Char>()
                val openSpaces = mutableSetOf<Point2D>()

                input.forEachIndexed { y, row ->
                    row.forEachIndexed { x, c ->
                        val place = Point2D(x, y)
                        if (c == '@') starts += place
                        if (c != '#') openSpaces += place
                        if (c in ('a'..'z')) keys[place] = c
                        if (c in ('A'..'Z')) doors[place] = c
                    }
                }
                return Maze(starts, keys, doors, openSpaces)
            }
        }
    }
}

We’ll do the main work in the from method in the companion object on Maze. This function loops through each spot in the input and identifies what it is. Anything that is not a # (a wall) is considered open space because we can move to it. We also record the keys and doors. All of this is stored in a class called Maze.

⭐ Day 18, Part 1

The puzzle text can be found here.

Because I know things that you might not about Part 2, we’re going to make what looks like an odd choice for Part 1. We’re going to write an algorithm that accounts for an arbitrary number of starting points. The reasoning for this will become clear when we get to Part 2. All of our work will be in the Maze class.

We need three functions to do this, so lets break it down into some small conceptually manageable steps.

First, we’re going to need our top level function. This is called minimumSteps and is ultimately responsible for calculating our answer by taking our starting points and figuring out what keys we can collect from that point.

// In Day18.Maze

fun minimumSteps(from: Set<Point2D> = starts,
                 haveKeys: Set<Char> = mutableSetOf(),
                 seen: MutableMap<Pair<Set<Point2D>, Set<Char>>, Int> = mutableMapOf()): Int {
    val state = Pair(from, haveKeys)

    if (state in seen) return seen.getValue(state)

    val answer = findReachableFromPoints(from, haveKeys).map { entry ->
        val (at, dist, cause) = entry.value
        dist + minimumSteps((from - cause) + at, haveKeys + entry.key, seen)
    }.min() ?: 0
    seen[state] = answer
    return answer
}

Once we have some keys and a new point, we can try again and again, finding the path with the fewest number of steps. It is important to cache as much as possible here, so we’ve got a rather odd looking data structure: seen is a MutableMap<Pair<Set<Point2D>, Set<Char>>, Int>. You can feel free to encapsulate that into another class, if you’d like. Essentially, the key to the map is a Pair of all the points we’ve crosses and the keys we’ve collected. The value in the map is the number if steps it took to do that. The findReachableFromPoints we offload the path finding to will return us some tuples - a point (at), its distance (dist), and the original starting point we used to get there (cause). We need this because the recursive call to minimumSteps needs to substitute that point for the best answer findReachableFromPoints could come up with for that original starting position.

Since this function depends on another one called findReachableFromPoints, we’ll write that next:

// In Day18.Maze

private fun findReachableFromPoints(
    from: Set<Point2D>, 
    haveKeys: Set<Char>
): Map<Char, Triple<Point2D, Int, Point2D>> =
    from.map { point ->
        findReachableKeys(point, haveKeys).map { entry ->
            entry.key to Triple(entry.value.first, entry.value.second, point)
        }
    }.flatten().toMap()

IF we only dealt with one starting point, we wouldn’t need this function. It’s job is to take all our starting points and call another function that does a Depth First Traversal, trying to find more keys. Ultimately, it returns a Map where the key is a maze key and the value is the tuple we described above (a point, its distance, and the cause (starting point)).

The real work is done in findReachable:

// In Day18.Maze

private fun findReachableKeys(
    from: Point2D, 
    haveKeys: Set<Char> = mutableSetOf()
): Map<Char, Pair<Point2D, Int>> {
    val queue = ArrayDeque<Point2D>().apply { add(from) }
    val distance = mutableMapOf(from to 0)
    val keyDistance = mutableMapOf<Char, Pair<Point2D, Int>>()

    while (queue.isNotEmpty()) {
        val next = queue.pop()
        next.neighbors()
            .filter { it in openSpaces }
            .filterNot { it in distance }
            .forEach { point ->
                distance[point] = distance[next]!! + 1
                val door = doors[point]
                val key = keys[point]
                if (door == null || door.toLowerCase() in haveKeys) {
                    if (key != null && key !in haveKeys) {
                        keyDistance[key] = Pair(point, distance[point]!!)
                    } else {
                        queue.add(point)
                    }
                }
            }
    }
    return keyDistance
}

This function should look familiar - we’ve use a Depth First Traversal a few times this year. We set up a queue to order our work in increasingly deep steps. We also keep a distance map for any given point from the starting point, and map of keys to their location and how many steps they took to get there. So long as our work queue isn’t empty, we’ll get all the neighbors of the spot at the head of the queue. We’ll filter out spots that aren’t open (walls), and spots that we’ve already examined (because we’re caching things in the distance map). Otherwise, we need to do some work.

Congratulations, the neighboring spot we are looking at is something we can move to, and something we haven’t seen yet. Record its distance as one plus the distance it took to get to the spot that we came from. Next, if we’re standing at a door and we do not have the key, we’re done. This path is fruitless. Otherwise, if we are standing on a key and don’t already have it, collect it by adding a record into keyDistance. Otherwise, we can add the point we’re looking at now to the queue.

When that function ends, we’ll know a bunch of keys and how many steps it took to get to them.

Calling our original function solves Part 1!

fun solve(): Int =
    maze.minimumSteps()

Star earned!

⭐ Day 18, Part 2

The puzzle text can be found here.

See? Now you know why we wrote Part 1 to take in multiple starting positions. I solved Part 2 by manually making alterations to my Part 1 input. Of course, you could write a simple function to find the single starting point, add in the walls, and create the new starting points.

Star earned!

⭐ Day 18, Part 1

⭐ Day 18, Part 2

Further Reading