# Advent of Code 2017 - Day 24, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 24: 'Electromagnetic Moat'

Posted on

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!