# Advent of Code 2022 - Day 23, in Kotlin - Unstable Diffusion

Kotlin solutions to parts 1 and 2 of Advent of Code 2022, Day 23: 'Unstable Diffusion'

Posted on

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)
}
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!