Advent of Code 2017 - Day 24, in Kotlin • Todd Ginsberg

On Day 24 we will recursively build bridges. If you’d rather jump straight to the code, it’s right here .

I’ve challenged myself to post each day’s solution to Github and blog about it. Like last year, I’m going to be solving these problems in Kotlin. I might go back and revise solutions, but I’ll be sure to annotate that fact in these posts.

Problem Input

We are given a set of input for this problem. I’ve loaded this into a List<String> called input, which we will do some further parsing on later.

⭐ Day 24, Part 1

The puzzle text can be found here.

Let’s get some housekeeping out of the way before we decide how to solve the problem. Here we parse our input and define a data class to represent our bridge components:

private val components = parseInput(input)

private fun parseInput(input: List<String>): Set<Component> =
    input.map { it.split("/") }.map { Component(it[0].toInt(), it[1].toInt()) }.toSet()

data class Component(private val x: Int, private val y: Int) {
    val strength = x + y
    fun fits(port: Int): Boolean = x == port || y == port
    fun opposite(port: Int): Int = if (port == x) y else x
}

Our Component class has a property to tell us its strength, a function to see if another port fits with this one, and a function to get the opposite end of the given port. That way we can test if one Component fits with another.

While we’re at it, a way to get the strength of a bridge, which we are going to implement as a List<Component>:

private fun List<Component>.strength(): Int = this.sumBy { it.strength }

Now, how do we solve this? Let’s think about what we have. We always know what port size we’re plugging into (starting with 0). From there, we have a set of Components, some of which fit that port and some that don’t. Picture the possibilities of each decision we could make branching out like a tree. When I think of problems easily expressed as trees, I think of recursive solutions:

private fun makeBridges(components: Set<Component>,
                        bridge: List<Component> = emptyList(),
                        port: Int = 0): List<List<Component>> {
    val compatible = components.filter { it.fits(port) }
    return when (compatible.size) {
        0 -> listOf(bridge)
        else ->
            compatible.flatMap { pick ->
                makeBridges(
                    components - pick,
                    bridge + pick,
                    pick.opposite(port)
                )
            }
    }
}

Let’s go over what our makeBridges function actually does. It’s given a set of possible Components to choose from, a bridge that we are in the process of constructing (starting with an empty bridge), and the port we’ve most recently plugged into (starting with 0). The fist thing we do is set aside the Components that are compatible. A Component is compatible if it fits on the end port of the bridge we’re currently building. Once we know what we have to choose from, we test our end condition. If there are no components to pick from, we’ve made a bridge that we cannot extend, so we will return that bridge in a single element list. Why in a list? Because our makeBridges function returns a list of all the bridges it can make, which is represented as List<List<Component>>.

On the other hand, if we have components to pick from, we want to test all of them so we will go through that set of compatible Components and try extending the bridge with each one. So we recurse, calling our makeBridges function again. When we call it, we have to take out the current components we’re trying from the list of all possible components, and tell the function that our bridge now contains that pick. We also tell the function call that it’s looking at the opposite port end of the components we’ve just picked. And in order to make the types line up we use flatMap for this, which will just produce one list of bridges, rather than list of list of bridges.

Executing this and picking out the strongest bridge is a simple prospect:

fun solvePart1(): Int =
    makeBridges(components).maxBy { it.strength() }?.strength() ?: 0

Since our makeBridges function returns all of the bridges that can be made, we have to measure their strength, find the maximum value, and then return that value to the caller. All that work earns us a star!

⭐ Day 24, Part 2

The puzzle text can be found here.

We already have everything we need because our bridge building function returns all the bridges it can. Solving part 2 is a simple matter of picking out the longest bridges and finding the strongest among them.

fun solvePart2(): Int =
    makeBridges(components)
        .maxWith(
            compareBy({ it.size }, { it.strength() })
        )?.strength() ?: 0

Thanks to Kotlin’s strong standard library, we don’t have to jump through too many hoops. We use the maxWith function which takes a comparator. In this case, we’re building one comparator using compareBy, which compares the size of the List<Component> and then their strengths in the case of a tie. Because maxWith might not actually find a max element (if the list is empty), we have to safely call .strength() on the List<Component> that we ultimately decide is the longest and strongest.

Second star: done!

I hope you had fun.

That makes 24 days and 48 stars with only 2 left to go! Tomorrow is our last day!

⭐ Day 24, Part 1

⭐ Day 24, Part 2

Further Reading