Advent of Code 2018 - Day 22, in Kotlin • Todd Ginsberg

Today is another grid problem, but there’s an interesting twist in part 2 (there’s always a twist in part 2!).

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

Problem Input

The input file is two lines, with simple integers and a regular format so we’ll parse them directly:

class Day22(rawInput: List<String>) {

    private val depth: Int = rawInput.first().substring(7).toInt()
    private val target: Point = Point.of(rawInput.drop(1).first().substring(8))

}

⭐ Day 22, Part 1

The puzzle text can be found here.

“Before you go in”… Me?! I’m the last person you want rescuing your dear friend in the caves. Trust me. Well, if we must…

The approach I took for this is to not define our cave as an Array<CharArray> like we’ve been doing, because it has to grow as we explore it in part 2. So we’ll define our erosion levels as a Map<Point, Int> where our good friend Point is some location in the cave, and the Int value is the erosion level. Let me warn you, there are faster ways to do this, for instance by using a List<List<Int>> instead. This approach makes part 2 about 3x slower, but I feel it is clear, and if you want faster you can always experiment with that once you get this working.

Terrain

Let’s write an enum for our terrain.

// In Day22
private enum class Terrain(val symbol: Char, val modVal: Int) {
    Rocky('.', 0),
    Wet('|', 1),
    Narrow('=', 2);

    companion object {
        val values = arrayOf(Rocky, Wet, Narrow)
        fun byErosionLevel(level: Int): Terrain =
            values.first { it.modVal == level % 3 }
    }

}

We don’t strictly need symbol on there, you can leave it off if you don’t plan on printing out the map in the end (I did for debugging, so I left it in)

Lazy Grid

We can now go and define our caves and some extension functions on Point which are scoped to our grid code, so we don’t share them with every other project we have in this package.

// In Day22

private class LazyGrid(val target: Point, val depth: Int) {
    private val erosionLevels = mutableMapOf<Point, Int>()

    fun riskLevel(at: Point = target): Int =
        (0..at.y).flatMap { y ->
            (0..at.x).map { x ->
                Point(x, y).erosionLevel() % 3
            }
        }.sum()

    private fun Point.erosionLevel(): Int {
        if (this !in erosionLevels) {
            val geo = when {
                this in erosionLevels -> erosionLevels.getValue(this)
                this in setOf(Point.origin, target) -> 0
                y == 0 -> x * 16807
                x == 0 -> y * 48271
                else -> left.erosionLevel() * up.erosionLevel()
            }
            erosionLevels[this] = (geo + depth) % 20183
        }
        return erosionLevels.getValue(this)
    }

}

Let’s go through it. To calculate the risk level, we need to go through each spot and figure out its erosion level and get its value modulo 3. That logic is one we’ve seen before - flatmap of map, and sum. Kotlin makes that nice and easy and concise.

Calculating the erosion level of a Point needs more explanation. We’ll make this an extension on Point and scope it to our LazyGrid class so we don’t have it elsewhere in our code for Advent of Code. Since we’re doing this lazily, the first thing we do is to check if we have this cached already, otherwise we calculate it. This is going to be a recursive call because if we aren’t on the 0 axis or at the start or target, we need to look left and up. So that will recursively call itself to get the answer.

Calling this gives us the answer to part 1:

fun solvePart1(): Int =
    cave.riskLevel()

Star earned! Onward!

⭐ Day 22, Part 2

The puzzle text can be found here.

I suppose we’re going to ignore the fact that even if we do get to the target before he dies, we didn’t seem to bring along a second set of gear for him to use. Nor do we account for the fact that we have to go back to the start (presumably).

Anyway, this is a lot like Day 15 except we have a variable cost instead of just 1 more cost per movement. And instead of keeping track of where we’ve been, we need to keep track of where we’ve been with each tool, and how much it cost to get there. For instance, we’ll treat being in spot 2,3 with the torch as a different state than being in spot 2,3 with the climbing gear. That way, if we can improve the cost with the same tool, we will prefer that over other paths.

More enums!

Let’s add an enum for each of our tools and then modify Terrain to figure out which tools we’re allowed to have there:

// In Day22

private enum class Tool {
    Torch,
    Climbing,
    Neither
}

private enum class Terrain(val symbol: Char, val modVal: Int, val tools: Set<Tool>) {
    Rocky('.', 0, setOf(Tool.Climbing, Tool.Torch)),
    Wet('|', 1, setOf(Tool.Climbing, Tool.Neither)),
    Narrow('=', 2, setOf(Tool.Torch, Tool.Neither));

