Skip to Content

Advent of Code 2017 - Day 11, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 11: 'Hex Ed'

Posted on

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

Crossing the bridge, you’ve barely reached the other side of the stream when a program comes up to you, clearly in distress. “It’s my child process,” she says, “he’s gotten lost in an infinite grid!”

Fortunately for her, you have plenty of experience with infinite grids.

Unfortunately for you, it’s a hex grid.

The hexagons (“hexes”) in this grid are aligned such that adjacent hexes can be found to the north, northeast, southeast, south, southwest, and northwest:

  \ n  /
nw +--+ ne
  /    \
-+      +-
  \    /
sw +--+ se
  / s  \

You have the path the child process took. Starting where he started, you need to determine the fewest number of steps required to reach him. (A “step” means to move from the hex you are in to any adjacent hex.)

For example:

  • ne,ne,ne is 3 steps away.
  • ne,ne,sw,sw is 0 steps away (back where you started).
  • ne,ne,s,s is 2 steps away (se,se).
  • se,sw,se,sw,sw is 3 steps away (s,s,sw).

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

How many steps away is the furthest he ever got from his starting position?

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!

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 11.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - The Grid, by Daft Punk.