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

On Day 22 we a nasty infection in the form of another grid problem. 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 22, Part 1

The puzzle text can be found here.

Another grid problem! This time it is unbounded, so we have to weigh our options. Approaches we could take:

Create a massive grid that we couldn’t possibly overrun.
Implement the grid as a List<List<Char>> and move all of the columns and rows if we run over the edges.
Create a Node and create the neighbors when we need them.
Store coordinates in a data class as a key to a map, and the value of the node as the value in the map.

I’m going to go with option 4, a map of coordinates. I feel 1 would work but uses a ton of memory for no real purpose (also, it will become impractical when we get to part two). Number 2 is impractical, expanding the grid on demand is too much work for too little gain. And number 3 is more difficult than it looks - if I need a new neighbor to the North, we have to make sure it links up with any of its existing neighbors.

So a map it is! Let’s define the key, an x/y Point. Sure, we could use Pair<Int,Int>, but this seems easier to read.

data class Point(val x: Int, val y: Int) {
    operator fun plus(that: Point): Point =
        Point(x + that.x, y + that.y)
}

The operator + will allow us to alter our location by means of an offset Point. I’m also going to define an enumeration for our node state. Originally I had just used true/false, but the question changes in part two and we’ll need this later:

enum class NodeState {
    Clean,
    Infected
}

We have enough to parse our input and set our starting point.

private val grid = parseInput(input)
private var current = Point(input.size / 2, input.first().length / 2)

private fun parseInput(input: List<String>): MutableMap<Point, NodeState> {
    val destination = mutableMapOf<Point, NodeState>()
    input.forEachIndexed { y, row ->
        row.forEachIndexed { x, char ->
            destination[Point(x, y)] = if (char == '.') NodeState.Clean else NodeState.Infected
        }
    }
    return destination
}

As with previous days, we have options when it comes to direction. I’m going to keep today nice and simple and just define the direction as an integer, and the offsets for turning/movement as a list of Point objects. I will also provide handy methods for turning left and right. I could have put these on Point, but I wanted to keep movement separated from location.

private val directions = listOf(Point(0, -1), Point(1, 0), Point(0, 1), Point(-1, 0))
private var pointing = 0

private fun left(): Int =
    if (pointing == 0) 3 else pointing - 1

private fun right(): Int =
    pointing.inc() % 4

The left and right functions just provide a new index into our directions list, taking care to not over or underflow.

Now we have everything we need to walk around on our grid and implement the core requirements:

fun solvePart1(iterations: Int = 10_000): Int {
    var infectionsCaused = 0
    repeat(iterations) {
        if (grid.getOrDefault(current, NodeState.Clean) == NodeState.Clean) {
            infectionsCaused += 1
            grid[current] = NodeState.Infected
            pointing = left()
        } else {
            // Infected
            grid[current] = NodeState.Clean
            pointing = right()
        }
        current += directions[pointing]
    }
    return infectionsCaused
}

For every iteration, we either are causing or cleaning up an infection, as well as moving. Movement is done by changing pointing to the offset we care about (left or right from the past one). We keep a counter of infectionsCaused and move after every turn.

Running this for 10,000 iterations takes about 15ms and earns us a star!

⭐ Day 22, Part 2

The puzzle text can be found here.

See? I told you we’d need that enum. Let’s redefine it:

enum class NodeState {
    Clean,
    Infected,
    Weakened,
    Flagged
}

And while we’re at it, let’s provide a reverse() function to go along with left() and right():

private fun reverse(): Int =
    (pointing + 2) % 4

And now we can solve part two, which looks a lot like part one, but with more states:

fun solvePart2(iterations: Int = 10_000_000): Int {
    var infectionsCaused = 0
    repeat(iterations) {
        when (grid.getOrDefault(current, NodeState.Clean)) {
            NodeState.Clean -> {
                pointing = left()
                grid[current] = NodeState.Weakened
            }
            NodeState.Weakened -> {
                infectionsCaused += 1
                grid[current] = NodeState.Infected
            }
            NodeState.Infected -> {
                pointing = right()
                grid[current] = NodeState.Flagged
            }
            NodeState.Flagged -> {
                pointing = reverse()
                grid[current] = NodeState.Clean
            }
        }
        current += directions[pointing]
    }
    return infectionsCaused
}

This runs in only about 1.6 seconds for me, even with 10,000,000 iterations! That’s one more star for us.

I hope you had fun.

That makes 22 days and 44 stars with only 6 left to go! Only 3 days remaining!

⭐ Day 22, Part 1

⭐ Day 22, Part 2

Further Reading