Advent of Code 2024 - Day 4, in Kotlin - Ceres Search • Todd Ginsberg

Today, day 4, we encounter our first path traversal puzzle of the year (kinda). I enjoy puzzles like this because even though I’ve solved a lot of them over the years for AoC, they always make me think about how I really want to represent the grid and how to traverse it.

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

Puzzle Input

While it is tempting to parse our input into some kind of object structure, we’ll just leave it as a List<String> and work with it directly.

class Day04(private val input: List<String>) {

}

⭐ Day 4, Part 1

The puzzle text can be found here.

We’ll solve Part 1 by finding every X in the input and following every path away from it in eight directions to see how many of them spell XMAS. In order to do this, we will need to know how to move along each path in the x and y direction. The first thing we’ll do is create a reference list called ALL_DIRECTIONS which is a List<Pair<Int,Int>> where the pair represents the x and y changes to move in each direction.

We’ll define ALL_DIRECTIONS in the companion, and I’ve arranged the values visually so we can see which direction each Pair takes us.

// In Day04

private companion object {
    val ALL_DIRECTIONS = listOf(
        -1 to -1, -1 to 0, -1 to 1,
         0 to -1,           0 to 1,
         1 to -1,  1 to 0,  1 to 1
    )
}

Next, we want a way to get an x/y pair from the input without having to do a bunch of range checking. Let’s implement that logic as an extension function called safeAt on List<String>. If we’re asked for an out-of-range x or y, we can return a character we know we aren’t ever going to look for (like space, in this case).

// In Day04

private fun List<String>.safeAt(x: Int, y: Int): Char =
    if (y in indices && x in this[y].indices) this[y][x] else ' '

We also want to answer the question “If I follow the grid in a specific direction, does it spell a specific thing?”. We’ll call this concept vectorFind which takes a target (the thing we’re searching for), the x and y values we’re searching from, and a vector representing the amount to modify x and y when checking the grid for the next character.

// In Day04

private tailrec fun vectorFind(target: String, x: Int, y: Int, vector: Pair<Int, Int>): Boolean =
    when {
        target.isEmpty() -> true
        target.first() != input.safeAt(x, y) -> false
        else -> vectorFind(target.substring(1), x + vector.first, y + vector.second, vector)
    }

This is a recursive function, which means it is a function that calls itself. Moreover, it is a tail recursive function, which means the very last call it makes is to itself. While it doesn’t especially matter in this specific case (we’re not recursing that deep), marking a function with tailrec allows Kotlin to optimize these calls. If we were expecting a situation where we’d have a very deep call chain, we might need tailrec. In this case, it’s only here so I can point out that it’s a thing you might need at some point in the future.

The first thing to do in any recursive function is to check your end conditions. In this case, if the target has no more characters to search for, we’ve found our match! Similarly, if the first character of the target is not what is on the x/y spot in the input, we know we’ve not found our match.

Otherwise, we have found a character in the right place, in the right order, and may have more to check. So we remove the first character of the target, alter x by the vector, alter y by the vector, and recursively call vectorFind.

This will result in true when we’ve successfully found “XMAS” based at a certain point or false when we haven’t.

Now let’s write the solution to Part 1, using vectorFind:

// In Day04

fun solvePart1(): Int =
    input.flatMapIndexed { y, row ->
        row.mapIndexed { x, c ->
            if (c == 'X') {
                ALL_DIRECTIONS.count { vector ->
                    vectorFind("XMAS", x, y, vector)
                }
            } else 0
        }
    }.sum()

We see this pattern a lot in Advent of Code in order to go through every row and column in a List<String> or similar structure. An outer flatMapIndexed to get each y index and a row value, which we call mapIndexed on to get the x index and the value c at that x/y spot. We have to flat map the outer loop so we end up with a List<Int> (in this case) rather than a List<List<Int>>. Flatmap flattens the inner lists into a single list.

The guts of this function check to see if we’re looking at “X”, and then use our ALL_DIRECTIONS to count how many of the vectors starting at x and y spell “XMAS”. If we aren’t looking at “X” the answer is 0.

There is a handy sum() function on List<Int> (really on Iterable<Int>) that we can use to calculate the answer to Part 1.

Star earned! Onward!

⭐ Day 4, Part 2

The puzzle text can be found here.

If you think about it, there are only four valid ways to arrange MAS crossing into an X:

 1      2      3      4
---    ---    ---    ---
M M    M S    S S    S M
 A      A      A      A
S S    M S    M M    S M

Anything else is not valid. So instead of doing a vector search like in Part 1, we can find any instance of A and iterate the corners in a predictable order (NW, NE, SE, SW) and see if the resulting values are M and S in the right order (MMSS, MSSM, SSMM, and SMMS).

Let’s start by defining offsets for the CORNERS, which we will add to the companion object:

// In Day04.companion

val CORNERS = listOf(-1 to -1, -1 to 1, 1 to 1, 1 to -1)

Again, we want this order to be predictable, so we’ll put them in a list and arrange them from NorthWest to NorthEast to SouthEast to SouthWest.

Next, we’ll go through the input to find any instance of A, safely grab all of the values to its corners, and join them together into Strings. If the resulting String is something we’re looking for, we’ve found an X-MAS!

// In Day04

fun solvePart2(): Int =
    input.flatMapIndexed { y, row ->
        row.mapIndexed { x, c ->
            if (c == 'A') {
                CORNERS
                    .map { (dx, dy) -> input.safeAt(x + dx, y + dy) }
                    .joinToString("") in setOf("MMSS", "MSSM", "SSMM", "SMMS")
            } else false
        }
    }.count { it }

This structure should look similar to the solution we developed for Part 1. The difference being instead of seeing how many XMAS we’ve got starting at a given X, we want to know if the given A is the center of an X-MAS. So we’re ultimately creating a List<Boolean> and then using count to figure out how many are true.

As in Part 1, we go through all of the rows and columns of the input. The inner part of the loop first determines if we’re looking at an A. If so, we get all of the values from the CORNERS (using safeAt so we don’t have to worry about range checks), joinToString the individual values, and then compare them to see if we’ve found one of the four valid arrangements.

Running this solves Part 2.

Star earned! See you tomorrow!

Puzzle Input

⭐ Day 4, Part 1

⭐ Day 4, Part 2

Further Reading