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

On day 3 of Advent of Code 2017 , we get a more mathematical-based problem. These kinds of problems usually present more of a challenge for me personally. It’s interesting to see what kinds of problems appear to each user. So, there might just be easier ways to solve today’s problems if I were a stronger mathematician, so feedback on that is most welcome!

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.

⭐ Day 3, Part 1

In part one, our hero (us) comes across a computer with spiral memory and needs to know how to get from the middle of the spiral to a target number. We’re reminded by the puzzle author what Manhattan Distance is, and to use that to express our answer.

The problem:

The puzzle text can be found here.

OK, perhaps there’s a really clever way to do this that’s eluding me. Essentially what I’m going to do first is figure out which “ring” my target number is on. That gives me the steps I need to take on one axis. That’s the simple part.

Next, I’m going to find the four mid-points for each of the sides of the ring I’m on. Then it’s a simple matter of figuring out which one of those mid-points is closest to our target number. That gives us the number of steps to take on the other axis. I found this solution easier to reason about than perhaps doing a more complicated formula, or constructing the grid in memory and walking it.

fun solvePart1(): Int {
    val sideLength = lengthOfSideWith(target)
    val stepsToRingFromCenter = (sideLength - 1) / 2
    val midpoints = midpointsForSideLength(sideLength)
    return stepsToRingFromCenter + midpoints.map { abs(target - it) }.min()!!
}

private fun lengthOfSideWith(n: Int): Int =
    ceil(sqrt(n.toDouble())).toInt().let {
        if (it.isOdd()) it
        else it + 1
    }

fun midpointsForSideLength(sideLength: Int): List<Int> {
    val highestOnSide = sideLength * sideLength
    val offset = ((sideLength - 1) / 2.0).toInt()
    return (0..3).map {
        highestOnSide - (offset + (it * sideLength.dec()))
    }
}

I don’t like is the fact that I had to use the hold my beer operator (!!) when I know for a fact that list does have a minimum value.

Additionally, in order to make things a little more readable and because I feel like it will come in handy, I’ve opted to make extension functions on Int to test for even/odd numbers.

// Even/Odd on Integer
fun Int.isEven(): Boolean = this % 2 == 0
fun Int.isOdd(): Boolean = this % 2 != 0

Tests passing, star earned, we move on to part 2!

⭐ Day 3, Part 2

The puzzle text can be found here.

This strikes me as a job for Kotlin’s generateSequence . I’m going to create a grid, seed it with 1 in the middle, and walk around in a spiral, emitting each spot I get to as the next value from the generated sequence. I’ll take the first number from that sequence that’s larger than our target and call that our answer.

The sequence will look like this:

1 1 2 4 5 10 11 23 ...

Maybe instead of a grid, we could do this as a list. We would have to have a way to know that given how far along we are, which spots are our neighbors and look back. Perhaps I’ll do an alternate version using this approach if I can figure out a clear way to express that.

I’m going to start out defining a Grid class, which has a List<IntArray> to represent our actual grid, a pointer to the current spot, and a sealed class structure to represent a Direction.

First, let’s think about Direction. It has a way to move forward, and it knows which direction comes next when turning. I’ll define Direction as a sealed class with four implementations. I’d like to implement this as an enum, but I have circular reference issues if I do that, unfortunately.

sealed class Direction {
    abstract fun move(point: Pair<Int, Int>): Pair<Int, Int>
    abstract val turn: Direction
}

object East : Direction() {
    override fun move(point: Pair<Int, Int>): Pair<Int, Int> = Pair(point.first + 1, point.second)
    override val turn = North
}
// Other directions are similar.

As you can see, East is an object since it doesn’t have state, and if you turn while facing East, you are facing North. This will come in handy as we walk our grid, which we’ll define below.

We’ll start with something basic for the grid, giving it no behavior.

class Grid(size: Int) {
    private var pointer: Pair<Int, Int> = Pair(size / 2, size / 2)
    private var direction: Direction = East
    private val grid: List<IntArray> = (0 until size).map { IntArray(size) }.apply {
        this[pointer.first][pointer.second] = 1
    }

    fun generateSpots(): Sequence<Int> = 
        TODO() // We will define this below.

    private fun sumNeighbors(): Int = 
        TODO() // We will define this below.

    private fun atSpot(spot: Pair<Int, Int>): Int? =
        atSpot(spot.first, spot.second)

    private fun atSpot(x: Int, y: Int): Int? =
        if (x in (0 until grid.size) && y in (0 until grid.size)) grid[x][y]
        else null
}

Creating a Grid will give us a grid of all zeros, except for the starting point (the exact middle) which has a value of 1. You gotta start somewhere. I’ll also throw in some helper functions to get the value of a spot in the grid, and they’ll both guard against ArrayIndexOutOfBoundsException by returning an Int?.

Now, to walk our grid, I said we’d use a sequence generator. We have to seed our generator with something, so we will give it a 1, because that’s what our pointer is pointing to. The logic to generate the next value in the sequence is:

Advance the pointer one spot in the direction of travel.
Sum the neighbors at our pointer’s spot and store them in the grid at the pointer.
If turning would land us on a spot with a 0, turn. Otherwise, just keep going in our direction of travel.
Emit the next value of our sequence, which is the value in the grid at the pointer.

And for me, that looks like this:

fun generateSpots(): Sequence<Int> =
    generateSequence(1) {
        pointer = direction.move(pointer)
        grid[pointer.first][pointer.second] = sumNeighbors()
        // Turn if we can.
        direction = if (atSpot(direction.turn.move(pointer)) == 0) direction.turn else direction
        atSpot(pointer)
    }

Summing the neighbors of a spot is also easy. We just have to know the values of all the spots around us. Since we have that atSpot() function that handles array bounds for us, we can just filter nulls and sum them up.

private fun sumNeighbors(): Int =
    (pointer.first - 1..pointer.first + 1).map { x ->
        (pointer.second - 1..pointer.second + 1).map { y ->
            atSpot(x, y)
        }
    }.flatten()
        .filterNotNull()
        .sum()

And the actual solution to our problem is easy. Create a Grid, generate a sequence, find the first value we care about:

fun solvePart2(): Int =
    Grid(lengthOfSideWith(target))
        .generateSpots()
        .first { it > target }

In the end, I feel like that solution is probably a bit overwrought. I’ll put some thought into a simpler approach, but since we did in fact generate the correct answer, we’ve earned ourselves another star!

At the end of day 3, we’ve earned 6 stars with 44 left to go! Bully!

⭐ Day 3, Part 1

⭐ Day 3, Part 2

Further Reading