Advent of Code 2024 - Day 15, in Kotlin - Warehouse Woes • Todd Ginsberg

A nice puzzle for a lazy Sunday. I got part 1 pretty quickly, using a method I don’t actually show in this post. After I implemented part 2, I realized I could make some slight changes and it would work for part 1 as well!

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 parse it into two values: A warehouse which represents the map as a List<CharArray>, and the ordered movements we need to make, as a List<Point2D>, where the Point2D objects represent offsets.

class Day15(input: List<String>) {

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

    private val movements: List<Point2D> = input
        .dropWhile { it.isNotEmpty() }
        .dropWhile { it.isEmpty() }
        .flatMap { row ->
            row.map { it.toDirection() }
        }
}

Because the input is in two parts, we need to separate them using takeWhile and dropWhile. Creating the warehouse involves turning each String into a CharArray (so we can mutate it later), while the movements require mapping Char to Point2D. We’ll do that via a toDirection() function on Char.

// In Day15

private fun Char.toDirection(): Point2D =
    when (this) {
        '^' -> Point2D.NORTH
        '>' -> Point2D.EAST
        'v' -> Point2D.SOUTH
        '<' -> Point2D.WEST
        else -> throw IllegalArgumentException("Invalid direction: $this")
    }

⭐ Day 15, Part 1

The puzzle text can be found here.

Strategy

When I originally solved Part 1, I implemented a strategy that only worked for Part 1. Namely, if I run into a box (“O”), search along the direction of travel until we find an empty place and then swap the box with the empty place. If we run into a wall, we can’t push this box. This prevents us from having to shift multiple identical and completely fungible boxes, we just need to swap the ends.

What we’ll do instead is implement an algorithm that works for both parts of today’s puzzle. We will do it for part 1 and them make a slight refactoring for part 2.

Our strategy for Part 1 and 2 will be to implement a Breadth-First search that does one of two things: Returns null when we can’t push a box (because a wall is in the way), or returns a List<Pair<Point2D,Point2D>>, with each pair of points representing a from position and a destination position that is valid. So either we get a list of valid box pushing instructions or we get nothing. We will implement this one way for Part 1 and then make some slight changes for Part 2.

OK, let’s get started with some helper functions. These allow us to get and set values in the warehouse by some Point2D more easily. We will define them in an Extensions.kt file because these are probably useful generally.

// In Extensions.kt

operator fun List<CharArray>.get(at: Point2D): Char =
    this[at.y][at.x]

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

And this function calculates the gps of a given Point2D:

// In Day15

private fun Point2D.gps(): Int =
    (100 * y) + x

Our final helper function finds all of some target in the warehouse. We’ll use this a few times.

// In Day15

private fun List<CharArray>.findAll(target: Char): List<Point2D> =
    flatMapIndexed { y, row ->
        row.mapIndexed { x, c ->
            if (c == target) Point2D(x, y) else null
        }
    }.filterNotNull()

OK, housekeeping done. Let’s implement the core of our algorithm - the function to push starting at a given position in a specific direction. This function will do one of two things:

Return null if we can’t push this chain of boxes because a wall prevents it
Return a set of movements that need to be made to satisfy the initial request of pushing from a position in a direction.

Let’s look at it, and then I’ll explain it.

// In Day15

private fun List<CharArray>.push(
    position: Point2D,
    direction: Point2D
): List<Pair<Point2D, Point2D>>? {
    val safePushes = mutableListOf<Pair<Point2D, Point2D>>()
    val queue = mutableListOf(position)

    while (queue.isNotEmpty()) {
        val thisPosition = queue.removeFirst()
        val nextPosition = thisPosition + direction
        when (get(nextPosition)) {
            '#' -> return null // Wall! Can't push anything!
            'O' -> queue.add(nextPosition)
        }
        safePushes.add(thisPosition to nextPosition)
    }
    return safePushes.reversed()
}

This is a Breadth-First search. We will create a queue to hold the in-order list of Point2D objects we want to examine. We also create a list of safePushes to hold the from/to pairing of places that make up the instructions. We’ll calculate this value as we go.

While the queue has some work, we look at thisPosition (the first element in the queue) and add the direction to it to calculate the nextPosition. There are two things that can happen next. If the nextPosition represents a wall ("#"), that means the push function has determined that a wall blocks us from pushing anything, so we return null. Otherwise, if we’re looking at a crate (“O”), we want to see if that position can push in the direction, so we add it to the queue.

Because we haven’t returned from the function, we can speculatively determine that moving a crate from thisPosition to nextPosition is safe.

At the end, when we’ve run out of work to do and have not exited early because of a wall, we return the reversed list of safePushes. We reverse to make the movements happen farthest to nearest, so we don’t overwrite things we intend to push but haven’t.

Next, let’s implement the loop to move through the warehouse, we’ll call this doMovements:

// In Day15

