Skip to Content

Advent of Code 2018 - Day 13, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 13: 'Mine Cart Madness'

Posted on

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

A crop of this size requires significant logistics to transport produce, soil, fertilizer, and so on. The Elves are very busy pushing things around in carts on some kind of rudimentary system of tracks they’ve come up with.

Seeing as how cart-and-track systems don’t appear in recorded history for another 1000 years, the Elves seem to be making this up as they go along. They haven’t even figured out how to avoid collisions yet.

You map out the tracks (your puzzle input) and see where you can help.

Tracks consist of straight paths (| and -), curves (/ and \), and intersections (+). Curves connect exactly two perpendicular pieces of track; for example, this is a closed loop:

/----\
|    |
|    |
\----/

Intersections occur when two perpendicular paths cross. At an intersection, a cart is capable of turning left, turning right, or continuing straight. Here are two loops connected by two intersections:

/-----\
|     |
|  /--+--\
|  |  |  |
\--+--/  |
   |     |
   \-----/

Several carts are also on the tracks. Carts always face either up (^), down (v), left (<), or right (>). (On your initial map, the track under each cart is a straight path matching the direction the cart is facing.)

Each time a cart has the option to turn (by arriving at any intersection), it turns left the first time, goes straight the second time, turns right the third time, and then repeats those directions starting again with left the fourth time, straight the fifth time, and so on. This process is independent of the particular intersection at which the cart has arrived - that is, the cart has no per-intersection memory.

Carts all move at the same speed; they take turns moving a single step at a time. They do this based on their current location: carts on the top row move first (acting from left to right), then carts on the second row move (again from left to right), then carts on the third row, and so on. Once each cart has moved one step, the process repeats; each of these loops is called a tick.

For example, suppose there are two carts on a straight track:

|  |  |  |  |
v  |  |  |  |
|  v  v  |  |
|  |  |  v  X
|  |  ^  ^  |
^  ^  |  |  |
|  |  |  |  |

First, the top cart moves. It is facing down (v), so it moves down one square. Second, the bottom cart moves. It is facing up (^), so it moves up one square. Because all carts have moved, the first tick ends. Then, the process repeats, starting with the first cart. The first cart moves down, then the second cart moves up - right into the first cart, colliding with it! (The location of the crash is marked with an X.) This ends the second and last tick.

Here is a longer example:

/->-\        
|   |  /----\
| /-+--+-\  |
| | |  | v  |
\-+-/  \-+--/
  \------/   

/-->\        
|   |  /----\
| /-+--+-\  |
| | |  | |  |
\-+-/  \->--/
  \------/   

/---v        
|   |  /----\
| /-+--+-\  |
| | |  | |  |
\-+-/  \-+>-/
  \------/   

/---\        
|   v  /----\
| /-+--+-\  |
| | |  | |  |
\-+-/  \-+->/
  \------/   

/---\        
|   |  /----\
| /->--+-\  |
| | |  | |  |
\-+-/  \-+--^
  \------/   

/---\        
|   |  /----\
| /-+>-+-\  |
| | |  | |  ^
\-+-/  \-+--/
  \------/   

/---\        
|   |  /----\
| /-+->+-\  ^
| | |  | |  |
\-+-/  \-+--/
  \------/   

/---\        
|   |  /----<
| /-+-->-\  |
| | |  | |  |
\-+-/  \-+--/
  \------/   

/---\        
|   |  /---<\
| /-+--+>\  |
| | |  | |  |
\-+-/  \-+--/
  \------/   

/---\        
|   |  /--<-\
| /-+--+-v  |
| | |  | |  |
\-+-/  \-+--/
  \------/   

/---\        
|   |  /-<--\
| /-+--+-\  |
| | |  | v  |
\-+-/  \-+--/
  \------/   

/---\        
|   |  /<---\
| /-+--+-\  |
| | |  | |  |
\-+-/  \-<--/
  \------/   

/---\        
|   |  v----\
| /-+--+-\  |
| | |  | |  |
\-+-/  \<+--/
  \------/   

/---\        
|   |  /----\
| /-+--v-\  |
| | |  | |  |
\-+-/  ^-+--/
  \------/   

/---\        
|   |  /----\
| /-+--+-\  |
| | |  X |  |
\-+-/  \-+--/
  \------/   

After following their respective paths for a while, the carts eventually crash. To help prevent crashes, you’d like to know the location of the first crash.Locations are given in X,Y coordinates, where the furthest left column is X=0 and the furthest top row is Y=0:

           111
 0123456789012
0/---\        
1|   |  /----\
2| /-+--+-\  |
3| | |  X |  |
4\-+-/  \-+--/
5  \------/   

In this example, the location of the first crash is 7,3.

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

There isn’t much you can do to prevent crashes in this ridiculous system. However, by predicting the crashes, the Elves know where to be in advance and instantly remove the two crashing carts the moment any crash occurs.

They can proceed like this for a while, but eventually, they’re going to run out of carts. It could be useful to figure out where the last cart that hasn’t crashed will end up.

For example:

/>-<\  
|   |  
| /<+-\
| | | v
\>+</ |
  |   ^
  \<->/

/---\  
|   |  
| v-+-\
| | | |
\-+-/ |
  |   |
  ^---^

/---\  
|   |  
| /-+-\
| v | |
\-+-/ |
  ^   ^
  \---/

/---\  
|   |  
| /-+-\
| | | |
\-+-/ ^
  |   |
  \---/

After four very expensive crashes, a tick ends with only one cart remaining; its final location is 6,4.

What is the location of the last cart at the end of the first tick where it is the only cart left?

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!

Further Reading

  1. Index of All Solutions - All solutions for 2018, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 13
  4. Advent of Code - Come join in and do these challenges yourself!