Advent of Code 2023 - Day 21, in Kotlin - Step Counter • Todd Ginsberg

Yee-haw that was a difficult puzzle. I got part 1 more or less right away (thanks to all the practice we’ve had this year writing BFS implementations) but was so lost on part 2. Thankfully, somebody on GitHub provided a wonderful analysis (links in part 2!) and I implemented her approach. It’s days like this that I have to remind myself that the goal of Advent of Code (for me) is to become a better programmer, not know all the answers to everything. Sometimes we need to ask for help, and that’s fine.

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

Puzzle Input

We’ll parse our input into another Array<CharArray>, like we’ve done on previous days. And since we need the starting point, we’ll go find that as well and save it as a Point2D in start. I guess we could have derived the starting point given the size of the gardenMap as it is always in the exact middle, but this works too.

class Day21(input: List<String>) {

    private val gardenMap: Array<CharArray> = input.map { it.toCharArray() }.toTypedArray()
    private val start: Point2D = gardenMap.mapIndexedNotNull { y, row ->
        if ('S' in row) Point2D(row.indexOf('S'), y) else null
    }.first()

⭐ Day 21, Part 1

The puzzle text can be found here.

Another day, another Breadth-First Search to the rescue! We’ll write a function to countSteps from the center of the gardenMap outward. We will stop walking the garden when we’ve taken the max amount of steps, or when we can’t take any more (whichever comes first).

// In Day21

private fun countSteps(max: Int = gardenMap.size): Map<Point2D, Int> = buildMap {
    val queue = ArrayDeque<Pair<Point2D, Int>>().apply {
        add(start to 0)
    }
    while (queue.isNotEmpty()) {
        queue.removeFirst().let { (location, distance) ->
            if (location !in this && distance <= max) {
                this[location] = distance
                queue.addAll(
                    location
                        .cardinalNeighbors()
                        .filter { it !in this }
                        .filter { gardenMap.isSafe(it) }
                        .filter { gardenMap[it] != '#' }
                        .map { it to distance + 1 }
                )
            }
        }
    }
}

Since the return type of countSteps is a Map<Point2D, Int> where the key is a place in the garden and the value is how many steps it took to get there, we’ll start with buildMap. This function allows us to build an immutable map but allow for mutability during the building process.

First, we’ll set up our work queue which contains a Pair<Point2D, Int>>. The Point2D is a place in the garden and the Int is how many steps it took to get there. Like our map. While we have work left to do (the queue.isNotEmpty), we destructure the first element of the queue into a location and its distance. If we don’t already have a record of the location in the map we’re building, and its distance is not over the max allowed, we will add it to the map we’re building. Then we enqueue all of the cardinalNeighbors (NOT: neighbors as I discovered after a few minutes of debugging!) that are not already in the map we’re building (no walking backwards), and are valid spots to go to (within the garden and are not walls/rocks).

This function ends whenever we’ve run out of work to do, which is that we’ve walked anywhere we can walk in the garden, or we’ve taken the max amount of steps.

Now we can answer part 1.

// In Day21

fun solvePart1(goal: Int): Int =
    countSteps(goal).values.count { it % 2 == 0 }

We call countSteps with the goal number (this differs from the example and the real input) and count the number of values in the resulting step map whose step count is even.

Star earned! Onward!

⭐ Day 21, Part 2

The puzzle text can be found here.

I was totally lost when I read part 2. I knew that even if we wanted to simply traverse the garden and pretend it is multiplied ad infinitum, it would take longer than I want to wait around for. I tried to look at the input and saw that there is a diamond of free spaces around the centerpoint, and that the row and column the starting point are on don’t have any blockers, but I couldn’t string that together into an answer.

Go read the wonderful analysis of this problem by villuna at GitHub . She does a great job of explaining the problem, why the rock-free zones are important, and provides some diagrams as well. Thanks Luna!

Anyway, this is a Kotlin implementation of that approach. Note that this won’t work on the example inputs because they don’t have the same characteristics that apparently all real inputs do.

// In Day21

fun solvePart2(stepCount: Int): Long {
    val steps = countSteps()
    val oddCorners = steps.count { it.value % 2 == 1 && it.value > 65 }.toLong()
    val evenCorners = steps.count { it.value % 2 == 0 && it.value > 65 }.toLong()
    val evenBlock = steps.values.count { it % 2 == 0 }.toLong()
    val oddBlock = steps.values.count { it % 2 == 1 }.toLong()
    val n: Long = ((stepCount.toLong() - (gardenMap.size / 2)) / gardenMap.size)

    val even: Long = n * n
    val odd: Long = (n + 1) * (n + 1)
    return (odd * oddBlock) + (even * evenBlock) - ((n + 1) * oddCorners) + (n * evenCorners)
}

I’m not going to say much here that the analysis doesn’t cover better. I originally had the distance checks as Manhattan distances but discovered that I didn’t need them for my input. In the event that this approach doesn’t yield the right answer for you, try replacing it.value > 65 with it.value.distanceTo(start) > 65 and see if that helps!

Star earned (kinda)! See you tomorrow!

⭐ Day 21, Part 1

⭐ Day 21, Part 2

Further Reading