Skip to Content

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

Somehow, a network packet got lost and ended up here. It’s trying to follow a routing diagram (your puzzle input), but it’s confused about where to go.

Its starting point is just off the top of the diagram. Lines (drawn with |, -, and +) show the path it needs to take, starting by going down onto the only line connected to the top of the diagram. It needs to follow this path until it reaches the end (located somewhere within the diagram) and stop there.

Sometimes, the lines cross over each other; in these cases, it needs to continue going the same direction, and only turn left or right when there’s no other option. In addition, someone has left letters on the line; these also don’t change its direction, but it can use them to keep track of where it’s been. For example:

     |          
     |  +--+    
     A  |  C    
 F---|----E|--+ 
     |  |  |  D 
     +B-+  +--+ 

Given this diagram, the packet needs to take the following path:

  • Starting at the only line touching the top of the diagram, it must go down, pass through A, and continue onward to the first +.
  • Travel right, up, and right, passing through B in the process.
  • Continue down (collecting C), right, and up (collecting D).
  • Finally, go all the way left through E and stopping at F.
  • Following the path to the end, the letters it sees on its path are ABCDEF.

The little packet looks up at you, hoping you can help it find the way. What letters will it see (in the order it would see them) if it follows the path? (The routing diagram is very wide; make sure you view it without line wrapping.)

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 packet is curious how many steps it needs to go.

For example, using the same routing diagram from the example above…

     |          
     |  +--+    
     A  |  C    
 F---|--|-E---+ 
     |  |  |  D 
     +B-+  +--+ 

…the packet would go:

  • 6 steps down (including the first line at the top of the diagram).
  • 3 steps right.
  • 4 steps up.
  • 3 steps right.
  • 4 steps down.
  • 3 steps right.
  • 2 steps up.
  • 13 steps left (including the F it stops on).

This would result in a total of 38 steps.

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!

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 19.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - I Walk The Line, by Johnny Cash.