By Eric Burden | December 11, 2023
It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Kotlin. I’ll post my solutions and code to GitHub as well. If you haven’t given AoC a try, I encourage you to do so along with me!
Day 11 - Cosmic Expansion
Find the problem description HERE.
The Input - Galaxy Brain
Back to 2D maps, are we? Well, I came prepared today. I added another input
pre-processing function to read in a 2D grid like this as a List<List<Char>>.
It’s not much, but it’s a nice convenience to have on the front-end. After that,
I think all I’ll need is a list of where the galaxies are and lists of which
rows/columns from the input I need to expand. Let’s get that done.
/**
* This class represents a position on our map of galaxies.
*
* @property row The row of this position.
* @property col The col of this position.
*/
data class Position(val row: Int, val col: Int) {
/**
* Calculate the Manhattan distance between two Positions
*
* @param other The other position to calculate distance to.
* @return The Manhattan distance to the `other` position.
*/
fun manhattanDistanceTo(other: Position): Int {
return abs(row - other.row) + abs(col - other.col)
}
}
/**
* This class represents the map of galaxies from the input
*
* @property galaxies A list of [Position]s of galaxies on the map.
* @property expandedRows A list of the row indices in the map with no galaxies.
* @property expandedCols A list of the column indices in the map with no
* galaxies.
*/
data class GalaxyMap(
val galaxies: List<Position>,
val expandedRows: List<Int>,
val expandedCols: List<Int>
) {
companion object {
/**
* Parse the input file into a [GalaxyMap]
*
* @param input The grid of characters from the input file.
* @return A [GalaxyMap] parsed from the input.
*/
fun fromInput(input: List<List<Char>>): GalaxyMap {
// Every '#' is a galaxy. Everything else is just empty space.
val galaxies = input.withIndex()
.flatMap { (rowIdx, row) ->
row.withIndex().map { (colIdx, char) ->
char to Position(
rowIdx,
colIdx
)
}
}
.filter { (char, _) -> char == '#' }
.map { (_, position) -> position }
// It seemed most straightforward to start with a set of all row
// and column indices, then remove any row or column with a galaxy
// on it.
val expandedRows = input.indices.toMutableSet()
val expandedCols = input.first().indices.toMutableSet()
galaxies.forEach { position ->
expandedRows.remove(position.row)
expandedCols.remove(position.col)
}
// I'm sorting the expanded rows and columns lists here so that I
// can binary search them later for _max velocity_.
return GalaxyMap(
galaxies,
expandedRows.toList().sorted(),
expandedCols.toList().sorted()
)
}
}
}
class Day11(input: List<List<Char>>) {
// Let's map the galaxy!
private val parsed = GalaxyMap.fromInput(input)
}
That wasn’t too painful. I feel like I’m getting more fluent with the available iterator chaining functions from the standard library, which is a nice benefit. Now, let’s map this galaxy for real!
Part One - The One That Got Away
So, I guess we decided we didn’t have time to go track that random robot critter down and… I don’t know, interrogate it about where to find parts? Probably a good call to just move on, but I’m keeping my eye out for that thing to randomly reappear in another puzzle. Probably for us to play dice with or some such. As for the task at hand, it looks like if we can help this elvish astronomer calculate some astronomical distances, he’ll lead us to the hot springs. Sounds like a real winner to me!
import kotlin.math.abs
// data class Position(val row: Int, val col: Int) { ... }
data class GalaxyMap(
val galaxies: List<Position>,
val expandedRows: List<Int>,
val expandedCols: List<Int>
) {
// companion object { ... }
/**
* Count the number of expanded rows between two galaxies
*
* Because the expanded rows are sorted, we can binary search to determine
* how many expanded rows are between two rows that we know aren't in the
* list (because they have galaxies on them).
*
* @param galaxyA The first galaxy in the pair.
* @param galaxyB the other galaxy in the pair.
* @return The number of expanded rows between the pair of galaxies.
*/
private fun expandedRowsBetween(galaxyA: Position, galaxyB: Position): Int =
abs(
expandedRows.binarySearch(galaxyA.row) - expandedRows.binarySearch(
galaxyB.row
)
)
/**
* Count the number of expanded columns between two galaxies
*
* Because the expanded columns are sorted, we can binary search to determine
* how many expanded columns are between two columns that we know aren't in
* the list (because they have galaxies on them).
*
* @param galaxyA The first galaxy in the pair.
* @param galaxyB the other galaxy in the pair.
* @return The number of expanded columns between the pair of galaxies.
*/
private fun expandedColsBetween(galaxyA: Position, galaxyB: Position): Int =
abs(
expandedCols.binarySearch(galaxyA.col) - expandedCols.binarySearch(
galaxyB.col
)
)
/**
* Calculate the real distance between two galaxies
*
* The distance between two galaxies consists of their Manhattan distance
* on the map, plus the expansion of the universe that occurred during
* the time it took the light to travel to our observation point. This
* is accomplished by doubling the "width" of rows and columns without
* any galaxies on them.
*
* @param galaxyA The first galaxy.
* @param galaxyB The second galaxy.
* @return The distance between the two galaxies.
*/
fun distanceBetween(galaxyA: Position, galaxyB: Position): Int {
val observedDistance = galaxyA.manhattanDistanceTo(galaxyB)
val rowExpansions = expandedRowsBetween(galaxyA, galaxyB)
val colExpansions = expandedColsBetween(galaxyA, galaxyB)
// Because each expanded row/columns counts as 2, and because we already
// accounted for each of them once in the `observedDistance`, we just
// add the "extra width" of 1 for each expanded row/column to our final
// distance.
return observedDistance + rowExpansions + colExpansions
}
}
/**
* Returns a sequence of non-repeating pairs of elements in a list
*
* This extension function defines a sequence of pairs of elements from the
* original list such that all unique pairs are generated. For this purpose,
* the pairs (A, B) and (B, A) are considered equivalent.
*
* @return A sequence of non-repeating pairs of elements in [List<T>].
*/
fun <T> List<T>.pairs(): Sequence<Pair<T, T>> =
sequence {
for (i in indices) {
for (j in i + 1 until size) {
yield(this@pairs[i] to this@pairs[j])
}
}
}
class Day11(input: List<List<Char>>) {
// private val parsed = ...
// In part one, the galaxy has a static expansion. Since the "shortest path"
// through empty space is just the distance, calculate the distance between
// all unique pairs of galaxies and return the sum.
fun solvePart1(): Int =
parsed.galaxies.pairs().sumOf { (galaxyA, galaxyB) ->
parsed.distanceBetween(galaxyA, galaxyB)
}
}
I’m not going to lie, I’m a big fan of that extension function on a List<T>
that returns a sequence over that list. I feel like that’s going to come in
handy in future days, so I’m pretty excited to have found it today. Oddly,
or at least, oddly to me, I tried to write an iterator at first, but found I
needed to call .toSequence() on the iterator to include it in a chain of
method calls. I felt like I should have been able to use it without, but maybe
I just misunderstood the difference between iterators and sequences in Kotlin.
More to learn, I guess, which is a good reason to keep going!
Part Two - The Final Frontier
Of course the actual input evaluation is different that we originally thought. At least this time, it’s not because we read the instructions too quickly or failed to look at the back or some other nonsense, it was someone else’s mistake! Sweet vindication! Thankfully, we have everything we need from part one to adapt to this relatively minor change.
import kotlin.math.abs
// data class Position(val row: Int, val col: Int) { ... }
data class GalaxyMap(
val galaxies: List<Position>,
val expandedRows: List<Int>,
val expandedCols: List<Int>
) {
// companion object { ... }
// private fun expandedRowsBetween(
// galaxyA: Position,
// galaxyB: Position
// ): Int = ...
// private fun expandedColsBetween(
// galaxyA: Position,
// galaxyB: Position
// ): Int = ...
// fun distanceBetween(galaxyA: Position, galaxyB: Position): Int { ... }
/**
* Calculate the real distance between two galaxies with variable expansion
*
* The distance between two galaxies consists of their Manhattan distance
* on the map, plus the expansion of the universe that occurred during
* the time it took the light to travel to our observation point. For part
* two, the examples are for smaller levels of expansion than the expected
* answer, so this function accepts the multiple by which the empty rows
* and columns have expanded as a parameter.
*
* @param galaxyA The first galaxy.
* @param galaxyB The second galaxy.
* @param expansionFactor The multiple by which the empty rows/columns have
* expanded.
* @return The distance between the two galaxies.
*/
fun enhancedDistanceBetween(
galaxyA: Position,
galaxyB: Position,
expansionFactor: Int
): Long {
val observedDistance = galaxyA.manhattanDistanceTo(galaxyB)
// We multiply the number of rows/columns by the expansionFactor - 1
// because, once again, the one-wide row/column is already accounted
// for in the `observedDistance`.
val rowExpansions =
expandedRowsBetween(galaxyA, galaxyB) * (expansionFactor - 1)
val colExpansions =
expandedColsBetween(galaxyA, galaxyB) * (expansionFactor - 1)
return observedDistance.toLong() + rowExpansions.toLong() + colExpansions.toLong()
}
}
// fun <T> List<T>.pairs(): Sequence<Pair<T, T>> = ...
class Day11(input: List<List<Char>>) {
// private val parsed = ...
// fun solvePart1(): Int = ...
// In part two, we need to accommodate a variable expansion factor if we want
// to use the same function for testing the example and real inputs (we do
// want to do that, by the way).
fun solvePart2(expansionFactor: Int): Long =
parsed.galaxies.pairs().sumOf { (galaxyA, galaxyB) ->
parsed.enhancedDistanceBetween(galaxyA, galaxyB, expansionFactor)
}
}
This was an interesting part two in that we didn’t actually get an example answer with the real expansion factor. Thankfully, it was straightforward enough to include it as a parameter and calculate the example results and our answer with the same function.
Wrap Up
Today’s puzzle was interesting. Don’t think I didn’t catch all those “shortest distance” references trying to trick me into writing a breadth-first search (or, God forbid, Dijkstra’s!) to find the distance between stars. To be honest, the line in one of the partial examples is what really gave it away. Also, sequences are awesome! Had fun, learned some more Kotlin. What more could you ask for?