# 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 CPU itself is a large, black building surrounded by a bottomless pit. Enormous metal tubes extend outward from the side of the building at regular intervals and descend down into the void. There’s no way to cross, but you need to get inside.

No way, of course, other than building a bridge out of the magnetic components strewn about nearby.

Each component has two ports, one on each end. The ports come in all different types, and only matching types can be connected. You take an inventory of the components by their port types (your puzzle input). Each port is identified by the number of pins it uses; more pins mean a stronger connection for your bridge. A `3/7` component, for example, has a type-3 port on one side, and a type-7 port on the other.

Your side of the pit is metallic; a perfect surface to connect a magnetic, zero-pin port. Because of this, the first port you use must be of type 0. It doesn’t matter what type of port you end with; your goal is just to make the bridge as strong as possible.

The strength of a bridge is the sum of the port types in each component. For example, if your bridge is made of components `0/3`, `3/7`, and `7/4`, your bridge has a strength of `0+3 + 3+7 + 7+4 = 24`.

For example, suppose you had the following components:

``````0/2
2/2
2/3
3/4
3/5
0/1
10/1
9/10``````

With them, you could make the following valid bridges:

``````0/1
0/1--10/1
0/1--10/1--9/10
0/2
0/2--2/3
0/2--2/3--3/4
0/2--2/3--3/5
0/2--2/2
0/2--2/2--2/3
0/2--2/2--2/3--3/4
0/2--2/2--2/3--3/5``````

(Note how, as shown by `10/1`, order of ports within a component doesn’t matter. However, you may only use each port on a component once.)

Of these bridges, the strongest one is `0/1--10/1--9/10`; it has a strength of `0+1 + 1+10 + 10+9 = 3*`.

What is the strength of the strongest bridge you can make with the components you have available?

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 bridge you’ve built isn’t long enough; you can’t jump the rest of the way.

In the example above, there are two longest bridges:

``````0/2--2/2--2/3--3/4
0/2--2/2--2/3--3/5``````

Of them, the one which uses the 35 component is stronger; its strength is `0+2 + 2+2 + 2+3 + 3+5 = 19`.

What is the strength of the longest bridge you can make? If you can make multiple bridges of the longest length, pick the strongest one.

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!