Advent of Code 2024 - Day 6, in Kotlin - Guard Gallivant • Todd Ginsberg

Every year, Advent of Code has a few puzzles like this; traversing a maze or finding a path through a room. I really enjoy because they are so different from the code I normally write.

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

Puzzle Input

Today we’ll take our input as a List<String> and convert it to a List<CharArray> and store it as our grid. Why CharArray? Because in part 2 we’ll be mutating the grid and String doesn’t allow for this.

We will also search through the grid to find the start point, which we’ll represent as a Point2D. If you’ve read any of my Advent of Code posts from years past, you might recognize this. Eventually, I suspect this class will expand to have things like lists of neighbors and calculating distances between points. But for now, we just need to store x and y coordinates and add them together. We’ll also define some directional constants to make our life a bit easier.

// In Point2D.kt

data class Point2D(val x: Int, val y: Int) {

    operator fun plus(other: Point2D): Point2D =
        Point2D(x + other.x, y + other.y)

    companion object {
        val NORTH = Point2D(0, -1)
        val EAST = Point2D(1, 0)
        val SOUTH = Point2D(0, 1)
        val WEST = Point2D(-1, 0)
    }
}

In order to get our start point, we loop through all of the rows and columns to find the single instance of ^, and return it in a Point2D.

// In Day06

class Day06(input: List<String>) {

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

    private val start: Point2D = grid
        .flatMapIndexed { y, row ->
            row.mapIndexed { x, c ->
                if (c == '^') Point2D(x, y) else null
            }
        }.filterNotNull().first()
}

OK, enough setup, on to Part 1.

⭐ Day 6, Part 1

The puzzle text can be found here.

Alright, maybe just a bit more setup. First, we’ll need a way to get values out of our grid given a Point2D. We don’t want to do any kind of bounds checking, so we’ll return null when the Point2D represents a space outside the grid. We’ll define the get function as an operator on List<CharArray> (the type of our grid).

// In Day06

private operator fun List<CharArray>.get(at: Point2D): Char? =
    getOrNull(at.y)?.getOrNull(at.x)

We will implement both location and direction of travel with Point2D. The direction will be the changes to x and y so we can easily add direction to location to get a new location in the direction of travel. To make this easier, we’ll write a function to turn a given Point2D. When we hit an obstacle, we’re supposed to turn 90 degrees to the right. We could put this in Point2D but this doesn’t strike me as a reusable thing. Maybe I’m wrong, but let’s leave it here as a private extension function in the Day06 class for now.

// In Day06

private fun Point2D.turn(): Point2D =
    when (this) {
        Point2D.NORTH -> Point2D.EAST
        Point2D.EAST  -> Point2D.SOUTH
        Point2D.SOUTH -> Point2D.WEST
        Point2D.WEST  -> Point2D.NORTH
        else -> throw IllegalStateException("Bad direction: $this")
    }

Now we have everything we need to traverse the grid. First we will need to keep track of each place in the grid we have seen, which will be a MutableSet<Point2D>. We also need a mutable location and direction which we will initialize with the start point we calculated earlier and NORTH, respectively.

// In Day06

private fun traverse(): Int {
    val seen = mutableSetOf<Point2D>()
    var location = start
    var direction = Point2D.NORTH

    while (grid[location] != null ) {
        seen += location
        val next = location + direction

        if (grid[next] == '#') direction = direction.turn()
        else location = next
    }
    return seen.size
}

With the setup done, we want to march around the grid until we fall off. So we will set up a while loop that keeps going so long as location is within the grid. If it isn’t, we’ll get a null instead of some actual Char and we know we’ve fallen off the edge of the world.

Within the while loop, we add the current location to the seen set and calculate our next location by adding the current location to the current direction. This is where we can check if we’ve run into an obstacle. If the next place in the grid is a #, that means we need to turn, otherwise we can safely set the location to next and loop.

The while loop ends when we run off the edge, and the seen set is filled with points we’ve visited. Returning the size of the set gives us the length of the path.

We can solve Part 1 by calling traverse():

// In Day06

fun solvePart1(): Int = traverse()

Star earned! Onward!

⭐ Day 6, Part 2

The puzzle text can be found here.

To solve part 2, we’re going to need to refactor our traverse function to take into account location and direction. This way we can detect cycles. Because if the guard ends up in a location going in the same direction more than once, we know they’re in a cycle and won’t ever fall of the end of the grid. To do this, we’ll find the set of steps the guard takes without us interfering, add an obstacle to each of those spots, traverse the grid, and calculate how many of them are cycles.

Since we will be modifying the grid, we need to add another operator to make working with our List<CharArray> (the grid) easier. This time we need to set the given x/y coordinates (as a Point2D) to the given Char, c. We won’t do bounds checking on this one because know all of the points will be valid in this puzzle. In the “real world”, we’d probably want to do some kind of checking here.

// In Day06

private operator fun List<CharArray>.set(at: Point2D, c: Char) {
    this[at.y][at.x] = c
}

Now we can rewrite traverse to answer two questions:

What locations did the guard touch and
Was there a cycle, or did the guard fall off the grid?

Let’s look at the code and then we’ll go through it.

// In Day06

private fun traverse(): Pair<Set<Point2D>, Boolean> {
    val seen = mutableSetOf<Pair<Point2D, Point2D>>()
    var location = start
    var direction = Point2D.NORTH

    while (grid[location] != null && (location to direction) !in seen) {
        seen += location to direction
        val next = location + direction

        if (grid[next] == '#') direction = direction.turn()
        else location = next
    }
    return seen.map { it.first }.toSet() to (grid[location] != null)
}

In addition to a somewhat unwieldy return type, the only major change is accounting for direction. We modify seen to take a Pair<Point2D, Point2D> where the first element of the pair is the location and the second element of the pair is the direction of travel.

The while loop stays mostly the same except we also want to check that we have not seen this combination of location and direction yet. When we return from the traverse function, we want the set of points the guard has traversed (we aren’t interested in direction at all anymore), and whether the loop ended because of a cycle (non-null current location) or the guard walked off the grid (null current location).

With our newly refactored traverse() function, we can solve Part 2. We will do this by tracing the guard’s original path, and then run a traversal with an obstacle in each place the guard walks. If we count the number of times this results in a cycle, we’ll have our answer.

We’ll start by doing a normal traverse just like in Part 1 to calculate the guard’s path. Since traverse returns a Pair<Set<Point2D>, Boolean> now, we want the first element in the pair. We need to take care here not to put an obstacle right on top of the guard so we filter out the start.

Next, for each candidate place, we place our obstacle using our new set operator, run the traverse, taking care to reset the grid back to not having an obstacle (through the also function), and then pick out the second element of the pair, which tells us if there was a loop (true) or if the guard fell off the grid (false).

// In Day06

fun solvePart2(): Int =
    traverse()
        .first
        .filterNot { it == start }
        .count { candidate ->
            grid[candidate] = '#'
            traverse().also { grid[candidate] = '.' }.second
        }

To fix the now broken solvePart1() (because we changed the signature of traverse()), we need to pick out the first part of the pair (the set of points) and get its size.

// In Day06

fun solvePart1(): Int =
    traverse().first.size

Star earned! See you tomorrow!

Puzzle Input

⭐ Day 6, Part 1

⭐ Day 6, Part 2

Further Reading