# Advent of Code 2023 - Day 23, in Kotlin - A Long Walk

Kotlin solutions to parts 1 and 2 of Advent of Code 2023, Day 23: 'A Long Walk'

Posted on

It’s appropriate that the title of today’s puzzle is A Long Walk, as that’s exactly what I was doing when I figured out how I’d solve part 2! I had solved part 1 in the morning and then took my dog Charlie for a walk along the Sal’s Branch Trail at Umstead State Park. While we were walking through the woods I devised my approach for part 2.

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

Puzzle Input

Another grid, another `Array<CharArray>` so we can use the extension functions we’ve already written to make grids easier to manage. We will take our `input` in as a `List<String>` and not declare it as a property as we’re done looking at it after the class initializes.

``````class Day23(input: List<String>) {

private val grid = input.map { it.toCharArray() }.toTypedArray()
private val start = Point2D(input.first().indexOfFirst { it == '.' }, 0)
private val goal = Point2D(input.last().indexOfFirst { it == '.' }, input.lastIndex)

}
``````

Since we refer to them a few times, and they are in different places in everybody’s input, we also pick through the `input` to find the `start` and `goal`. Basically look for the first `.` in the first row for the start and the final row for the goal.

Strategy

Today we’ll write a Depth-First Search (DFS) function to go through the maze for both parts. If you’ve been following my solutions you’ve seen quite a few Breadth-First Search (BFS) functions (and you’ll see another today as well!). What’s the difference? With a BFS, we move through a maze or graph along a frontier. Meaning, all of the spots that are at a certain distance (say, 5 units) are evaluated at the same time (more or less). This has the benefit of being able to stop evaluating when we find the closest thing we’re looking for. No need to keep looking any more, the closest one will be found this way first. On the other hand, a DFS tries to go all the way to the goal and then back up the path it came from. Usually, these are recursive algorithms (you can, of course, write them iteratively as well). Because today’s puzzle asks us to find the longest route to the goal, we’ll use DFS to evaluate all of the possible routes.

Since we’re using DFS in both parts, we will write a single `traverse` function that takes a function as an argument. The function’s job is to determine, given a `Point2D`, what places we should look at next and how much it will cost to get there (it is not always 1!). So the function takes a `Point2D` and returns a `Pair<Point2D,Int>`.

``````// In Day23

private fun traverse(nextLocations: (Point2D) -> List<Pair<Point2D, Int>>): Int {
var best = 0
val visited = mutableSetOf<Point2D>()

fun traverseWork(location: Point2D, steps: Int):Int {
if (location == goal) {
best = max(steps, best)
return best
}
visited += location
nextLocations(location)
.filter { (place, _) -> place !in visited }
.forEach { (place, distance) -> traverseWork(place, distance + steps) }
visited -= location
return best
}

return traverseWork(start, 0)
}
``````

What the heck? Functions in functions? Yes, Kotlin supports this, and while I don’t use it very often because I personally find it confusing, it is handy for a situation like this. We’re making a trade-off here. Either the signature to `traverse` gets really messy, OR we have a global `best` and `visited` variable (ew), OR we have a separate private function that does the `traverseWork`. So I opted to make `traverseWork` an inner function within `traverse`.

The first thing we do is set the `best` we’ve seen to 0 and initialize an empty set of `visited` nodes. Then (down at the bottom) we call `traverseWork` giving it a starting point and how far we’ve traveled so far. In theory, we could make these default values.

Within `traverseWork` we first check to see if the `location` we’re looking at is the `goal`, and if so, we figure out if the number of `steps` we’ve just taken to get here is longer than the `best` so far, and if so, we keep it.

Assuming we’re not at the goal, we add the current `location` to the `visited` set and ask our `nextLocations` function to tell us where to go next. Because the `nextLocations` function may return places we’ve already visited, we check to make sure we haven’t seen them yet. Any location that is left is somewhere we want to go, so we recursively call `traverseWork` with the new `place` and the cost to get there (which is the `steps` we’ve taken so far plus the `distance` cost).

After we’ve exhausted all of the next options for the current location, we remove it from the `visited` set so if we come back through here via a longer route, we’ll be able to. In theory, we could cache our answer here, but I didn’t as it ran fast enough (for me) without doing so.

#### ⭐ Day 23, Part 1

The puzzle text can be found here.

Before we can go traverse the maze, we need to think about how we pick the next spots to look at. In past puzzles, we’d call `cardinalNeighbors` on a `Point2D` and filter out the ones that are walls. We need to do that today too, but we also need to account for the slippery places, so if we run into one of those, we need to make sure that if we hit one, the direction of the next place is also in that direction.

For this, we’ll implement `matchesDirection` on `Char` taking in the `direction` we’re moving.

``````// In Day23

private fun Char.matchesDirection(direction: Point2D): Boolean =
when (this) {
'^' -> Point2D.NORTH == direction
'<' -> Point2D.WEST == direction
'v' -> Point2D.SOUTH == direction
'>' -> Point2D.EAST == direction
'.' -> true
else -> false
}
``````

This enforces the rules that a) If we want to move to a slippery patch that it matches the direction we’re going, b) that we can move to a `.` spot and c) we can’t move to anything else (basically, `#`).

Now that we have that, we can write the logic for the `traverse` function which picks the next places to go.

``````// In Day23

