# Advent of Code 2023 - Day 21, in Kotlin - Step Counter

Kotlin solutions to parts 1 and 2 of Advent of Code 2023, Day 21: 'Step Counter'

Posted on

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 {
}
while (queue.isNotEmpty()) {
queue.removeFirst().let { (location, distance) ->
if (location !in this && distance <= max) {
this[location] = distance
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!