Advent of Code 2018 - Day 13, in Kotlin • Todd Ginsberg

Get ready to use a lot of mutable data structures for this one. We’ll explore some sealed classes, use one of my favorite Kotlin patterns, and write another sequence.

Problem Input

It’s a bunch of ASCII tracks! We’ll largely consume it as-is, and save picking the carts out for part 1. So check below for the implementation of Cart.findAll().

typealias Track = Array<CharArray>

class Day13(rawInput: List<String>) {

    private val track: Track = rawInput.map { it.toCharArray() }.toTypedArray()
    private val carts: Set<Cart> = Cart.findAll(track)

}

I’ve decided to typealias our Track because it just I find Array<CharArray> hard to read, and why not because that feature comes for free.

⭐ Day 13, Part 1

The puzzle text can be found here.

I know that’s a lot. Let me first just say that even though we’re asked to give the first crash site, we are going to write a sequence to generate them all. It’s not much more work and I have a feeling that it will come in handy later.

Directions and Turning

Before we get into defining our Cart, let’s define sealed class structures for turning and direction. Turn will be used to keep track of which type of turn to make when we reach a + interchange.

private sealed class Turn {
    abstract val next: Turn

    object Left : Turn() {
        override val next = Center
    }

    object Center : Turn() {
        override val next = Right
    }

    object Right : Turn() {
        override val next = Left
    }
}

We have to define our Turn sealed class as opposed to an enum because they all reference each other. We can’t just define next in the constructor of Turn or else we’ll get circular references and end up with nulls where we shouldn’t actually have them (go try it!). So we have to override our var in each subclass.

Direction works similarly, and tracks the change in x and y (dx, dy), and what left and right mean in the given context. As a bonus, it makes use of one of my favorite Kotlin patterns!

private sealed class Direction {

    companion object {
        operator fun invoke(id: Char): Direction =
            when (id) {
                '^' -> North
                'v' -> South
                '>' -> East
                '<' -> West
                else -> throw IllegalArgumentException("No such direction $id")
            }
    }

    abstract val left: Direction
    abstract val right: Direction
    abstract val dx: Int
    abstract val dy: Int

    fun turn(turn: Turn): Direction =
        when (turn) {
            Turn.Left -> this.left
            Turn.Center -> this
            Turn.Right -> this.right
        }

    object North : Direction() {
        override val left = West
        override val right = East
        override val dx = 0
        override val dy = -1
    }

    object South : Direction() {
        override val left = East
        override val right = West
        override val dx = 0
        override val dy = 1
    }

    object East : Direction() {
        override val left = North
        override val right = South
        override val dx = 1
        override val dy = 0
    }

    object West : Direction() {
        override val left = South
        override val right = North
        override val dx = -1
        override val dy = 0
    }
}

I really like overriding invoke in the companion of sealed classes. This lets us treat the top level class like it’s the only class, and we don’t really have to know about each implementation. Think of it like a factory that’s disguised as a constructor!

Cart

Now that we can move in a specific Direction and Turn relative to that direction, let’s design a class for our cart data. We need to know where it is, what direction it is pointed in, what direction it will turn next, and if it is alive. We’re specifically tracking it’s liveness because I don’t want to write a bunch of code to manage concurrent access to our set of carts. I just find that more confusing, and since we’ll be modifying other aspects of the Cart, why not just add this too?

private data class Cart(var x: Int, var y: Int,
                   var direction: Direction, var turn: Turn = Turn.Left,
                   var alive: Boolean = true) : Comparable<Cart> {

   override fun compareTo(other: Cart): Int =
        when {
            x < other.x -> -1
            x > other.x -> 1
            y < other.y -> -1
            y > other.y -> 1
            else -> 0
        }                   	

}

The first thing we will do is implement Comparable<Cart>, so we can sort them into an order. The instructions, tell us to go from top left to bottom right when picking carts, and that’s what our compareTo function does.

Next, we’ll need to pick all of our Carts out given a Track. To do that, we’ll define a findAll on the companion of Cart that will loop through the entire Track and pick out the input. You might wonder why we don’t replace the cart symbols in the Track with track symbols (- or |). We’re going to leave them as-is because we can just treat them as if they weren’t there. Carts are always on a straight piece of rail to start, and we only ever need to make a decision when turning, so we can ignore these symbols.

