Advent of Code 2022 - Day 16, in Kotlin - Proboscidea Volcanium • Todd Ginsberg

The solution to Part Two of this puzzle took me a really long time to get right. I had a few ideas and tried them all. Some worked slowly, and some didn’t work at all. In the end I compromised on one of my principles for these solutions (no external libraries) in order to get past a sticking point, and it worked! I’m pretty happy with how this ended up.

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

Puzzle Input

We’ll parse our input into a class called ValveRoom, which contains the name of the room itself, a list of paths leading from this room, and the flowRate of the valve in this room. As usual, we’ll define an of function in the companion object to help with parsing. And as usual, I’m being stubborn about regular expressions and using substringBefore and substringAfter.

// In Day16

private data class ValveRoom(val name: String, val paths: List<String>, val flowRate: Int) {
        companion object {
            fun of(input: String): ValveRoom =
                ValveRoom(
                    input.substringAfter(" ").substringBefore(" "),
                    input.substringAfter("valve").substringAfter(" ").split(", "),
                    input.substringAfter("=").substringBefore(";").toInt()
                )
        }
    }

We will map each line of input to its ValveRoom giving us a List<ValveRoom>. Because we want to map the ValveRoom objects by their name, we’ll use associateBy from the Kotlin Standard Library to do this, giving us a Map<String, ValveRoom> of rooms.

class Day16(input: List<String>) {

    private val rooms: Map<String, ValveRoom> = input.map { ValveRoom.of(it) }.associateBy { it.name }

}

Adding A Combinatorics Library

For Part Two, we’re going to need an open source library called combinatoricskt , written by @shiguruikai . Its API is easy to understand, and most importantly, got me past what was probably a buggy attempt at doing this myself.

To add this, we’ll modify build.gradle.kts and add it to the dependencies section:

// In build.gradle.kts

dependencies {
    implementation("com.github.shiguruikai:combinatoricskt:1.6.0") {
        because("I need combinations of sets for Day 16 and this was a bug-free way to do it")
    }
}

In theory, the because part is optional but I like to include my reasoning for adding a library as a form of documentation. If you do this on larger projects, your future self will thank you!

⭐ Day 16, Part 1

The puzzle text can be found here.

We’ll start by refining our ValveRoom objects down to the set of transitions we actually care about. If you look at the input, there are a lot of rooms that don’t do anything. We could move to them, but doing so would be a waste. What we need is to know the cost of moving from one room to any other room that has work to do, but only for rooms that have actual work to do. This reduces the search space significantly. We’ll call this function calculateShortestPaths, and its return type is a bit hard to read. It is a Map<String, Map<String, Int>> where the key to the first map is the name of a room, and the value is another map whose key is a destination room, and its value is the cost to move to that room and turn on the valve.

// In Day16

private fun calculateShortestPaths(): Map<String, Map<String, Int>> {
    val shortestPaths = rooms.values.associate {
        it.name to it.paths.associateWith { 1 }.toMutableMap()
    }.toMutableMap()

    shortestPaths.keys.permutations(3).forEach { (waypoint, from, to) ->
        shortestPaths[from, to] = minOf(
            shortestPaths[from, to], // Existing Path
            shortestPaths[from, waypoint] + shortestPaths[waypoint, to] // New Path
        )
    }
    val zeroFlowRooms = rooms.values.filter { it.flowRate == 0 || it.name == "AA" }.map { it.name }.toSet()
    shortestPaths.values.forEach { it.keys.removeAll(zeroFlowRooms) }
    val canGetToFromAA: Set<String> = shortestPaths.getValue("AA").keys
    return shortestPaths.filter { it.key in canGetToFromAA || it.key == "AA" }
}

We start by looking at all the rooms and calling associate and asociateWith to create our structure. Since we’ll be manipulating the data before we return it, we’ll be sure to convert each map to a MutableMap. At this point shortestPaths has a key of a source room, and a value of another map whose key is the destination room and the cost to move there is 1.

Next, we will use the combinatoricskt library to generate permutations of all our room names. I had originally written a function to do this, but since we’ll use this library for Part Two, we can use it here too. Basically, we get a steady stream of List<String> of length 3. We will destructure these into three names - waypoint, to, and from. If we can get from to to waypoint and from waypoint to from cheaper than our previous answer of going directly from to to from, we take that and store it in the shortestPath map. You might see some funky array acessors, we’ll discuss those in a moment.

So now we have our map of sources, destinations, and cost. We want to filter this down to just the rooms that make sense. Basically anything with a positive flow rate and AA (the starting point). So we refine our shortestPath map structure down to just the rooms with a positive flow rate, and AA.

Now about those funky array-style accessors:

// In Day16

private operator fun Map<String, MutableMap<String, Int>>.set(key1: String, key2: String, value: Int) {
    getValue(key1)[key2] = value
}

