Advent of Code 2024 - Day 10, in Kotlin - Hoof It • Todd Ginsberg

There are several ways we could have solved this problem and today I’ve chosen to implement a Breadth-First search. I seem to implement a lot of them in the context of Advent of Code and almost never anywhere else. I generally like the graph/maze puzzles in Advent of Code so this was a nice start to my day.

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

Puzzle Input

We will take our input in as a List<String> and we could keep it that way if we wanted to. However, since we’ll be doing some numerical comparisons on the height map, we probably want the individual places as integers. So we’ll convert the inner String to an IntArray (we could also have gone with List<Int> if we had wanted).


class Day10(input: List<String>) {

    private val grid: List<IntArray> = input.map { row -> 
        row.map { it.digitToInt() }.toIntArray() 
    }

}

⭐ Day 10, Part 1

The puzzle text can be found here.

Since we’ll be doing some operations on our grid, let’s add some private extension functions to make that a bit more clean. First up, a contains operator so we can see if a Point2D is in the grid. We will represent all x/y pairs using the Point2D class we’ve been building over the last few puzzles.

// In Day10

private operator fun List<IntArray>.contains(at: Point2D): Boolean =
    at.y in indices && at.x in get(at.y).indices

And another to get the value at a Point2D in the grid (assuming it is a valid place, we don’t do any error checking).

// In Day10

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

When we are looking at a Point2D, we want to get its cardinalNeighbors, so we will add a function to do that. This returns a set of points created from the cardinal direction offsets we’ve previously declared.

// In Point2D

fun cardinalNeighbors(): Set<Point2D> =
    setOf(
        this + NORTH,
        this + EAST,
        this + SOUTH,
        this + WEST
    )

Next, we want to actually find paths from the start to any high point (“9”). I’m going to spoil part 2 a bit and let you know that we will be doing the same thing as part 1 except calculating unique paths to the high point, not unique high points. The only difference in there is whether we remember our path or not, so we’ll add a memory flag do the findPaths function now, so we don’t have to refactor it later, which could potentially be confusing.

The findPaths method is a fairly standard Breadth-First Search. Meaning, for a given spot on the grid, we’ll search all of its neighbors before searching any of their neighbors. If you think of the grid like a tree, we will be searching all of the nodes on the next level before any nodes on the following level. This is opposed to a Depth-First search (which we also could have used here) that searches deep before it searches wide.

// In Day10

private fun findPaths(start: Point2D, memory: Boolean): Int {
    val queue = mutableListOf(start)
    val seen = mutableSetOf<Point2D>()
    var found = 0

    while (queue.isNotEmpty()) {
        val place = queue.removeFirst()
        if (place !in seen) {
            if (memory) seen += place
            if (grid[place] == 9) found++
            else {
                queue.addAll(
                    place.cardinalNeighbors()
                        .filter { it in grid }
                        .filter { grid[it] == grid[place] + 1 }
                )
            }
        }
    }
    return found
}

Our first step is to set up a queue to hold work we plan to do, in the order we plan to do it in. In this case, the queue will hold Point2D objects, representing places on the grid to examine. We’ll also create a seen set to hold places we’ve visited, to prevent us from re-visiting them when memory is turned on. We also count the number of high points we have found.

Next, the actual work of the algorithm. While there is work to do (the queue has something in it), we remove the first element from the queue and make sure we haven’t seen this yet. In the case when memory is off, this will never be false. We examine the place and see if it is a high point, and if so we add to the found counter. If not, we want to get all of the cardinalNeighbors of the place. We need to take care to make sure they are in the grid (there’s the call to our contains operator!), and that the neighbor is one higher than the current place. We add all those Point2D objects (if any) to the queue. When the queue runs out of work to do (meaning we’ve seen all of the end spots), we return the count of the high points found.

All we have left is to write a function to add up all the scores of the starting points.

// In Day10

private fun scoreTrails(memory: Boolean): Int =
    grid.mapIndexed { y, row ->
        row.mapIndexed { x, i ->
            if (i == 0) findPaths(Point2D(x, y), memory) else 0
        }.sum()
    }.sum()

The scoreTrails function takes in a memory flag do pass to findPaths and then calls findPaths for every x/y Point2D that represents a trailhead (“0”). We sum all of these numbers together to get our answer.

Calling scoreTrails and telling it to remember our path solves part 1.

// In Day10

fun solvePart1(): Int = scoreTrails(true)

Star earned! Onward!

⭐ Day 10, Part 2

The puzzle text can be found here.

See? Adding that memory flag sure saved us time here. Basically, by turning off the memory, we’re allowing the findPaths function to visit the same place twice. Because of the nature of the Breath-First search, this means we are on a slightly different path to the high point if this happens.

Calling scoreTrails with memory set to false solves part 2.

// In Day10

fun solvePart2(): Int = scoreTrails(false)

Star earned! See you tomorrow!

Puzzle Input

⭐ Day 10, Part 1

⭐ Day 10, Part 2

Further Reading