Skip to Content

# Advent of Code 2023 - Day 17, in Kotlin - Clumsy Crucible

Kotlin solutions to parts 1 and 2 of Advent of Code 2023, Day 17: 'Clumsy Crucible'

Posted on

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!

#### Further Reading

1. Index of All Solutions - All posts and solutions for 2023, in Kotlin.
2. My Github repo - Solutions and tests for each day.
3. Solution - Full code for day 17
4. Advent of Code - Come join in and do these challenges yourself!