Our Cart factory:

// In Cart

companion object {
    fun findAll(theTrack: Track): Set<Cart> =
        theTrack.mapIndexed { y, row ->
            row.mapIndexed { x, spot ->
                if (spot in setOf('>', '<', '^', 'v')) {
                    Cart(x, y, Direction(spot))
                } else null
            }
        }
            .flatten()
            .filterNotNull()
            .toCollection(TreeSet())
}

Another thing Cart needs to do is figure out if it collides with another Cart. It does so if they are both alive, reference different Carts, and are in the same place.

// In Cart

fun collidesWith(other: Cart): Boolean =
    this != other && this.alive && other.alive && x == other.x && y == other.y

Movement of the cart in a given turn is the last thing we need to concentrate on, and it is the most complicated part of the Cart:

// In Cart
fun move(track: Track) {
    // Move in the direction we are facing
    x += direction.dx
    y += direction.dy

    // Handle turning, anything else is movement in the same direction the next time through.
    when (track[y][x]) {
        // Interchange rules
        '+' -> {
            direction = direction.turn(turn)
            turn = turn.next
        }
        // Turn
        '\\' -> {
            direction = when (direction) {
                Direction.North, Direction.South -> direction.left
                else -> direction.right
            }
        }
        // Turn
        '/' -> {
            direction = when (direction) {
                Direction.East, Direction.West -> direction.left
                else -> direction.right
            }
        }
    }
}

In this we move first by applying the delta x and y from our current Direction. Then we handle each special case of track we might have just moved over. In the case of +, we turn by asking direction where to go next, and increment our turn variable to the next instruction (because we cycle through Left, Center, Right). If we handle an \, we figure out what direction we are facing and turn left or right as is appropriate. The same calculation is done for /.

Colliding Carts

Now we’re finally ready to mash some carts together! We’ll do this with a sequence that gives us each of the crash sites as a Point that we defined a few days ago.

private fun collisions(): Sequence<Point> = sequence {
    while (carts.count { it.alive } > 1) {
        carts.sorted().forEach { cart ->
            if (cart.alive) {
                cart.move(track)

                // If we collided, mark ourselves and the cart we collided with as not alive
                // yield the crash site.
                carts.firstOrNull { cart.collidesWith(it) }?.let { otherCart ->
                    cart.alive = false
                    otherCart.alive = false
                    yield(Point(cart.x, cart.y))
                }
            }
        }

What this does is keep yielding crash sites until either all the carts are gone or only one is left. We have to check that a cart is alive before attempting to move it because it could have been collided with in a past iteration. Once a cart is moved, we pick through the entire list of carts for the one possible cart it may have collided with. If it did, we’ll have a non-null reference to another Cart here and we can use let to add some logic. We mark both carts as no longer being alive, and we yield the crash site.

Again, we could dispense with the alive flag if we were willing to deal with a different approach to this, or have a concurrent data structure. But I find this easy to follow, and there just aren’t that many carts so I’m willing to give up the extra performance of having to ignore dead carts in exchange for clarity.

Actually Solving the Problem

Now that we have all of that, we just need the first crash site from the sequence and we’re done!

fun solvePart1(): Point =
    collisions().first()

Be careful when entering your coordinates, Advent of Code doesn’t like spaces between the numbers and the comma.

With that star we are now 50% of the way though with Advent of Code 2018!

⭐ Day 13, Part 2

The puzzle text can be found here.

What if we were to go exhaust our entire collisions sequence, and find the location of the one remaining cart? That would solve part 2. Good thing we wrote so much code in part 1, it makes part 2 pretty short! We consume the entire collisions sequence and then go find the one cart we have left alive (wow this place sounds violent), and return its location as a Point:

fun solvePart2(): Point {
    collisions().toList() // Consume the entire sequence
    return carts.first { it.alive }.run { Point(this.x, this.y) }
}

Star earned!

⭐ Day 13, Part 1

⭐ Day 13, Part 2

Further Reading