Advent of Code 2023 - Day 14, in Kotlin - Parabolic Reflector Dish • Todd Ginsberg

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 userepeat to do the last few cycles and return the score.

Star earned! See you tomorrow!

⭐ Day 14, Part 1

⭐ Day 14, Part 2

Further Reading