    companion object {
        val values = arrayOf(Rocky, Wet, Narrow)
        fun byErosionLevel(level: Int): Terrain =
            values.first { it.modVal == level % 3 }
    }

}

We will also define a way to get the set of tools we’re allowed to have on a given Point. This means we need to figure out the erosion level, so that’s another call to our recursive function there. We also have special handling for the origin (0,0) and target:

// In LazyGrid (in Day22)

private fun Point.validTools(): Set<Tool> =
    when (this) {
        Point.origin -> setOf(Tool.Torch)
        target -> setOf(Tool.Torch)
        else -> Terrain.byErosionLevel(erosionLevel()).tools
    }

Once we have this, we can talk about traversing the cave. Let’s define a new data class to represent a step in the path, along with what tool we’re holding and how expensive it was to get to that part of the graph:

// In Day22

private data class Traversal(val end: Point, val holding: Tool, val cost: Int = 0) : Comparable<Traversal> {

    override fun compareTo(other: Traversal): Int =
        this.cost.compareTo(other.cost)
}

We implement Comparable<Traversal> here because when we put these into a queue for searching, we’ll want the cheapest one first every time.

Searching the Caves

Now we can write our cave searching algorithm. Like I said, this is very similar to Day 15, but with the added twist that we have to switch tools from time to time. Let’s look at it and then go over it:

// In LazyGrid, in Day22

fun cheapestPath(to: Point = target): Traversal? {
    val seenMinimumCost: MutableMap<Pair<Point, Tool>, Int> = mutableMapOf(Point.origin to Tool.Torch to 0)
    val pathsToEvaluate = PriorityQueue<Traversal>().apply {
        add(Traversal(Point.origin, Tool.Torch))
    }

    while (pathsToEvaluate.isNotEmpty()) {
        val thisPath = pathsToEvaluate.poll()

        // Found it, and holding the correct tool
        if (thisPath.end == to && thisPath.holding == Tool.Torch) {
            return thisPath
        }

        // Candidates for our next set of decisions
        val nextSteps = mutableListOf<Traversal>()

        // Move to each neighbor, holding the same tool.
        thisPath.end.cardinalNeighbors(false).forEach { neighbor ->
            // Add a Traversal for each if we can go there without changing tools
            if (thisPath.holding in neighbor.validTools()) {
                // Can keep the tool.
                nextSteps += thisPath.copy(
                    end = neighbor,
                    cost = thisPath.cost + 1
                )
            }
        }

        // Stay where we are and switch tools to anything we aren't using (but can)
        thisPath.end.validTools().minus(thisPath.holding).forEach { tool ->
            nextSteps += Traversal(
                end = thisPath.end,
                holding = tool,
                cost = thisPath.cost + 7
            )
        }

        // Of all possible next steps, add the ones we haven't seen, or have seen and we can now do cheaper.
        nextSteps.forEach { step ->
            val key = Pair(step.end, step.holding)
            if (key !in seenMinimumCost || seenMinimumCost.getValue(key) > step.cost) {
                pathsToEvaluate += step
                seenMinimumCost[key] = step.cost
            }
        }
    }
    return null // No path!? Come on...
}

First, we have to record every point in the cave we’ve seen, holding a specific tool, and how expensive it was to get there (time-wise). So we’ll define a Map<Pair<Point, Tool>, Int> to record that. We will seed that with the fact that we start at the origin holding the torch and it cost us nothing to get there. Similar to the other graph traversals we’ve written, we will need a queue of work to do, which we will implement as a PriorityQueue, which will always sort the least expensive option to the front of the queue.

So long as we have something to work on, we’ll pop a candidate out of the queue. If that’s the one we’re looking for, and we’re holding the torch, we’re done! Otherwise we need to do some work. First, we will see which neighbors we can move to without switching tools. Second, we’ll switch tools in speculation that it will open up more options for us later. We take all of those options and add the ones we’ve never seen, or have seen but were more expensive to the queue.

And now we can solve our problem:

fun solvePart2(): Int =
    cave.cheapestPath()?.cost ?: throw IllegalStateException("No path?! Really?!")

Again, changing data structures from Map<Point, Int> to something like an array of arrays, or a list of lists will almost certainly be faster, but I didn’t want to complicate this explanation with code to grow the map. I highly encourage you to experiment with this though, there are probably some pretty quick implementations out there if you think about it!

Star Earned!

⭐ Day 22, Part 1

⭐ Day 22, Part 2

Further Reading