private fun List<CharArray>.doMovements(): List<CharArray> {
    val start: Point2D = findAll('@').first()
    var place = start
    movements.forEach { direction ->
        val next = place + direction
        when(this[next]) {
            in "O" -> {
                push(next, direction)?.let { moves ->
                    moves.forEach { (from, to) ->
                        this[to] = this[from]
                        this[from] = '.'
                    }
                    place = next
                }
            }
            !in "#" -> {
                place = next
            }
        }
    }
    return this
}

First, we need to find the start position, which we will use findAll and first to accomplish. Why not just calculate the starting position when we create the warehouse and the movements? Because Part 2 changes it slightly, so we will find it fresh each time.

Next, we set aside our place as a mutable variable, starting with start.

Finally, we look at each of the movements and see if we need to push some crates or not. Note I had originally written this as a fold but it was super confusing so I turned it into a forEach, which I think is more simple.

Within the work loop, we determine the next place we want to go by adding the direction to the current place. We then look at that next place and if there is a crate, we call our push function to find either a list of instructions, or null. Assuming we find some instructions, we go through each of the moves and do them. This involves moving from to to, and then putting an empty space in the now empty from. At the end, we set the current place to next because we’re allowed to move there.

If instead we find anything other than a wall ("#"), we move there. Incidentally, this allows us to ignore the @ symbol entirely. We never end up using it, and we don’t really care if we move boxes over it because we track our location with a variable that we end up not caring about when we’re done moving things around. I suppose it really only gets in the way if you’re printing the warehouse to debug.

To keep up a fluid API, we return this, the warehouse.

All that’s left is to do the movements, find all of the crates, and get the sumOf their gps values!

// In Day15

fun solvePart1(): Int =
    warehouse
        .doMovements()
        .findAll('O')
        .sumOf { it.gps() }

Star earned! Onward!

⭐ Day 15, Part 2

The puzzle text can be found here.

We’re actually really close to a solution, thanks to all the work we did in part 1. Let’s tackle expanding the warehouse first. This remap function does the work of turning our CharArray into a CharArray that is two times as wide, with help from joinToString.

// In Day15

private fun CharArray.remap(): CharArray =
    joinToString("") {
        when (it) {
            '#' -> "##"
            'O' -> "[]"
            '.' -> ".."
            '@' -> "@."
            else -> throw IllegalArgumentException("Invalid $it")
        }
    }.toCharArray()

Let’s make some edits to doMovements. The only thing we need to change here is to alter what constitutes a box. In part 1, this is “O”, but in part 2, this is “[” or “]”. We can look for all three safely.

// In Day15

private fun List<CharArray>.doMovements(): List<CharArray> {
    val start: Point2D = findAll('@').first()
    var place = start
    movements.forEach { direction ->
        val next = place + direction
        when(this[next]) {
            in "[O]" -> {
                push(next, direction)?.let { moves ->
                    moves.forEach { (from, to) ->
                        this[to] = this[from]
                        this[from] = '.'
                        place = next
                    }
                }
            }
            !in "#" -> {
                place = next
            }
        }
    }
    return this
}

I’ve highlighted the line that changes, all other lines stay the same.

Next, let’s make a corresponding change to push. It’s a bit more code, and I’ll explain the theory in a moment.

// In Day15

private fun List<CharArray>.push(
    position: Point2D,
    direction: Point2D
): List<Pair<Point2D, Point2D>>? {
    val safePushes = mutableListOf<Pair<Point2D, Point2D>>()
    val queue = mutableListOf(position)
    val seen = mutableSetOf<Point2D>()

    while (queue.isNotEmpty()) {
        val thisPosition = queue.removeFirst()
        if (thisPosition !in seen) {
            seen += thisPosition
            if (direction in setOf(Point2D.NORTH, Point2D.SOUTH)) {
                when (get(thisPosition)) {
                    ']' -> queue.add(thisPosition + Point2D.WEST)
                    '[' -> queue.add(thisPosition + Point2D.EAST)
                }
            }
            val nextPosition = thisPosition + direction
            when (get(nextPosition)) {
                '#' -> return null // Wall! Can't push anything!
                in "[O]" -> queue.add(nextPosition)
            }
            safePushes.add(thisPosition to nextPosition)
        }
    }
    return safePushes.reversed()
}

The first thing to notice is the addition of a seen set. We didn’t need it for part 1, but we sure do for part 2 or we end up looping forever. Every time we look at a possible crate move, we check the seen set, and add the position to the seen set when we do any work with it.

Now, if we’re doing a push in a horizontal (East/West) direction, we don’t need to do much new work. However, if we’re pushing vertically (North/South), we need to account for the fact that pushing one half of a crate pushes the whole crate. So if we detect that, we queue the other half of the crate (WEST when we’re looking at the right hand side of the crate, EAST otherwise).

The only other change to push is to account for the new crate symbols as above. We can also safely look at all three here as well.

Solving part 2 looks almost exactly like solving part 1, except for the remap that needs to happen.

// In Day15

fun solvePart2(): Int =
    warehouse
        .map { it.remap() }
        .doMovements()
        .findAll('[')
        .sumOf { it.gps() }

Star earned! See you tomorrow!

Puzzle Input

⭐ Day 15, Part 1

⭐ Day 15, Part 2

Further Reading