# Advent of Code 2017 - Day 19, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 19: 'A Series of Tubes'

Posted on

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:

1. The entry point is always on the top row.
2. If you hit a turn (`+`), it’s always safe to make either turn.
3. 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:

1. If we end up on a space, we’re done. Falling off the end of the line is our terminal condition.
2. If we end up on a letter, collect it.
3. If we end up on a plus, turn either left or right (either one will work) unless they represent a space.
4. 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!