Advent of Code 2024 - Day 18, in Kotlin - RAM Run • Todd Ginsberg

Another maze puzzle! I love these. We’ll solve Part 1 with yet another Breadth-First search, and write our own binary search function to solve Part 2.

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

Puzzle Input

We will take our input in as a List<String> and turn it into a List<Point2D> objects to represent the bytes. We won’t generate a grid, we’ll just store the places we can’t go.

class Day18(input: List<String>) {

    private val bytes: List<Point2D> = input.map { Point2D.of(it) }

}

I can’t believe we haven’t had to convert a String to a Point2D yet! Let’s fix that by adding a of function to our existing Point2D companion object.

// In Point2D Companion Object

fun of(input: String): Point2D =
    input.split(",").let {
        Point2D(it.first().toInt(), it.last().toInt())
    }

⭐ Day 18, Part 1

The puzzle text can be found here.

First, let’s add an extension function private to Day18 on Point2D to figure out if a given Point2D is in the range.

// In Day18

private fun Point2D.inRange(end: Point2D): Boolean =
    x in 0..end.x && y in 0..end.y

In order to work ourselves through the maze, we’ll use another Depth-First search. The queue stores the location and cost to get there, and we record the set of Point2D places we’ve seen. This traverse function returns an Int? to cover the case where there may not be a path through the maze (we will need this for Part 2).

// In Day18

private fun traverse(end: Point2D, barriers: Set<Point2D>): Int? {
    val queue = mutableListOf(Point2D.ORIGIN to 0)
    val seen = mutableSetOf<Point2D>()

    while (queue.isNotEmpty()) {
        val (place, cost) = queue.removeFirst()

        if (place == end) return cost
        else if (seen.add(place)) {
            place.cardinalNeighbors()
                .filter { it.inRange(end) }
                .filterNot { it in barriers }
                .forEach { queue.add(it to cost + 1) }
        }
    }
    return null
}

This should look very familiar - while there is work to do, examine spots we haven’t seen before. Add any neighbors that we could move to at a cost + 1.

Calling traverse solves Part 1. The solvePart1 function takes in the range of the maze and the number of fallingBytes as the values of these changes between the example data and the actual data.

// In Day18

fun solvePart1(range: Point2D, fallingBytes: Int): Int =
    traverse(range, bytes.take(fallingBytes).toSet()) 
        ?: throw IllegalStateException()

Star earned! Onward!

⭐ Day 18, Part 2

The puzzle text can be found here.

We can do Part 2 by running the traverse function with increasing number of bytes until one of them returns null (no path through the maze). On my machine this finishes in just under 3 seconds. Not terrible, but we can do better.

What we’ll do is perform a binary search over the list of bytes, finding the first one that returns null. We’ll add this to our Extensions.kt file as it will be generally useful.

// In Extensions.kt

fun <T> List<T>.binarySearchIndexOfFirstOrNull(fn: (T) -> Boolean): Int? {
    var low = 0
    var high = lastIndex
    var firstFind: Int? = null
    while (low <= high) {
        val mid = (low + high) shr 1
        if (fn(get(mid))) {
            firstFind = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return firstFind
}

This binary search differs from most binary searches you’ve probably seen because it finds the first instance that passes the predicate (fn). If we don’t find a valid value, we return null.

Once we can do a binary search that returns the index or null, we can add some additional functions to make life easier.

I fully realize these names are somewhat long, but I am a) trying to be descriptive (“binary search”) and b) follow the naming standard already in the Kotlin Standard Library.

// In Extensions.kt

fun <T> List<T>.binarySearchFirst(fn: (T) -> Boolean): T =
    binarySearchFirstOrNull(fn) ?: 
        throw IllegalStateException("No elements match predicate")

fun <T> List<T>.binarySearchFirstOrNull(fn: (T) -> Boolean): T? =
    binarySearchIndexOfFirstOrNull(fn)?.let { get(it) }

fun <T> List<T>.binarySearchIndexOfFirst(fn: (T) -> Boolean): Int =
    binarySearchIndexOfFirstOrNull(fn) ?: 
        throw IllegalStateException("No elements match predicate")

Now that we can do a binary search, we’ll use it to traverse with varying number of bytes until we find the first byte that causes us to not have a path through the maze. Because we want both the value of the location and the index, we’ll use withIndex() from the Kotlin Standard Library.

// In Day18

fun solvePart2(range: Point2D): String =
    bytes
        .withIndex()
        .toList()
        .binarySearchFirst { (index, _) ->
            traverse(range, bytes.take(index + 1).toSet()) == null
        }.let { (_, value) ->
            "${value.x},${value.y}"
        }

We give binarySearchFirst a function call to traverse with a variable number of bytes to take, returning the first one that results in a null (no path through the maze). We use let to convert the Point2D we’ve found to a properly formatted String.

Star earned! See you tomorrow!

Puzzle Input

⭐ Day 18, Part 1

⭐ Day 18, Part 2

Further Reading