Skip to Content

Advent of Code 2018 - Day 22, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 22: 'Mode Maze'

Posted on

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

This is it, your final stop: the year -483. It’s snowing and dark outside; the only light you can see is coming from a small cottage in the distance. You make your way there and knock on the door.

A portly man with a large, white beard answers the door and invites you inside. For someone living near the North Pole in -483, he must not get many visitors, but he doesn’t act surprised to see you. Instead, he offers you some milk and cookies.

After talking for a while, he asks a favor of you. His friend hasn’t come back in a few hours, and he’s not sure where he is. Scanning the region briefly, you discover one life signal in a cave system nearby; his friend must have taken shelter there. The man asks if you can go there to retrieve his friend.

The cave is divided into square regions which are either dominantly rocky, narrow, or wet (called its type). Each region occupies exactly one coordinate in X,Y format where X and Y are integers and zero or greater. (Adjacent regions can be the same type.)

The scan (your puzzle input) is not very detailed: it only reveals the depth of the cave system and the coordinates of the target. However, it does not reveal the type of each region. The mouth of the cave is at 0,0.

The man explains that due to the unusual geology in the area, there is a method to determine any region’s type based on its erosion level. The erosion level of a region can be determined from its geologic index. The geologic index can be determined using the first rule that applies from the list below:

  • The region at 0,0 (the mouth of the cave) has a geologic index of 0.
  • The region at the coordinates of the target has a geologic index of 0.
  • If the region’s Y coordinate is 0, the geologic index is its X coordinate times 16807.
  • If the region’s X coordinate is 0, the geologic index is its Y coordinate times 48271.
  • Otherwise, the region’s geologic index is the result of multiplying the erosion levels of the regions at X-1,Y and X,Y-1.

A region’s erosion level is its geologic index plus the cave system’s depth, all modulo 20183. Then:

  • If the erosion level modulo 3 is 0, the region’s type is rocky.
  • If the erosion level modulo 3 is 1, the region’s type is wet.
  • If the erosion level modulo 3 is 2, the region’s type is narrow.

For example, suppose the cave system’s depth is 510 and the target’s coordinates are 10,10. Using % to represent the modulo operator, the cavern would look as follows:

  • At 0,0, the geologic index is 0. The erosion level is (0 + 510) % 20183 = 510. The type is 510 % 3 = 0, rocky.
  • At 1,0, because the Y coordinate is 0, the geologic index is 1 * 16807 = 16807. The erosion level is (16807 + 510) % 20183 = 17317. The type is 17317 % 3 = 1, wet.
  • At 0,1, because the X coordinate is 0, the geologic index is 1 * 48271 = 48271. The erosion level is (48271 + 510) % 20183 = 8415. The type is 8415 % 3 = 0, rocky.
  • At 1,1, neither coordinate is 0 and it is not the coordinate of the target, so the geologic index is the erosion level of 0,1 (8415) times the erosion level of 1,0 (17317), 8415 * 17317 = 145722555. The erosion level is (145722555 + 510) % 20183 = 1805. The type is 1805 % 3 = 2, narrow.
  • At 10,10, because they are the target’s coordinates, the geologic index is 0. The erosion level is (0 + 510) % 20183 = 510. The type is 510 % 3 = 0, rocky.

Drawing this same cave system with rocky as ., wet as =, narrow as |, the mouth as M, the target as T, with 0,0 in the top-left corner, X increasing to the right, and Y increasing downward, the top-left corner of the map looks like this:

M=.|=.|.|=.|=|=.
.|=|=|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..===..=|.|||.
.======|||=|=.|=
.===|=|===T===||
=|||...|==..|=.|
=.=|=.=..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

Before you go in, you should determine the risk level of the area. For the the rectangle that has a top-left corner of region 0,0 and a bottom-right corner of the region containing the target, add up the risk level of each individual region: 0 for rocky regions, 1 for wet regions, and 2 for narrow regions.

In the cave system above, because the mouth is at 0,0 and the target is at 10,10, adding up the risk level of all regions with an X coordinate from 0 to 10 and a Y coordinate from 0 to 10, this total is 114.

What is the total risk level for the smallest rectangle that includes 0,0 and the target’s coordinates?

“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

— Part Two — Okay, it’s time to go rescue the man’s friend.

As you leave, he hands you some tools: a torch and some climbing gear. You can’t equip both tools at once, but you can choose to use neither.

Tools can only be used in certain regions:

