Advent of Code 2023 - Day 17, in Kotlin - Clumsy Crucible • Todd Ginsberg

Remember yesterday when I said sometimes we’ll write a pathfinding algorithm where we care about the order of the work being done and have to use a PriorityQueue instead of an ArrayDeque? Well guess what happened today!

Update 2023-12-29: If you ran this code on your input and it didn’t work, I’ve got a fix. I was only accounting for inputs that started moving East at the start, like mine does. If your input assumes you need to move South, check out part 1 for a fix and attributions.

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

Puzzle Input

A few days ago, I wrote a couple of extension functions on Array<CharArray> to make working with grids easier. Unfortunately unless we want a lot of toInt() calls to convert characters to integers we’ll probably need to change our data structure around a bit and add new extensions.

Our input today will end up in a List<List<Int>> to represent a grid, so we can take it in as a List<String> and parse it directly. We’ll use Kotlin’s handy digitToInt function to turn a single character digit into an integer.

class Day17(input: List<String>) {

    private val grid = input.map { row -> 
    	row.map { it.digitToInt() } 
    }

}

And the new extension functions provide easier read access for the grid, assuming it is a List<List<*>> (meaning - the inner list can hold anything).

// In Extensions.kt

fun List<List<*>>.isSafe(at: Point2D) =
    at.y in this.indices && at.x in this[at.y].indices

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

These are just copies of the array-based versions.

⭐ Day 17, Part 1

The puzzle text can be found here.

Strategy

We’ll implement Dijkstra’s algorithm for finding the shortest path through a graph and use a priority queue to keep the states we need to evaluate in order of cheapest to most expensive.

Since part 1 and part 2 differ in what is a legal move for the crucible, we will allow the caller of the function to provide a function to determine if a potential move is valid or not. Callers will also be able to specify the minimum number of steps in a row the crucible must take (as this too changes for part 2).

Implementation

One thing to remember is…

The crucible also can’t reverse direction; after entering each city block, it may only turn left, continue straight, or turn right.

We’ll reuse NORTH, SOUTH, EAST, and WEST to represent directional offsets from our Point2D class, which we wrote a few days ago. In order to enforce the “no going backwards” rule, we will create a Map<Point2D, Set<Point2D>> of valid directions where the key is the direction we’re currently traveling and the value is the set of directions we’re allowed to travel from here.

// In Day17

private val directions = mapOf(
    NORTH to setOf(NORTH, EAST, WEST),
    WEST to setOf(WEST, NORTH, SOUTH),
    SOUTH to setOf(SOUTH, EAST, WEST),
    EAST to setOf(EAST, NORTH, SOUTH)
)

Next, when we write our path traversal algorithm, we’ll need to keep track of some State. Namely, the location within the grid, the direction we’re traveling, and how many steps total we’ve taken. If we see the same State more than once, we know any future evaluations will just cause duplicate work to happen, so we will cache all of the states we see. Let’s implement this as a data class so we get hashCode and equals for free.

// In Day17

private data class State(val location: Point2D, val direction: Point2D, val steps: Int) {
    fun next(nextDirection: Point2D): State =
        State(
        	location+nextDirection, 
        	nextDirection, 
        	if(direction == nextDirection) steps+1 else 1
        )
}

We also provide a next function to calculate the next State given a nextDirection to travel in. This function takes care of resetting the step count back to 1 if we turn.

Next, because we want to order our work by least amount of headLoss, but we don’t actually want that as part of the State, we’ll create a Work class which takes a state and the heatLoss. We’ll use this to schedule future work in our work queue. It implements Comparable<Work> so the priority queue will keep Work with a lower heatLoss value ahead of any Work with greater heatLoss values.

// In Day17

private data class Work(val state: State, val heatLoss: Int) : Comparable<Work> {
    override fun compareTo(other: Work): Int =
        heatLoss - other.heatLoss
}

And now we can write our calculateHeatLoss function. The general pattern should look familiar if you’ve been reading my solutions.

// In Day17

