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

On Day 19 we walk around on an ASCII art line! 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 19, Part 1

The puzzle text can be found here.

Let me get some assumptions about our input out of the way:

The entry point is always on the top row.
If you hit a turn (+), it’s always safe to make either turn.
There is no need to attempt multiple paths when you hit a branch.

That makes this problem a lot easier to contend with. First, let’s parse our input into a grid which we will implement as a List<CharArray>, and define a class to represent a specific coordinate in the grid:

private val grid = input.map { it.toCharArray() }

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

In the Coordinate class, we’re creating two operators: plus, so we can add coordinates together, and ! so we can negate a coordinate. This will come in handy in a moment when we talk about movement. Since we’ll need to know what is in the grid at a given coordinate, let’s define an extension function to help us out:

private fun List<CharArray>.at(coordinate: Coordinate): Char =
    this[coordinate.y][coordinate.x]

The instructions talk about turning, so we should be able to represent movement and turning with our Coordinate class. If we keep a list of offsets (meaning: how many spots x and y we move each step), we can simplify our turning and stepping logic. So let’s go ahead an enumerate all possible types of moves we can make:

private val directions = listOf(
    Coordinate(0, 1),
    Coordinate(0, -1),
    Coordinate(1, 0),
    Coordinate(-1, 0)
)

And now that we have the parts, let’s talk about how to assemble them. We’re going to write a recursive function to traverse the grid, and implement this logic:

If we end up on a space, we’re done. Falling off the end of the line is our terminal condition.
If we end up on a letter, collect it.
If we end up on a plus, turn either left or right (either one will work) unless they represent a space.
In every case, we will go forward one step in the direction of travel.

The complicated part of that is step 3, turning. How do we go from the list of directions down to one of them that’s valid?

private fun turn(location: Coordinate, direction: Coordinate) =
    directions
        .filter { it != direction }
        .filter { it != !direction }
        .first { grid.at(location + it) != ' ' }

What this is saying is given a location and a direction of travel, find all the directions that aren’t the one we’re currently moving in, or the one that we came from (!direction - here’s our not operator). Then find the first one where if we go that way, we don’t end up with a space. Anything else (a letter, a pipe, a dash, another plus) is fine.

And then we have all we need to implement our recursive function:

private tailrec fun traverse(location: Coordinate,
                             direction: Coordinate,
                             seen: List<Char> = emptyList()): String =
    if (grid.at(location) == ' ') seen.joinToString("")
    else {
        when (grid.at(location)) {
            in 'A'..'Z' -> traverse(location + direction, direction, seen + grid.at(location))
            '+' -> {
                val turn = turn(location, direction)
                traverse(location + turn, turn, seen)
            }
            else -> traverse(location + direction, direction, seen)
        }
    }

I realize there’s a lot going on, so let’s examine it in detail. We’re given a location in the grid, a direction of travel, and a list of letters we’ve seen. The first thing we do in any recursive function is to test our terminal condition - that we’ve fallen off the line. If that’s happened, we turn our seen list into a String and return it.

On the other hand, if we’re not done we have some work for ourselves. If we’re on a letter, we collect it and call traverse again with one step in the direction of travel, and our new letter. Both are implemented by the plus operator on their respective classes. If we find a +, that means we want to turn, so we call the turn function we’ve already talked about and call traverse with one step in our NEW direction, and the new direction. Otherwise, we’re doing something else so we just call traverse with one step in the current direction of travel.

Call this function by finding the entry point on the grid, and telling it we’re moving the equivalent of south:

fun solvePart1(): String =
    traverse(Coordinate(input[0].indexOf("|"), 0), Coordinate(0, 1))

In a few milliseconds,this crank out the right answer, earning us our first star of the day!

⭐ Day 19, Part 2

The puzzle text can be found here.

Good news! We can make a very slight modification to our existing function to track steps. We can just pass the current number of steps to traverse every time we call it. Let’s look at our new version, to which I’ve added steps:

private tailrec fun traverse(location: Coordinate,
                             direction: Coordinate,
                             seen: List<Char> = emptyList(),
                             steps: Int = 0): Pair<Int, String> =
    if (grid.at(location) == ' ') Pair(steps, seen.joinToString(""))
    else {
        when (grid.at(location)) {
            in 'A'..'Z' -> traverse(location + direction, direction, seen + grid.at(location), steps.inc())
            '+' -> {
                val turn = turn(location, direction)
                traverse(location + turn, turn, seen, steps.inc())
            }
            else -> traverse(location + direction, direction, seen, steps.inc())
        }
    }

As you can see, I’ve also had to change the return type to give us back both the steps and the letters we’ve seen, so both of our part 1 and 2 functions will also change slightly before we earn that second star:

fun solvePart1(): String =
    traverse(Coordinate(input[0].indexOf("|"), 0), Coordinate(0, 1)).second

fun solvePart2(): Int =
    traverse(Coordinate(input[0].indexOf("|"), 0), Coordinate(0, 1)).first

There are a ton of ways you could solve this problem, I highly encourage you to experiment with this one. I had two completely different solutions in addition to this (both iterative) and settled on this one. I feel it struck the right balance between code size and clarity. My other solutions put a heavy emphasis on directions and turning, implementing them as sealed classes.

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

19 days and we’ve earned 38 stars with only 12 left to go!

⭐ Day 19, Part 1

⭐ Day 19, Part 2

Further Reading