private operator fun Map<String, Map<String, Int>>.get(key1: String, key2: String, defaultValue: Int = 31000): Int =
    get(key1)?.get(key2) ?: defaultValue

I don’t especially like nested maps, and I don’t especially like the awkward syntax to deal with nullable values coming out of them. So we’ll hide this behind two operator functions - get and set. Thankfully, Kotlin lets us define these functions and provide whatever arguments we want. In both cases, we define the key to the outer and inner maps. We pick 31000 as the default defauleValue because it’s a high number (rather than make this nullable, which would be confusing, I think).

We’ll store the results of the shortestPath calculation in cheapestPathCosts.

// In Day16

private val cheapestPathCosts: Map<String, Map<String, Int>> = calculateShortestPaths()

To do the work of evaluating the cost of turning on various valves, we’ll write a recursive function (a function that calls itself). Each time through the call stack, we find one of the cheapestPathCosts rooms that we have not already seen, go to it by incurring them movement cost, gain from it by adding the total amount of flow it generates, adding the room to the list of rooms we’ve visited, and then calling ourselves with this new data. This strategy will quickly work through every combination of room visits we could possible have, and because we use maxOfOrNull, we will eventually get the right answer.

// In Day16

private fun searchPaths(
    location: String,
    timeAllowed: Int,
    seen: Set<String> = emptySet(),
    timeTaken: Int = 0,
    totalFlow: Int = 0
): Int = cheapestPathCosts
    .getValue(location)
    .asSequence()
    .filterNot { (nextRoom, _) -> nextRoom in seen }
    .filter { (_, traversalCost) -> timeTaken + traversalCost + 1 < timeAllowed }
    .maxOfOrNull { (nextRoom, traversalCost) ->
        searchPaths(
            nextRoom,
            timeAllowed,
            seen + nextRoom,
            timeTaken + traversalCost + 1,
            totalFlow + ((timeAllowed - timeTaken - traversalCost - 1) * rooms.getValue(nextRoom).flowRate)
        )
    } ?: totalFlow

Some interesting things to notice - we use the _ to indicate to Kotlin that we don’t care about a specific value. I wanted to use destructuring here as much as possible with clear names, but sometimes we have values we don’t care about in this context. That’s why _ is nice, we don’t have to make up a dummy name.

We can now solve Part One by calling searchPaths and giving it the starting point “AA”, and 30 as a time budget.

// In Day16

fun solvePart1(): Int = searchPaths("AA", 30)

Star earned! Onward!

⭐ Day 16, Part 2

The puzzle text can be found here.

For all the grief this part caused me, I’m surprised the solution has relatively little code.

The basic theory is this: We take the total list of rooms to go visit and divide it up between me and the elephant. We run the Part One solution for my half of the list, and add it to Part One answer for the elephant’s half of the list. By generating every possible combination of rooms, and taking the maximum value of the two runs, we’ll get our answer.

This is where the combinatoricskt comes in handy - it generates the combinations of the list of rooms we can move to. I just could not figure out a bug-free way of doing this, and this library saved the day.

// In Day16

fun solvePart2(): Int =
    cheapestPathCosts.keys.filter { it != "AA" }
        .combinations(cheapestPathCosts.size / 2)
        .map { it.toSet() }
        .maxOf { halfOfTheRooms ->
            searchPaths("AA", 26, halfOfTheRooms) + 
            searchPaths("AA", 26, cheapestPathCosts.keys - halfOfTheRooms)
        }

Let’s break this function down. First, we get a List<String> representing every one of the rooms in the cheapestPathCosts set, minus the starting room (“AA”). We then use the combinatoricskt to get combindations of this list. The argument we pass to combinations is the size of the resulting combinations lists we want. In our case half the total rooms. This returns us a Sequence<List<String>>, which we map down to Sequence<Set<String>>.

At this point, we have a steady stream of halfOfTheRooms, and we can use this to solve the puzzle. The answer (for my input, and the sample input, anyway) is to use searchPaths from Part One with a timeAllowed of 26 instead of 30. So how does this help? We run it twice and add the results - once for our trip through the rooms (using half of the rooms) and another for the elephant (using the other half of the rooms). Since we’re passing in a new set of seen rooms to each call, we can assure ourselves that neither we or the elephant will see each others rooms! Adding the results of me looking at my half of the rooms, and the elephant looking at its half of the rooms, give us an answer. Taking the maximum value of that calculation gives us the solution to the puzzle!

On my computer, this finishes in about seven seconds. That’s the slowest runtime we’ve had for a puzzle this year, but I’ll take it as it is not an unreasonable amount of time to spend on this.

Star most definitely earned! See you tomorrow!

⭐ Day 16, Part 1

⭐ Day 16, Part 2

Further Reading