In rocky regions, you can use the climbing gear or the torch. You cannot use neither (you’ll likely slip and fall). In wet regions, you can use the climbing gear or neither tool. You cannot use the torch (if it gets wet, you won’t have a light source). In narrow regions, you can use the torch or neither tool. You cannot use the climbing gear (it’s too bulky to fit). You start at 0,0 (the mouth of the cave) with the torch equipped and must reach the target coordinates as quickly as possible. The regions with negative X or Y are solid rock and cannot be traversed. The fastest route might involve entering regions beyond the X or Y coordinate of the target.

You can move to an adjacent region (up, down, left, or right; never diagonally) if your currently equipped tool allows you to enter that region. Moving to an adjacent region takes one minute. (For example, if you have the torch equipped, you can move between rocky and narrow regions, but cannot enter wet regions.)

You can change your currently equipped tool or put both away if your new equipment would be valid for your current region. Switching to using the climbing gear, torch, or neither always takes seven minutes, regardless of which tools you start with. (For example, if you are in a rocky region, you can switch from the torch to the climbing gear, but you cannot switch to neither.)

Finally, once you reach the target, you need the torch equipped before you can find him in the dark. The target is always in a rocky region, so if you arrive there with climbing gear equipped, you will need to spend seven minutes switching to your torch.

For example, using the same cave system as above, starting in the top left corner (0,0) and moving to the bottom right corner (the target, 10,10) as quickly as possible, one possible route is as follows, with your current position marked X:

Initially:

X=.|=.|.|=.|=|=.
.|=|=|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..===..=|.|||.
.======|||=|=.|=
.===|=|===T===||
=|||...|==..|=.|
=.=|=.=..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

Down:

M=.|=.|.|=.|=|=.
X|=|=|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..===..=|.|||.
.======|||=|=.|=
.===|=|===T===||
=|||...|==..|=.|
=.=|=.=..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

Right:

M=.|=.|.|=.|=|=.
.X=|=|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..===..=|.|||.
.======|||=|=.|=
.===|=|===T===||
=|||...|==..|=.|
=.=|=.=..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

Switch from using the torch to neither tool:

M=.|=.|.|=.|=|=.
.X=|=|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..===..=|.|||.
.======|||=|=.|=
.===|=|===T===||
=|||...|==..|=.|
=.=|=.=..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

Right 3:

M=.|=.|.|=.|=|=.
.|=|X|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..===..=|.|||.
.======|||=|=.|=
.===|=|===T===||
=|||...|==..|=.|
=.=|=.=..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

Switch from using neither tool to the climbing gear:

M=.|=.|.|=.|=|=.
.|=|X|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..===..=|.|||.
.======|||=|=.|=
.===|=|===T===||
=|||...|==..|=.|
=.=|=.=..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

Down 7:

M=.|=.|.|=.|=|=.
.|=|=|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..X==..=|.|||.
.======|||=|=.|=
.===|=|===T===||
=|||...|==..|=.|
=.=|=.=..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

Right:

M=.|=.|.|=.|=|=.
.|=|=|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..=X=..=|.|||.
.======|||=|=.|=
.===|=|===T===||
=|||...|==..|=.|
=.=|=.=..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

Down 3:

M=.|=.|.|=.|=|=.
.|=|=|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..===..=|.|||.
.======|||=|=.|=
.===|=|===T===||
=|||.X.|==..|=.|
=.=|=.=..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

Right:

M=.|=.|.|=.|=|=.
.|=|=|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..===..=|.|||.
.======|||=|=.|=
.===|=|===T===||
=|||..X|==..|=.|
=.=|=.=..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

Down:

M=.|=.|.|=.|=|=.
.|=|=|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..===..=|.|||.
.======|||=|=.|=
.===|=|===T===||
=|||...|==..|=.|
=.=|=.X..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

Right 4:

M=.|=.|.|=.|=|=.
.|=|=|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..===..=|.|||.
.======|||=|=.|=
.===|=|===T===||
=|||...|==..|=.|
=.=|=.=..=X||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

Up 2:

M=.|=.|.|=.|=|=.
.|=|=|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..===..=|.|||.
.======|||=|=.|=
.===|=|===X===||
=|||...|==..|=.|
=.=|=.=..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

Switch from using the climbing gear to the torch:

M=.|=.|.|=.|=|=.
.|=|=|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..===..=|.|||.
.======|||=|=.|=
.===|=|===X===||
=|||...|==..|=.|
=.=|=.=..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

This is tied with other routes as the fastest way to reach the target: 45 minutes. In it, 21 minutes are spent switching tools (three times, seven minutes each) and the remaining 24 minutes are spent moving.

What is the fewest number of minutes you can take to reach the target?

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!

Further Reading

  1. Index of All Solutions - All solutions for 2018, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 22
  4. Advent of Code - Come join in and do these challenges yourself!