# Advent of Code 2023 - Day 21

By Eric Burden | December 21, 2023

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Kotlin. I’ll post my solutions and code to GitHub as well. If you haven’t given AoC a try, I encourage you to do so along with me!

# Day 21 - Step Counter

Find the problem description HERE.

## The Input - Another Day, Another 2D Grid

Today, we have our old friends '.' and '#', along with the special guest 'S'! The grid represents a garden with passable spaces and impassable rocks. Let’s parse that grid!

/**
* This enum represents one tile in the map of the garden
*/
enum class GardenMapTile {
OPEN, ROCK, START;

companion object {
/**
* Parse a [GardenMapTile] from a character
*
* @param char The character representing a [GardenMapTile].
* @return A [GardenMapTile] represented by the input character.
* @throws Exception When the character does not represent a [GardenMapTile].
*/
fun fromChar(char: Char): GardenMapTile = when (char) {
'.' -> OPEN
'#' -> ROCK
'S' -> START
else -> throw Exception("Cannot parse \$char to a [GardenMapTile]!")
}
}
}

/**
* This class represents the map of the garden the elf wants to walk in
*
* @property grid The grid of tiles that comprise this garden.
* @property start The elf's starting location for their walkabout.
*/
open class GardenMap(
val grid: List<List<GardenMapTile>>,
val start: Utils.Index2D
) {
companion object {
/**
* Parse a [GardenMap] from the input
*
* @param input The grid of characters from the input file.
* @return The [GardenMap] represented by the input file.
* @throws Exception When the input cannot be parsed.
*/
fun fromInput(input: List<List<Char>>): GardenMap {
val grid = input.map { row -> row.map(GardenMapTile::fromChar) }

// Search the grid for the first row/col index containing a
// START tile.
val start = grid.withIndex().flatMap { (rowIdx, row) ->
row.withIndex().map { (colIdx, value) ->
Utils.Index2D(rowIdx, colIdx) to value
}
}.find { (_, tile) -> tile == GardenMapTile.START }?.first
?: throw Exception("Could not find starting tile!")

return GardenMap(grid, start)
}
}

// For pretty printing!
override fun toString(): String = grid.joinToString("\n") { row ->
row.joinToString("") { tile ->
when (tile) {
GardenMapTile.ROCK -> "#"
GardenMapTile.OPEN -> "."
GardenMapTile.START -> "S"
}
}
}
}

class Day21(input: List<List<Char>>) {

// We're old hands at parsing a grid of characters into a map of some sort.
private val parsed = GardenMap.fromInput(input)

}

Now, let’s see what we need to do with this map…

## Part One - Walking in a Winter Wonderland

So… turns out, there’s not really anything we need to be doing right now, so we’re going to help an active elf quantify their walk. I wonder if this elf knows the same trick as the ghost and plans to walk to all these reachable tiles simultaneously? Now that would be something to see! For now, though, we just need to identify which spaces in the map the elf can possibly land on after taking exactly 64 steps. Note that because the example uses a lower number of steps, the solution takes the number of allowed steps as a parameter.

/**
* This enum represents one tile in the map of the garden
*/
enum class GardenMapTile {
OPEN, ROCK, START;

// companion object { ... }
}

open class GardenMap(
val grid: List<List<GardenMapTile>>,
val start: Utils.Index2D
) {
// companion object { ... }

val rows: Int get() = grid.size
val cols: Int get() = grid.first().size
val offsets = listOf(
Utils.Offset2D(-1, 0),
Utils.Offset2D(1, 0),
Utils.Offset2D(0, -1),
Utils.Offset2D(0, 1)
)

/**
* Checks an index to ensure it is in the bounds of the map
*
* @param idx The index to check.
* @return A boolean indicating whether the index is in bounds.
*/
private fun inBounds(idx: Utils.Index2D): Boolean {
val (row, col) = idx
return row in 0..<rows && col in 0..<cols
}

// Indexing for the GardenMap
open operator fun get(idx: Utils.Index2D) = grid[idx.row][idx.col]

/**
* Return the reachable neighboring indices of the given index
*
* @param idx The index to check for neighbors.
* @return A list of neighboring indices that are reachable from idx. A
* reachable idx is one that is in the bounds of the map and doesn't contain
* a rock.
*/
open fun neighborsOf(idx: Utils.Index2D) = offsets.map { idx + it }
.filter { inBounds(it) && get(it) != GardenMapTile.ROCK }

/**
* Return the number of tiles that can be reached in a certain number of steps
*
* @param stepsAllowed The number of steps the elf will take.
* @return The number of tiles that can be reached in exactly stepsAllowed
* steps.
*/
fun reachableTiles(stepsAllowed: Int): Int {

// Mostly just a breadth-first search through the garden spaces.
val queue = ArrayDeque(listOf(0 to start))
val seen = mutableSetOf<Utils.Index2D>()

// With the twist that we're keeping track of every tile we reach
// and the number of steps it took to reach it.
val visited = mutableListOf<Pair<Int, Utils.Index2D>>()

while (queue.isNotEmpty()) {
val (steps, tileIdx) = queue.removeLast()
if (steps > stepsAllowed || seen.contains(tileIdx)) continue

for (neighborIdx in neighborsOf(tileIdx)) {
if (seen.contains(neighborIdx)) continue
}
}

// The tiles that are reachable in exactly stepsAllowed steps are
// the tiles that we reach at the same parity as stepsAllowed, i.e.,
// when stepsAllowed is even, the tiles reachable in an even number
// of steps will be included. When stepsAllowed is odd, the tiles
// reachable in an odd number of steps will be included. For our
// purposes, 0 counts as an even number (so that the start will be
// included for even numbers of steps).
return visited.count { (idx, _) -> idx % 2 == stepsAllowed % 2 }
}

}

