Advent of Code 2023 - Day 23, in Kotlin - A Long Walk • Todd Ginsberg

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 {
    add(start)
    add(goal)
    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
                    ) {
                        add(this)
                    }
                }
            }
        }
    }
}

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 {
        add(from to 0)
    }
    val seen = mutableSetOf(from)
    val answer = mutableMapOf<Point2D, Int>()
    while (queue.isNotEmpty()) {
        val (location, distance) = queue.removeFirst()
        if (location != from && location in toAnyOther) {
            answer[location] = distance
        } else {
            location.cardinalNeighbors()
                .filter { grid.isSafe(it) }
                .filter { grid[it] != '#' }
                .filter { it !in seen }
                .forEach {
                    seen += it
                    queue.add(it to distance + 1)
                }
        }
    }
    return answer
}

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!

⭐ Day 23, Part 1

⭐ Day 23, Part 2

Further Reading