private fun calculateHeatLoss(minSteps: Int = 1, isValidNextMove: (State, Point2D) -> Boolean): Int {
    val goal = Point2D(grid.first().lastIndex, grid.lastIndex)
    val seen = mutableSetOf<State>()
    val queue = PriorityQueue<Work>()

    listOf(EAST, SOUTH).forEach { startDirection ->
        State(Point2D(0, 0), startDirection, 0).apply {
            queue += Work(this, 0)
            seen += this
        }
    }

    while (queue.isNotEmpty()) {
        val (current, heatLoss) = queue.poll()
        if (current.location == goal && current.steps >= minSteps) return heatLoss

        directions
            .getValue(current.direction)
            .filter { direction -> grid.isSafe(current.location + direction) }
            .filter { direction -> isValidNextMove(current, direction) }
            .map { direction -> current.next(direction) }
            .filterNot { state -> state in seen }
            .forEach { state ->
                queue += Work(state, heatLoss + grid[state.location])
                seen += state
            }
    }
    throw IllegalStateException("No route to goal")
}

As mentioned above we’re letting the caller define the minSteps that the crucible must take as well as a function isValidNextMove to make sure that the Work we are about to add to the queue is valid.

First, we determine the goal (the end of the grid), set up our seen cache, and our work queue as a PriorityQueue. Since the PriorityQueue is typed to Work, it will use the comparator we defined above to order work items.

We start the process by initializing the queue with a start State (at the origin and having taken 0 steps so far). Since we could be traveling either EAST or SOUTH at this point, we need to add starting positions for either alternative. We wrap each starting State into a Work object, indicating that we have had zero heatLoss so far. Since we’re standing on the origin at the start of the puzzle, we can assume we’ve seen it so we add both start states to the cache.

Note: I originally had a bug here and only accounted for EAST as the starting direction (which worked for my East-based input but not for anybody whose input was South-based). Two people pointed this out to me and I appreciate them letting me know and identifying the correct solution as well! /u/Artraxes pointed it out on Reddit and was kind enough to provide an input that triggered the case I was missing, and @nkiesel filed a GitHub issue with a possible code fix. Thank you both!

Next, we start removing work items from the front of the queue. We’ll use destructuring to break up the Work into a current State and the heatLoss. The first thing to do is to check if we’re done working. We know we’re done if we’re standing on the goal having taken minSteps at least.

Assuming we haven’t reached the end, we’ll need to find some more work to do from here. To do that, we get the valid directions we can travel and make sure that traveling in that direction isSafe (is within the grid). Next we need to check that this move is valid, so we execute the isValidNextMove function provided by the caller (because again, this changes from part 1 to part 2). At this point we have a valid move that is within the grid, so we map it to the next State. At this point we check the seen cache to make sure we haven’t already seen this State. Note here that Kotlin has both filter and filterNot, which you can use interchangeably by negating the condition. I like to have a “positive” condition inside the lambda so I’ll use filterNot here and filter for the others.

Once we’ve reached this point we have a collection of states that are not only valid, but that are new to us. So we’ll add them all to the queue by calculating the new heatLoss value, and mark them all as seen. Why say we’ve seen this new state before actually pulling it out of the queue? Because the queue is ordered by heatLoss, so anything we say we’ve seen now will be the quickest we could have arrived at that state, even if the work is queued up to be evaluated later. So there’s not real reason not to do it now.

Now we can solve part 1.

// In Day17

fun solvePart1(): Int =
    calculateHeatLoss { state, nextDirection ->
        state.steps < 3 || state.direction != nextDirection
    }

In part 1, a valid next state is one that has taken fewer than 3 steps in the current direction OR is a turn. Running this gives the answer for part 1.

Star earned! Onward!

⭐ Day 17, Part 2

The puzzle text can be found here.

Because the calculateHeatLoss function takes arguments allowing us to modify its behavior, we don’t have much to write for part 2.

// In Day17

fun solvePart2(): Int =
    calculateHeatLoss(4) { state, nextDirection ->
        if (state.steps > 9) state.direction != nextDirection
        else if (state.steps < 4) state.direction == nextDirection
        else true
    }

We specify that the minSteps for part 2 is 4, and that a valid next state is at least 4 steps long and no more than 10 steps long. Running this gives us the answer to part 2.

Star earned! See you tomorrow!

⭐ Day 17, Part 1

⭐ Day 17, Part 2

Further Reading