# Advent of Code 2023 - Day 14, in Kotlin - Parabolic Reflector Dish

Kotlin solutions to parts 1 and 2 of Advent of Code 2023, Day 14: 'Parabolic Reflector Dish'

Posted on

Years ago I would have struggled with a problem like this (part 2, anyway). But true to one of the goals of Advent of Code, I’m a better programmer now in that I can recognize when a “detect the cycle” problem comes my way.

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

Puzzle Input

Today we’ll take our `input` in as a `List<String>` and convert it to a `List<CharArray>`. We’re using arrays because we’ll be altering the state of the `grid`.

``````class Day14(input: List<String>) {

private val grid: Array<CharArray> =
input.map { it.toCharArray() }.toTypedArray()
}
``````

#### ⭐ Day 14, Part 1

The puzzle text can be found here.

Let’s get some housekeeping functions out of the way. First up, we need to calculate the `score` of a `grid`.

``````// In Day14

private fun Array<CharArray>.score(): Int =
mapIndexed { y, row ->
row.sumOf { c ->
if (c == 'O') size - y
else 0
}
}.sum()
``````

If there were a `sumOfIndexed`, this might have been a bit easier to follow, but basically we loop through every `x` and `y` pair of coordinates in the grid and sum up the weights if a round rock is there. Otherwise, a space or a different rock contributes 0 to the score.

Next up, a way to `swap` the values in two points in a `grid`. Since we already have a few grid-based functions in our general extensions file, we’ll add this there.

``````// In Extensions.kt

fun Array<CharArray>.swap(a: Point2D, b: Point2D) {
val tmp = this[a]
this[a] = this[b]
this[b] = tmp
}
``````

Not much to say about swapping values in a mutable data structure. Make a copy of one value, overwrite it, use the copy to overwrite the second value.

Strategy

We will make use of the `Point2D` object we’ve created for previous puzzles this year. One aspect of these points is their composable nature (we can add them together) and our pre-defined `NORTH`, `WEST`, `SOUTH`, and `EAST` directional offsets.

Since I know about part 2, I’ll reveal one hint - we’re not going to only need to tilt to the NORTH. We’ll involve the other cardinal directions as well. So let’s plan for that.

Implementation

Part 1 has us tilting to the north one single time, but part 2 has us doing this many times. Since the order of how we evaluate each of the places in the grid is important, let’s capture this explicitly. Since every time we want to tilt north the order is the same, we can save this in a map we’ll call `progressions`.

``````// In Day14

private val progressions: Map<Point2D, List<Point2D>> = mapOf(
Point2D.NORTH to grid.indices.flatMap { y ->
grid.first().indices.map { x ->
Point2D(x, y)
}
}
)
``````

To tilt northward, we need to evaluate the grid from top to bottom or else things will run into each other prematurely. So to define the `List<Point2D>` representing a `NORTH` tilt, we make points by looping through all of the `y` values in order, and then all of the `x` values in order.

``````// In Day14

private fun Array<CharArray>.tilt(direction: Point2D) {
progressions
.getValue(direction)
.filter { this[it] == 'O' }
.forEach { doTilt(it, direction) }
}
``````

Again, we’ll be doing the `tilt` more than just one way, so let’s plan for that here. We look up our order of evaluation from `progressions`, then `filter` so we can only include round rock. Finally, we call our `doTilt` function which does the actual work of tilting and moving rocks around.

``````// In Day14

private fun Array<CharArray>.doTilt(place: Point2D, direction: Point2D) {
var current = place
while (isSafe(current + direction) && this[current + direction] == '.') {
swap(current, current + direction)
current += direction
}
}
``````

For a given rock we want it to roll in the `direction` we care about until it lands next to either the edge of the `grid` or up against something (another rock, we don’t care which kind). We’ll reuse our `isSafe` function from the other day to make sure where we want to roll is still on the `grid`, and `swap` our `current` location (a `O`) with its neighbor.

``````// In Day14

fun solvePart1(): Int {
grid.tilt(Point2D.NORTH)
return grid.score()
}
``````

The solution to part 1 is to `tilt` to the north a single time and take the `score`.

Star earned! Onward!

#### ⭐ Day 14, Part 2

The puzzle text can be found here.

See? I told you we’d need more than just north. Let’s fill out our `progressions` map.

``````// In Day14

private val progressions: Map<Point2D, List<Point2D>> = mapOf(
Point2D.NORTH to grid.indices.flatMap { y ->
grid.first().indices.map { x ->
Point2D(x, y)
}
},
Point2D.WEST to grid.first().indices.flatMap { x ->
grid.indices.map { y ->
Point2D(x, y)
}
},
Point2D.SOUTH to grid.indices.reversed().flatMap { y ->
grid.first().indices.map { x ->
Point2D(x, y)
}
},
Point2D.EAST to grid.first().indices.reversed().flatMap { x ->
grid.indices.map { y ->
Point2D(x, y)
}
}
)
``````

I won’t go into a ton of detail here, but basically each way we tilt has its own order of evaluation to avoid collisions we don’t want. For example, north is done top down, south is done bottom up, west is done left to right, east is done right to left.

We now have enough to form a `cycle`:

``````// In Day14

private fun Array<CharArray>.cycle() {
tilt(Point2D.NORTH)
tilt(Point2D.WEST)
tilt(Point2D.SOUTH)
tilt(Point2D.EAST)
}
``````

Four tilts in the order specified. Not much to say about `cycle` (for the record: I love code that’s so simple there’s not much to say about it).

Finally, we can solve. But given our `goal` is so huge, how do we do it? The trick here is to find out how long it takes for consecutive `cycle` calls to repeat and use that value to calculate our `goal`. For example, if our goal is 10, and the pattern repeats every 4 cycles, we know we can run 4 cycles to get us to 8, and then 2 more to get us to 10.

``````// In Day14

fun solvePart2(goal: Int = 1_000_000_000): Int {
val seen = mutableMapOf<Int, Int>()
var cycleNumber = 1
while (cycleNumber <= goal) {
grid.cycle()
when (val state = grid.sumOf { it.joinToString("").hashCode() }) {
!in seen -> seen[state] = cycleNumber++
else -> {
val cycleLength = cycleNumber - seen.getValue(state)
val cyclesRemaining = (goal - cycleNumber) % cycleLength
repeat(cyclesRemaining) {
grid.cycle()
}
return grid.score()
}
}
}
return grid.score()
}
``````

Since we need to detect the cycle, we have a map called `seen` which holds some number representing the state of the `grid` and the `cycleNumber` we encountered that state on. While we have not reached the goal (it is possible to ask for a `goal` smaller than the cycle), we `cycle` the grid, calculate the `state` hash of the resulting grid (which is just the sum of the hashcodes of the stringified rows), and then loop again.

Once we have detected that the same state has been seen twice, we can calculate the `cycleLength` and how many remaining cycles we need to perform to get to the goal. We use`repeat` to do the last few cycles and return the `score`.

Star earned! See you tomorrow!