Advent of Code 2023 - Day 11, in Kotlin - Cosmic Expansion • Todd Ginsberg

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!

⭐ Day 11, Part 1

⭐ Day 11, Part 2

Further Reading