Skip to Content

Advent of Code 2019 - Day 6, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2019, Day 6: 'Universal Orbit Map'

Posted on

When I woke up and read the title of today’s puzzle, I thought “Oh great, they’re going to have us learning differential equations for calculating orbits using IntCode or something”. Thankfully, today’s problem wasn’t nearly that complicated.

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

Problem Input

We’re given a list of String objects representing orbital pairs. What we want to end up with is a Map where the orbiting object is the key and the entity it is orbiting is the value. Moon -> Earth, for example.

private val orbitPairs: Map<String, String> = 
    input.map { it.split(")") }.associate { it.last() to it.first() }

Here, we split each line of input on ) (the symbol for orbit), and use Kotlin’s associate function to turn a List<String> (in this case) into a Map<String, String>. The logic we pass to associate in the lamba provides a Pair<String, String>, which are used to represent a key/value pair for the Map.

This is shorthand for:

private val orbitPairs: Map<String, String> = 
    input.map { it.split(")") }.map { it.last() to it.first() }.toMap()

⭐ Day 6, Part 1

The puzzle text can be found here.

In order to calculate the total number of orbits and direct orbits we need to know how far each element is from the center of the system. Once we have each of those distances, we can add them together to get our answer!

Let’s concentrate on getting a single path from one orbiting object to the center. For this, we’ll write a recursive function to generate the path. We could change our return type to an Int, denoting the length of the path, but I know things about Part 2, so let’s not do that.

private fun pathTo(orbit: String, path: MutableList<String> = mutableListOf(orbit)): List<String> =
    orbitPairs[orbit]?.let { around ->
        path.add(orbit)
        pathTo(around, path)
    } ?: path

Let’s walk through this. The first thing to observe is the path argument. It’s a MutableList<String> and will ultimately be our path. Every time we recurse (call ourselves), we add the element we just found to it. However, the first time we call the function, the only part of the path we know is the starting point. To make things easier, we’ll initialize the path with the starting point by default.

If our orbit is found in the orbitPairs map, we know the path is still being constructed. If this happens we add around (what orbit revolves “around”) to the list we are building and call ourselves with the next orbit (around). On the other hand, if we can’t find anything that orbit is orbiting, we just return the path we’ve calculated because we’ve reached the end.

The benefits of this are that we’re not constantly re-allocating a List. By passing a MutableList down through the call stack, we can just add to it as we need to. Another benefit is that this path is in order (so Moon -> Earth -> Sun). I wrote this another way initially and it was backwards and I ended up having to reverse the list to use it in Part 2.

The drawback is that this isn’t tail recursive. I didn’t end up needing that, and I don’t think any of the program inputs available are so large that it would be required for any of them. Re-writing pathTo to be tail recursive might be a nice challenge, if you are looking for something to do.

All that’s left is to sum all our paths:

fun solvePart1(): Int =
    orbitPairs.keys.sumBy { pathTo(it).size -1 }

We have to subtract 1 at the end because this is a variant of The Fence Post Error. We want to calculate one less than the total number of orbital elements to get how far away each one is from the start.

Problem solved, star earned!

⭐ Day 6, Part 2

The puzzle text can be found here.

Because we wrote our recursive function to generate a path (List<String>), rather than just its length, we’re very close to being able to solve part 2. My plan is to calculate our path (called “YOU”) to the end, and Santa’s path (called “SAN”) to the end. The first point they intersect is the common point.

fun solvePart2(): Int {
    val youToRoot = pathTo("YOU")
    val santaToRoot = pathTo("SAN")
    val intersection = youToRoot.intersect(santaToRoot).first()

    return youToRoot.indexOf(intersection) + santaToRoot.indexOf(intersection) - 2
}

Once we know the intersection point, we can figure out how far along that point is on our path, and how far along that point is on Santa’s path. We subtract 2 because we don’t want to count ourselves or Santa on those paths (for the same reason we subtracted 1 in part 1).

Running this solves Part 2 and earns us our second star for today!

Further Reading

  1. Index of All Solutions - All posts and solutions for 2019, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 6
  4. Advent of Code - Come join in and do these challenges yourself!