Advent of Code 2023 - Day 16, in Kotlin - The Floor Will Be Lava • Todd Ginsberg

This was a fun puzzle for a Saturday morning. We’ll write up a quick breadth-first algorithm to get our answer, and reuse several of the extension functions we’ve already written to make working with grids easier.

If you’d rather just view the code, my GitHub Repository is here.

Puzzle Input

Today our input comes to us as a List<String>, which we map into an Array<CharArray> as a grid. Honestly, because we don’t actually mutate the grid this time, I’d probably have just left it as a List<String> if I hadn’t already written several helper functions that were typed specifically for Array<CharArray>. I guess that’s a good lesson for me to stop and think about types before I throw things into the extension file.


class Day16(input: List<String>) {

    private val grid: Array<CharArray> =
        input.map { it.toCharArray() }.toTypedArray()

}

⭐ Day 16, Part 1

The puzzle text can be found here.

If you read over the rules for what to do when we run into a specific symbol, they basically come in three flavors:

Do nothing (keep going in the direction you are going)
Pick a single new direction
Pick two new directions

Also, as the beam makes its way though the grid the important thing to record isn’t just the location of the beam, but also the direction it is moving.

So let’s take these facts and encode a table of allowed movements. We assume anything that isn’t in the map falls into category 1 (keep going in the current direction). Do note that \ is the escape character in Kotlin, so we have to write it as \\ to escape it.

// In Day16

private val movements = mapOf(
    '-' to NORTH to listOf(EAST, WEST),
    '-' to SOUTH to listOf(EAST, WEST),
    '|' to EAST to listOf(NORTH, SOUTH),
    '|' to WEST to listOf(NORTH, SOUTH),
    '\\' to NORTH to listOf(WEST),
    '\\' to WEST to listOf(NORTH),
    '\\' to SOUTH to listOf(EAST),
    '\\' to EAST to listOf(SOUTH),
    '/' to NORTH to listOf(EAST),
    '/' to WEST to listOf(SOUTH),
    '/' to SOUTH to listOf(WEST),
    '/' to EAST to listOf(NORTH)
)

This might be a bit confusing with all the to calls in there. The key to the map is a Pair<Char, Point2D> where the Char represents what the spot in the grid is, and the Point2D represents the direction we’re moving. Remember, we have NORTH/SOUTH/EAST/WEST offsets defined in Point2D already. The value of the map is a List<Point2D> which represents the new directions that the beam can take. In most cases, these are singleton lists, but in four of them the beam splits.

Next we’ll write a function to have the beam traverse the grid until it fully loops back on itself.

// In Day16

private fun energize(startPoint: Point2D, startDirection: Point2D): Int {
    val seen = mutableSetOf(startPoint to startDirection)
    val queue = ArrayDeque<Pair<Point2D, Point2D>>().apply {
        add(startPoint to startDirection)
    }
    while (queue.isNotEmpty()) {
        val (place, direction) = queue.removeFirst()
        val nextDirections = movements[grid[place] to direction] ?: listOf(direction)
        nextDirections.forEach { nextDirection ->
            val nextPlace = place + nextDirection
            val nextPair = nextPlace to nextDirection
            if (nextPair !in seen && grid.isSafe(nextPlace)) {
                queue.add(nextPair)
                seen += nextPair
            }
        }
    }

    return seen.map { it.first }.toSet().size
}

If you’ve followed my solutions, this should look familiar. First, we define a seen set to capture states we’ve already experienced. We use this to cut down on the amount of work we have to do and to detect when we’ve looped around. For example, if we’re on spot 0,0 coming from the SOUTH, and we’ve been in the same place moving the same direction before, there can be no other outcome to doing it a second time, so we can stop working. The queue is there to hold the work we haven’t done yet but know we need to do. For example, if we run into a splitter we will need to add two work items to the queue. In some implementations of this algorithm we care about the order of the items in the queue (in which case we’d possibly opt for PriorityQueue over ArrayDeque) but in this case we don’t. We use ArrayDeque because we can easily add to one and and remove from the other.

Once the work queue has been set up and initialized with the startPoint and startDirection, we loop until the queue is empty. For each work item we remove from the queue via removeFirst, we use destructuring to turn the returned Pair<Point2D, Point2D> into place and direction. We use this information to figure out where we are on the grid and what character we’re looking at and use that to look up our next move in the movements map. If the movements map doesn’t have an answer for us, we assume “keep going” is acceptable and return listOf(direction).

Next, we calculate where we move to given the nextDirection, for each of the directions returned from movements. We add that direction to the current place to figure out where to go next. The only checks we need to make are to check if we’ve seen that state before, and to make sure the nextPlace is in the grid, using the isSafe function we wrote a few days ago. Assuming those checks pass, we add the nextPair to the work queue and the seen set.

At the end of the energize function we find all of the unique places we’ve seen and return the count.

// In Day16

fun solvePart1(): Int =
    energize(Point2D(0, 0), EAST)

Calling energize indicating we start from the top left corner moving EAST solves par 1 of the puzzle.

Star earned! Onward!

⭐ Day 16, Part 2

The puzzle text can be found here.

My strategy for part 2 is to call what we wrote for part 1 for every spot along the outside of the grid. Maybe there’s a better way to do this, but this works fast enough and I’m only running this code once to get an answer for a puzzle.

So let’s generate our data.

// In Day16

fun solvePart2(): Int =
    listOf(
        grid.first().indices.map { Point2D(it, 0) to SOUTH },
        grid.first().indices.map { Point2D(it, grid.lastIndex) to NORTH },
        grid.indices.map { Point2D(0, it) to EAST },
        grid.indices.map { Point2D(grid.first().lastIndex, it) to WEST }
    )
        .flatten()
        .maxOf { energize(it.first, it.second) }

The outer listOf will eventually create a List<List<Pair<Point2D, Point2D>> where the Pair represents a starting point and a direction. We don’t really want this structure though, so we flatten it into a single List<Pair<Point2D, Point2D>> which lets us call maxOf with energize.

Inside the listOf we loop through all of the indices in the x and y directions and set the direction to how we’ll come into the grid. For example the first list is created by going through all of the x indices and assuming y is 0. Since that means we come from the top of the grid, we’ll be moving SOUTH. I will note that I love that Kotlin defines lastIndex so we don’t have to do something like length() -1. For symmetry there is also firstIndex but since it is 0 in these cases, I didn’t use it because it makes the code look busier than it needs to be.

Running this function gives us the answer to part 2!

Star earned! See you tomorrow!

⭐ Day 16, Part 1

⭐ Day 16, Part 2

Further Reading