Skip to Content

# Advent of Code 2023 - Day 11, in Kotlin - Cosmic Expansion

Kotlin solutions to parts 1 and 2 of Advent of Code 2023, Day 11: 'Cosmic Expansion'

Posted on

We’re almost half-way thought with Advent of Code 2023 and I think it’s been pretty fun so far. Today, we’ll be able to solve both parts with the same solution, which I always enjoy doing when I can.

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

Puzzle Input

Once again, we will take our `input` in as a `List<String>` and parse it directly, so no need to declare it as a property.

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

private val galaxies: List<Point2D> = parseGalaxies(input)
}
``````

To parse our `galaxies` we will look through all of the `input` character by character and create a `List<Point2D>` to hold them all. We could use a `Set<Point2D>` here as well if we wanted.

``````// In Day11

private fun parseGalaxies(input: List<String>): List<Point2D> =
input.flatMapIndexed { y, row ->
row.mapIndexedNotNull { x, c ->
if (c == '#') Point2D(x, y)
else null
}
}
``````

Manhattan Distance

Can you believe we made it all the way to Day 11 without having to calculate the Manhattan Distance between two points? To do this, let’s add a `distanceTo` function to `Point2D` (which I just copied from last year’s implementation of `Point2D`):

``````// In Point2D

fun distanceTo(other: Point2D): Int =
(x - other.x).absoluteValue + (y - other.y).absoluteValue
``````

#### ⭐ Day 11, Part 1

The puzzle text can be found here.

Strategy

Let’s start from what we want first and work backwards on how to get there. We want to end up with our `galaxies` spread out (meaning: a new list of `Point2D` objects to represent where the galaxies are after spreading out).

To get that, we need to know how far in the `x` and `y` dimensions to move them. And to calculate that we need to know for a given value of `x` (or `y`) how many empty columns/rows have happened already.

For example, given this map:

``````..#..
#....
....#
``````

For `x`, we want to know how much to spread each of the galaxies out x-ward. It would be helpful to have an array to map this out for us. So, `[0, 1, 1, 2, 2]` which means the galaxy in the 0th column doesn’t move, the galaxy in the 2nd column moves 1, and the galaxy on the end moves 2. The array represents how many blank columns/rows have happened already given that index. We’ll write this function and call it `findEmptySpace`.

``````// In Day11

private fun findEmptySpace(axis: (Point2D) -> Int): IntArray {
val counts: Set<Int> = galaxies.map(axis).toSet()

return IntArray(counts.max() + 1)
.scanIndexed(if (0 in counts) 0 else 1) { index, acc, _ ->
acc + if (index !in counts) 1 else 0
}.toIntArray()
}
``````

The `findEmptySpace` function works the same way for each of the `x` and `y` dimensions, so we’ll take in a function to tell us which `axis` to use. We `map` over the `galaxies` and pick out each of the `x` or `y` values. Once we have them, we create an `IntArray` to hold all of the offsets and set up a `scan` in order to calculate them. The `scanIndexed` function is like a `fold` that keeps each of the values returned (as opposed to keeping the end result only). This allows us to see the previous value that we just calculated and add 1 to it or not depending on whether our column/row is empty in that index.

Next, we need to actually do the galaxy spreading out. We will take in a `spreadFactor` and default it to 2 (the value needed for part 1) in order to make part 2 easier. The `spreadFactor` is how many multiples of each empty column we’re making.

``````// In Day11

private fun spreadGalaxies(spreadFactor: Int = 2): List<Point2D> {
val xOffsets = findEmptySpace { it.x }
val yOffsets = findEmptySpace { it.y }

return galaxies.map { point ->
Point2D(
x = point.x + (xOffsets[point.x] * (spreadFactor - 1)),
y = point.y + (yOffsets[point.y] * (spreadFactor - 1))
)
}
}
``````

The `spreadGalaxies` function does a `findEmptySpace` for both `x` and `y` values of each galaxy. This gives us an array of offsets for each dimension. We then use those to remap all of the galaxies. The calculation looks a a bit complicated but basically we take the current point and add the total offset for that column/row multiplied by one less than the `spreadFactor`. So for a `spreadFactor` of 2, we have the effect of adding 1 to `x` for each empty column.

At the end of this function we have a `List<Point2D>` representing the new locations of all the `galaxies`.

One of the things that surprises me about the Kotlin Standard Library is the lack of a way to get the Cartesian product of lists. Sure, we could write our own (as we will below) or pull in a dependency (which I generally like to avoid if possible ). I’d really like a comprehensive combinations/permutations/products implementation in the Kotlin Standard Library one of these days.

So let’s write our own. I think we could probably use this again, so we’ll put it in `Extensions.kt` and have it return a generic `Pair`. I originally wrote this to take a lambda to perform the operation on the two elements but figured this might be easier to follow.

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

fun <E> List<E>.cartesianPairs(): List<Pair<E, E>> =
this.flatMapIndexed { index, left ->
this.indices.drop(index).map { right -> left to this[right] }
}
``````

There are a lot of algorithms to pair up items, and the one I wrote looks all of the elements by `index`, sets up a range of `indicies` after the current `index` in the list, and then does a `map` of each of those two elements. If we had made `galaxies` a `Set<Point2D>`, we would have to take a different approach to this.

All that’s left to do is solve the puzzle:

``````// In Day11

fun solvePart1(): Int =
spreadGalaxies()
.cartesianPairs()
.sumOf { it.first.distanceTo(it.second) }
``````

First we spread the `galaxies` out with `spreadGalaxies`, create all possible pairs of galaxies, and then get the `sumOf` their distance from one another.

Star earned! Onward!

#### ⭐ Day 11, Part 2

The puzzle text can be found here.

Now you see why we added the `expansion` factor to `spreadGalaxies`?

``````// In Day11

fun solvePart2(expansion: Int): Long =
spreadGalaxies(expansion)
.cartesianPairs()
.sumOf { it.first.distanceTo(it.second).toLong() }
``````

The only differences between parts 1 and 2 are the need for the `expansion` parameter (I wrote a few unit tests and pass in the parameter from them), and the need to convert the distances to `Long` so the `sumOf` won’t wrap over the `Int` limit.

Star earned! See you tomorrow!

#### Further Reading

1. Index of All Solutions - All posts and solutions for 2023, in Kotlin.
2. My Github repo - Solutions and tests for each day.
3. Solution - Full code for day 11
4. Advent of Code - Come join in and do these challenges yourself!