Skip to Content

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!

I hope you had fun.

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

Further Reading

  1. Index of All Solutions - All solutions for 2017, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 24.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - The Crunge, by Led Zeppelin (where’s that confounded bridge?).