fun solvePart1(): Int =
traverse { location ->
location.cardinalNeighbors()
.filter { grid.isSafe(it) }
.filter { newLocation -> grid[newLocation].matchesDirection(newLocation - location) }
.map { it to 1 }
}
``````

We are allowed to go to any of our `cardinalNeighbors`, if they are valid places in the grid, which we determine via `isSafe`, and that `matchesDirection` lines up. We create a `Pair<Point2D,Int>` representing all of the new spots to go to and their distance from the previous spot, which is always 1.

Star earned! Onward!

#### ⭐ Day 23, Part 2

The puzzle text can be found here.

If we alter our test of what is a valid next location to not check for `matchesDirection` (so, no slippery parts) the grid becomes too large to traverse in a reasonable amount of time. What if we could reduce the number of spots in the maze?

This is what I came up with on our walk. Let’s look at this maze here, where `S` is the start, `G` is the goal, `.` is a valid place to move to, and `#` is a wall:

``````
##S#########
##.#########
##.........#
##.#######.#
##........G#
############
``````

If you think about it, we only get to make a single decision while traversing the maze; whether we want to go East or South at the place 2 steps south of the starting point. If we elide the steps that we must take, and just count their steps instead, we could save a lot of effort.

Looking at that graph, what we want is something like this:

``````|   From   |   To      | Distance |
|----------|-----------|----------|
| x=2, y=0 | x=2,  y=2 | 2        |
| x=2, y=2 | x=10, y=4 | 10       |
``````

We don’t actually have to take the 2 steps from the start to the first decision point, or the 10 steps from there to the end. Assuming a more complicated maze, as long as we know a source, destination, and distance, we can turn our maze (which is really a graph) into a more efficient graph that elides most of the work.

So let’s write a function to find the decision points, called (wait for it…) `findDecisionPoints`. We’ll make this an extension function on the grid (which is an `Array<CharArray>`).

``````// In Day23

private fun Array<CharArray>.findDecisionPoints() = buildSet {
this@findDecisionPoints.forEachIndexed { y, row ->
row.forEachIndexed { x, c ->
if (c != '#') {
Point2D(x, y).apply {
if (cardinalNeighbors()
.filter { grid.isSafe(it) }
.filter { grid[it] != '#' }.size > 2
) {
}
}
}
}
}
}
``````

We’ll use Kotlin’s `buildSet` function to allow us to build a set as we go and not force this into a series of functional calls that may look more complicated. We’ll start by addin gthe `start` and `goal` positions to the set, as they are decision points that we wouldn’t find otherwise. The other decision points are any points in the grid that have at least 3 neighbors that we could move to (otherwise, 2 neighbors means we’re in a hallway and have no choice but to go forward).

Now that we have the list of “interesting” points in the graph, we can reduce the grid to just these points, and make a structure that is like the table above. The data structure we’re going for is `Map<Point2D, Pair<Point2D, Int>>` where the key in the outer map is the place we are moving from and the value of the outer map is a `Pair<Point2D, Int>` where the `Point2D` is the place we’re moving to, and the `Int` is the cost to move there.

Let’s write `reduceGrid` to do this for us.

``````// In Day23

private fun reduceGrid(): Map<Point2D, Map<Point2D, Int>> =
grid.findDecisionPoints().let { decisionPoints ->
decisionPoints.associateWith { point ->
reduceGridFromPoint(point, decisionPoints)
}
}
``````

The real work is done in `reduceGridFromPoint`, which implements a Depth-First Search from a single point to any other points it can reach without going through any other decision points. This runs until it stops and returns all of the spots directly reachable from the source spot, and how far away they are.

``````// In Day23

private fun reduceGridFromPoint(from: Point2D, toAnyOther: Set<Point2D>): Map<Point2D, Int> {
val queue = ArrayDeque<Pair<Point2D, Int>>().apply {
}
val seen = mutableSetOf(from)
while (queue.isNotEmpty()) {
val (location, distance) = queue.removeFirst()
if (location != from && location in toAnyOther) {
} else {
location.cardinalNeighbors()
.filter { grid.isSafe(it) }
.filter { grid[it] != '#' }
.filter { it !in seen }
.forEach {
seen += it
}
}
}
}
``````

The Depth-First Search here works like the ones we’ve written on previous days. Create a `queue` for our work initialized with the start state, a set of spots we’ve `seen` so we don’t back-track, and a map to store our `answer`. We keep taking work from the `queue` as long as it is not empty and evaluate the places it returns. If the place we’re looking at is in the set of decision points, we’ve found something we care about, so we can add it and its `distance` to the `answers` map. Otherwise, we add all of its valid neighbors to the work queue.

Eventually, this function will return a `Map<Point2D, Int>` which is all of the places and their distances that we can reach from some source!

And now we can solve the puzzle by proving a function to `traverse` to tell it how to determine where to go next.

``````// In Day23

fun solvePart2(): Int {
val reducedGrid = reduceGrid()
return traverse { location ->
reducedGrid
.getValue(location)
.map { it.key to it.value }
}
}
``````

We get the `reducedGrid` and then call `traverse` with a function that considers the next valid places to go anything that the reduced grid has, along with its distance.

On my machine this takes about 1.5s to run, which I am fine with. Maybe there’s a better way to do this that’s faster, but I’m satisfied with this since it’s for a puzzle I’ll solve once.

Star earned! See you tomorrow!