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

On Day 11 we will learn the value of researching what smart people have to say about our problem domain before deriving things from first principles. 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 String called input, which we will do some further parsing on later.

⭐ Day 11, Part 1

The puzzle text can be found here.

I didn’t know anything at all about how hexagonal grids work before looking at this problem. At one point I wanted to write a game based on hex grids and bookmarked a fantastic page from Red Blob Games on the subject. If you’ve never seen this page it goes into an amazing amount of detail on how to think about the various flavors of hex grids (we’re evidently using what’s called an “odd-q” grid), how to label them, and how to traverse them.

The trick with our grid is to think of it as a three dimensional cube projected into two dimensional space. Normally a square grid is going to have x and y coordinates only. But because we are really crawling around the outside of a cube, we’ll need three axes: x, y, and z.

This image from the Distances Section above, shows what I’m talking about with x, y, and z conveniently labeled. I’ve shown where North and South are, because this image doesn’t exactly represent our “odd-q” structure as it is presented (but it could, if you turn your head a bit).

hex grid

Let’s write a class to encapsulate our Hex Spot, now that we know how to address them and what changes when we move:

class HexSpot(private val x: Int, private val y: Int, private val z: Int) {

    fun travel(direction: String): HexSpot =
        when (direction) {
            "n" -> HexSpot(x, y + 1, z - 1)
            "s" -> HexSpot(x, y - 1, z + 1)
            "ne" -> HexSpot(x + 1, y, z - 1)
            "nw" -> HexSpot(x - 1, y + 1, z)
            "se" -> HexSpot(x + 1, y - 1, z)
            "sw" -> HexSpot(x - 1, y, z + 1)
            else -> throw IllegalArgumentException("Invalid direction: $direction")
        }

    fun distanceTo(there: HexSpot): Int =
        maxOf(
            (this.x - there.x).absoluteValue,
            (this.y - there.y).absoluteValue,
            (this.z - there.z).absoluteValue
        )
}

I didn’t go crazy and provide multiple implementations for each type of hex grid. We will refactor later if we need that level of detail.

The reference page even provides a very simple distance calculation, which is exactly what we need. Finally, to get our answer we just walk our grid and then calculate the distance from where we end up to the origin:

class Day11(input: String) {

    private val origin = HexSpot(0, 0, 0)
    private val steps = input.split(",")

    fun solvePart1(): Int =
        steps
            .fold(origin) { spot, dir -> spot.travel(dir) }
            .distanceTo(origin)
}

That earns us a star, let’s move on.

⭐ Day 11, Part 2

The puzzle text can be found here.

We can solve this directly and there are a couple of ways to do it. The way I decided was to perform a fold over our directions, turning them into a List<HexSpot>, which essentially creates a path from the origin to where we end up. Measure the distance to each one, take the maximum value, and we’re done.

fun solvePart2(): Int =
    steps
        .fold(listOf(origin)) { path, dir -> path + (path.last().travel(dir)) }
        .map { it.distanceTo(origin) }
        .max() ?: 0

Again, there are probably a few good ways to approach that solution, but this one passes the tests and earns us our second star!

I hope you’ve learned something and as always, feedback is welcome!

11 days and we’ve earned 22 stars with 28 left to go!

⭐ Day 11, Part 1

⭐ Day 11, Part 2

Further Reading