class Day21(input: List<List<Char>>) {

// private val parsed = ...

// Walk the elf through the garden his desired number of steps and return
// a count of all the tiles that can be landed on in exactly stepsAllowed
// number of steps.
fun solvePart1(stepsAllowed: Int): Int = parsed.reachableTiles(stepsAllowed)

}

Not too tough. A little breadth-first search with some pruning and we can directly find all the reachable spaces. Now for part two…

## Part Two - Get To Steppin'

I’ll be honest, I really expected part two to involve some sort of quantum splitting of the elf along different paths. Instead, we just crank the number of steps to 11 and break the laws of space by wrapping the garden infinitely in all directions. Ugh. The worst part? We need math for this one. Double ugh!

/**
* This enum represents one tile in the map of the garden
*/
enum class GardenMapTile {
OPEN, ROCK, START;

// companion object { ... }
}

open class GardenMap(
val grid: List<List<GardenMapTile>>,
val start: Utils.Index2D
) {
// companion object { ... }

val rows: Int get() = grid.size
val cols: Int get() = grid.first().size
val offsets = listOf(
Utils.Offset2D(-1, 0),
Utils.Offset2D(1, 0),
Utils.Offset2D(0, -1),
Utils.Offset2D(0, 1)
)

// private fun inBounds(idx: Utils.Index2D): Boolean { ... }

// open operator fun get(idx: Utils.Index2D) = ...

// open fun neighborsOf(idx: Utils.Index2D) = ...

// fun reachableTiles(stepsAllowed: Int): Int { ... }

}

/**
* This class represents the repeating garden map
*
* In part two, the map goes infinite! This subclass of [GardenMap] updates
* some methods so that it can be treated as if it repeats infinitely in all
* four directions.
*
* @property grid The grid of tiles that comprise this garden.
* @property start The elf's starting location for their walkabout.
*/
class GardenMapInfinite(
grid: List<List<GardenMapTile>>,
start: Utils.Index2D
) : GardenMap(grid, start) {
companion object {
fun fromGardenMap(gardenMap: GardenMap): GardenMapInfinite {
return GardenMapInfinite(gardenMap.grid, gardenMap.start)
}
}

/**
* Access an index in an infinite, repeating map
*
* To treat the _actually_ finite grid as an infinite map for indexing,
* we need to wrap the indexes around the width and height of the grid.
*
* @param idx The index to fetch.
* @return The map tile at that index.
*/
override operator fun get(idx: Utils.Index2D): GardenMapTile {
// Some fun with modulo to wrap the indices in both directions
val rowIdx = (idx.row % rows + rows) % rows
val colIdx = (idx.col % cols + cols) % cols
return grid[rowIdx][colIdx]
}

/**
* Get the neighbors of an index in an infinite garden
*
* The only change here is to remove the bounds-checking, because
* an infinite garden is *boundless*!
*
* @param idx The index to check for neighbors.
* @return A list of neighboring indices that are reachable from idx. A
* reachable idx is one that doesn't contain a rock.
*/
override fun neighborsOf(idx: Utils.Index2D) = offsets.map { idx + it }
.filter { get(it) != GardenMapTile.ROCK }
}

