Advent of Code 2022 - Day 23, in Kotlin - Unstable Diffusion • Todd Ginsberg

I sure am glad this puzzle wasn’t another cube we had to move across. I had the core logic done on this one fairly quickly but a typo caused me a delay while I debugged. Anyway, that’s all sorted out now and I’m happy with the results.

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

Puzzle Input

Today’s puzzle input will be parsed into a Set<Point2D>, one for each position an elf is standing. Since the ground is (seemingly) infinite in all directions, and we can’t ever have a collision, all we need is the position of the elves.

// In Day23

private fun parseInput(input: List<String>): Set<Point2D> =
    input.flatMapIndexed { y, row ->
        row.mapIndexedNotNull { x, char ->
            if (char == '#') Point2D(x, y) else null
        }
    }.toSet()

The body of parseInput should look somewhat familiar by now, we’ve used this pattern a few times during Advent of Code. Basically, iterate over every row, and then iterate over every char in the row. It’s important to do these as indexed operations so we get the x and y values as well. We will use mapIndexedNotNull so our inner logic doesn’t have to produce a value when we detect empty space.

While we’re here, let’s createOffsets that we will use later to solve Part One. This is a List containing List<Point2D>, each of which is three elements long. These inner lists represent the North, South, West, and East points. Important: Make sure you don’t mistype this. I spent a while debugging a typo here!. Note that the cardinal direction we want (North, South, West, East) is the first element in each of these lists. That will be helpful later.

// In Day23

private fun createOffsets(): List<List<Point2D>> =
    listOf(
        listOf(Point2D(0, -1), Point2D(-1, -1), Point2D(1, -1)), // N
        listOf(Point2D(0, 1), Point2D(-1, 1), Point2D(1, 1)), // S
        listOf(Point2D(-1, 0), Point2D(-1, -1), Point2D(-1, 1)), // W
        listOf(Point2D(1, 0), Point2D(1, -1), Point2D(1, 1)), // E
    )

We’ll set both of these things aside in startingPositions and nextTurnOffsets respectively.

// In Day23

class Day23(input: List<String>) {

    private val startingPositions = parseInput(input)
    private val nextTurnOffsets: List<List<Point2D>> = createOffsets()

}

⭐ Day 23, Part 1

The puzzle text can be found here.

Time for another new function on Point2D, this time to get all of the neighbors(). We already had cardinalNeighbors, which gives us the North, South, East, and West points. This gives us the eight points surrounding a given point.

// In Point2D

fun neighbors(): Set<Point2D> =
    setOf(
        Point2D(x - 1, y - 1),
        Point2D(x, y - 1),
        Point2D(x + 1, y - 1),
        Point2D(x - 1, y),
        Point2D(x + 1, y),
        Point2D(x - 1, y + 1),
        Point2D(x, y + 1),
        Point2D(x + 1, y + 1)
    )

Now we have enough supporting code to write our playRound function. It takes in a roundNumber so we know which round we’re in, as we need that to figure out which of the nextTurnOffsets to pick each round. the playRound function is an extension function on Set<Point2D> and returns a new Set<Point2D>. I suppose we could have written this as MutableSet<Point2D>.playRound(roundNumber:Int):Unit, but this way seemed more natural.

// In Day23

private fun Set<Point2D>.playRound(roundNumber: Int): Set<Point2D> {
    val nextPositions = this.toMutableSet()
    val movers: Map<Point2D, Point2D> = this
        .filter { elf -> elf.neighbors().any { it in this } }
        .mapNotNull { elf ->
            nextTurnOffsets.indices.map { direction -> nextTurnOffsets[(roundNumber + direction) % 4] }
                .firstNotNullOfOrNull { offsets ->
                    if (offsets.none { offset -> (elf + offset) in this }) elf to (elf + offsets.first())
                    else null
                }
        }.toMap()

    val safeDestinations = movers.values.groupingBy { it }.eachCount().filter { it.value == 1 }.keys
    movers
        .filter { (_, target) -> target in safeDestinations }
        .forEach { (source, target) ->
            nextPositions.remove(source)
            nextPositions.add(target)
        }
    return nextPositions
}

The first thing we do is make a mutable copy of the set which we will call nextPositions. To calculate the movers (elves that move this turn), we use filter to find all of the elves that have any neighbor by checking the neighbors of each elf and if they are in the set or not. IF they are, we’ve found an elf that can move. If not, this elf cannot move as it has no neighbors.

Next, we use mapNotNull to find which direction (if any!) this elf will move. At this point we need to look in every direction and see if that elf can move there or not based on the rules. But the trick is we need to evaluate the nextTurnOffsets in a different order every time. Since indices gives us a convenient 0..3 range, we’ll get the indices of nextTurnOffsets and use the direction (the index we are looking at, 0-3), plus the roundNumber mod 4 to figure out which set of offsets to apply.

Once we know that, we use the oddly named firstNotNullOfOrNull (“return me the first one of these that maps to something that isn’t null, but return null if none of them do”) to figure out which, if any offsets work. If one of them does (because none of them are in the set of points), we return a Pair<Point2D, Point2D> where the first value is the current location of an elf, and the second value is the proposed location of an elf. At the end, this will be a List<Pair<Point2D, Point2D>>, which we’ll turn into a Map<Point2D, Point2D> via toMap.

At this point, movers represents all of the proposed moves. We have to find just the unique ones, so we can use groupingBy on the values in map, combined with eachCount to filter out anything that doesn’t have a single match (one elf wants to move there only). Since we only care about the keys at this point (places we are moving to), we get those and set them aside as safeDestinations.

Now we can manipulate our nextPositions by removing any elf that is moving, and adding the location they are moving to. This leaves in-place any elf that couldn’t move because they had no neighbors at the start, or couldn’t move because all the places they want to move were full, or wanted to move to a contested spot.

Returning the nextPositions gives us the results of a single round of play.

// In Day23

fun solvePart1(): Int {
    val locations = (0 until 10).fold(startingPositions) { carry, round -> carry.playRound(round) }
    val gridSize = ((locations.maxOf { it.x } - locations.minOf { it.x }) + 1) * 
                   ((locations.maxOf { it.y } - locations.minOf { it.y }) + 1)
    return gridSize - locations.size
}

To solve the puzzle, we playRound 10 times, which I’m doing here with a fold. At the end, we calculate the gridSize by finding the minimum and maximum values for x and y in locations that the elves ended up. We subtract the total number of elves from the size of the grid in order to find the number of free spots.

Star earned! Onward!

⭐ Day 23, Part 2

The puzzle text can be found here.

Our playRound function from Part One will do most of the work for us in Part Two. All we need to really do is to play rounds until we get two in a row that are identical. There are a few ways to do this (I experimented with generateSequence but didn’t end up liking how it looked). Today, we’ll solve this with a do/while loop.

// In Day23

fun solvePart2(): Int {
    var thisTurn = startingPositions
    var roundNumber = 0
    do {
        val previousTurn = thisTurn
        thisTurn = previousTurn.playRound(roundNumber++)
    } while (previousTurn != thisTurn)
    return roundNumber
}

For every time through the loop, we compare thisTurn to the previousTurn and stop when they match. We increment the roundNumber every time through, and the extra one at the end (incrementing just before determining we don’t need to loop again) will account for the fact that we zero-index our roundNumber and the puzzle wants one-indexed answers.

Star earned! See you tomorrow!

⭐ Day 23, Part 1

⭐ Day 23, Part 2

Further Reading