class Day21(input: List<List<Char>>) {

// private val parsed = ...

// fun solvePart1(stepsAllowed: Int): Int = ...

// Ugh, this is some funky (to me, at least) math.
fun solvePart2(stepsAllowed: Int): Long {
// Start by converting the garden map to a theoretically infinite tiling
// of the original grid map.
val map = GardenMapInfinite.fromGardenMap(parsed)

/*
And this is where it starts to get a bit...wonky. We can observe from
the input that the number of steps the elf wants to take is a multiple
of the grid size + (grid size // 2). The grid is 131 tiles square, so
we can see that 26501365 = n * 131 + 65, with n = 202,300. We also
note that, in the real input, there is a clear path from the start to
each edge and each edge is clear all the way around. Additionally, the
input forms a _diamond_ shape with a clear lane all the way around the
manhattan distance of (grid size / 2) from the start. So, this means
our zoomed out grid looks like:

2....2
..11..
..11..
2....2

where the 1's represent the inner section of obstacles and the 2's
represent the outer section of obstacles, which tiles to:

2....22....22....22....22....2
..11....11....11....11....11..
..11....11....11....11....11..
2....22....22....22....22....2
2....22....22....22....22....2
..11....11....11....11....11..
..11....11....11....11....11..
2....22....22....22....22....2
2....22....22....22....22....2
..11....11....11....11....11..
..11....11....11....11....11..
2....22....22....22....22....2
2....22....22....22....22....2
..11....11....11....11....11..
..11....11....11....11....11..
2....22....22....22....22....2
2....22....22....22....22....2
..11....11....11....11....11..
..11....11....11....11....11..
2....22....22....22....22....2

So, without assuming that the 1 set of rocks and the 2 set of rocks
are identical, we have alternating blocks of obstacles that form a
repeating ring-like pattern around the center. We can then proceed on
the assumption that these rings form the basis of a pattern in our
output, like:

- At (grid size / 2) steps, the elf's walking range encompasses the
1 set of obstacles in the center.
- At (grid size / 2) + (grid size) steps, the elf's range now
encompasses the entire first ring of obstacles, including 5 groups
of 1s and 4 groups of 2s.
- At (grid size / 2) + (grid size * 2), the elf's range now
encompasses the first two rings of obstacles, including 13 groups
of 1's and 12 groups of 2's.

Because the number of obstacle groups included is scaling in some
predictable fashion with an increase in number of steps by (grid size),
we are able to manually find the first few results for the function
steps -> reachable tiles and extrapolate the answer from there.
*/

// Taking the first four results of steps -> reachable tiles for
// step sizes at (grid size // 2), (grid size // 2) + (grid size),
// (grid size // 2) + (grid size * 2), (grid size // 2) + (grid size * 3)...
val stepIncrements = (0..3).map { incr ->
(map.grid.size / 2) + (map.grid.size * incr)
}
val reachableTileCounts = stepIncrements.map { map.reachableTiles(it).toLong() }
.toMutableList()

/*
For my input, I get [3755, 33494, 92811, 181706] for these first four
counts of reachable tiles. The increase isn't linear, however, if we
repeatedly take the differences between the values in sequence...

[3755, 33494, 92811, 181706]
[29739, 59317, 88895]
[29578, 29578]
[0]

It's Day 9! Or, rather, it's a polynomial sequence. There's definitely
math that can be done here to derive a formula for predicting the next
values based on this, but for my own sanity, I'm going to use the same
method from Day 9.
*/

// Start by generating the lists of differences shown above.
val diffs = mutableListOf(reachableTileCounts)
while (diffs.last().last() > 0) {
val diffDiffs =
diffs.last().windowed(2).map { (prev, next) -> next - prev }
.toMutableList()
}
diffs.reverse()

// Calculate the number of times we need to predict the next value as
// the number of times we can increase the number of steps by the
// grid size, up to the desired number of steps, starting at
// (grid size // 2), aka: 26501365 = n * 131 + 65, with n = 202,300.
val numStepCycles = (stepsAllowed - (map.grid.size / 2)) / map.grid.size

// Now, we use the same procedure from Day 9 to predict the next value
// in our sequence numStepCycles times, and return the last predicted
// value. Does this count as dynamic programming, I wonder?
while (diffs.last().size <= numStepCycles) {
for ((prev, next) in diffs.windowed(2)) {
}
}

return diffs.last().last()
}
}

I’m not going to lie, I needed a hint to get this one. I didn’t initially see the significance of the total number of steps or the fact that there was a clear path from the start to this entirely walk-able diamond shape within the pattern. With those two nuggets in hand, though, the rest of the solution (painfully) came together.

## Wrap Up

Whew! This was a tough day. Not only did we have a cycle, but the cycle results were quadratic instead of linear, and it wasn’t immediately clear what we had a cycle of. I needed a few different hints in the right direction to finally wrap my head around what was happening here. On the positive side, being exposed to this kind of problem should help me be better able to spot similar situations in the future! On the negative side, I really dislike when the examples and the actual solution require different procedures to generate. Can’t win them all, I guess!