Kotlin
I’m still catching up and this one was hard for me.
First I experimented with implementing a BVH (boundary volume hierarchy) due to three dimensions and possible dense connections between all junction boxes.
I couldn’t get that to work and figured that basically a graph would suffice.
Implementing a simple graph and actually using it, I noticed that I didn’t actually need a graph. The graph was rather slow and I had already calculated all the edges.
So I just kept the shortest ones for part 1. I didn’t even begin with part 2 at that time.
I used sorted sets as a way to keep the shortest connections because I didn’t find a heap; only to find out that a PriorityQueue is a heap.
For part 2 I knew I wouldn’t actually need all connections, so I kept the shortest 12 per junction box and sorted them by length, shortest ones first.
The main idea of part 1 is to build all connections and keeping the shortest one in a heap. That way longer connections can be replaced easily and the longest one is readily available at the root of the heap.
For part 2 instead of building and using all the connections from shortest to longest, this solution keeps only a small number of shortest connections per source junction box. This way the sorting overhead is minimized whilst still solving the solution.
Building the circuits is something else. In order to preserve performance, all junction boxes and their unmerged circuits are represented by a circuit ID in an array. Merging is done by replacing the target/second circuit ID by the first one.
For part 1 this continues until all connections are made. Then the frequencies, bounded to the amount of junction boxes/circuits, are calculated and sorted from largest to smallest. This gives the necessary circuit sizes.
For part 2 instead of merging until all connections are exhausted, the solution needs to check, whether there are any junction boxes not in the merged circuit. Once all junction boxes are in the same circuit, return the last connection made.
A lot of the code requires the input to be consistent and being able to solve the puzzle but that is given.
Code (yes, it's long)
class Day08 : AOCSolution {
override fun part1(inputFile: String): String {
val numConnections = numberOfConnections(inputFile)
val junctionBoxes = readResourceLines(inputFile).map { line ->
val (x, y, z) = line.split(",").map { it.toInt() }
JunctionBox(x, y, z)
}
val connections = buildShortestConnections(junctionBoxes, numConnections)
val circuitSizes = buildCircuitSizes(junctionBoxes, connections)
// Calculate the result as the product of the sizes
// of the three largest circuits
var result = circuitSizes[0]
for (i in 1 until 3) {
result *= circuitSizes[i]
}
return result.toString()
}
override fun part2(inputFile: String): String {
val junctionBoxes = readResourceLines(inputFile).map { line ->
val (x, y, z) = line.split(",").map { it.toInt() }
JunctionBox(x, y, z)
}
val connections = buildHeuristicConnections(junctionBoxes, 12)
val (box1Index, box2Index) = buildCompleteCircuit(junctionBoxes, connections)
val (x1) = junctionBoxes[box1Index]
val (x2) = junctionBoxes[box2Index]
return (x1.toLong() * x2.toLong()).toString()
}
private fun buildShortestConnections(
junctionBoxes: List<JunctionBox>,
connectionLimit: Int
): Queue<Connection> {
val shortestEdges = PriorityQueue<Connection>(connectionLimit)
junctionBoxes.forEachIndexed { index, box ->
for (j in index + 1 until junctionBoxes.size) {
val distance = junctionBoxes[j].distanceSquared(box)
if (shortestEdges.size >= connectionLimit) {
// Keep the set of connections the required size and
// only mutate (remove and add) when a shorter connection is found.
if (distance < shortestEdges.peek().distanceSquared) {
shortestEdges.poll()
shortestEdges.add(Connection(index, j, distance))
}
} else {
shortestEdges.add(Connection(index, j, distance))
}
}
}
return shortestEdges
}
private fun buildHeuristicConnections(
junctionBoxes: List<JunctionBox>,
connectionLimit: Int,
): List<Connection> {
return buildList {
val shortestConnections = PriorityQueue<Connection>(junctionBoxes.size * connectionLimit)
for (fromIndex in 0 until junctionBoxes.lastIndex) {
val from = junctionBoxes[fromIndex]
shortestConnections.clear()
for (toIndex in fromIndex + 1 until minOf(fromIndex + connectionLimit, junctionBoxes.size)) {
val other = junctionBoxes[toIndex]
val distance = from.distanceSquared(other)
shortestConnections.add(Connection(fromIndex, toIndex, distance))
}
// Calculate the remaining distances
for (toIndex in fromIndex + connectionLimit + 1 until junctionBoxes.size) {
val to = junctionBoxes[toIndex]
val distance = from.distanceSquared(to)
if (distance < shortestConnections.peek().distanceSquared) {
// Keep the set of connections the required size and
// only mutate (remove and add) when a shorter connection is found.
shortestConnections.poll()
shortestConnections.add(Connection(fromIndex, toIndex, distance))
}
}
addAll(shortestConnections)
}
// Sort by shortest length first
sortWith { c1, c2 -> c2.compareTo(c1) }
}
}
private fun buildCircuitSizes(
junctionBoxes: List<JunctionBox>,
connections: Iterable<Connection>
): IntArray {
// Array of circuit ids, beginning with each junction box as their own circuit
val circuits = IntArray(junctionBoxes.size) { it }
// Add connections between junction boxes by
// merging the circuits they are in
connections.forEach { (box1, box2) ->
val circuit1 = circuits[box1]
val circuit2 = circuits[box2]
if (circuit1 != circuit2) {
// Merge the circuits
circuits.replaceAll(circuit2, circuit1)
}
}
val sizes = circuits.boundedFrequencies(junctionBoxes.size)
sizes.sortDescending()
return sizes
}
private fun buildCompleteCircuit(
junctionBoxes: List<JunctionBox>,
connections: List<Connection>
): Connection {
// Array of circuit ids, beginning with each junction box as their own circuit
val circuits = IntArray(junctionBoxes.size) { it }
connections.forEach { connection ->
val (box1, box2) = connection
val circuit1 = circuits[box1]
val circuit2 = circuits[box2]
if (circuit1 != circuit2) {
// Merge the circuits
circuits.replaceAll(circuit2, circuit1)
if (circuits.all { it == circuit1 }) {
// We are done, when all circuits are the same
return connection
}
}
}
throw AssertionError()
}
private companion object {
const val NUM_CONNECTIONS_SAMPLE = 10
const val NUM_CONNECTIONS = 1000
private fun numberOfConnections(inputFile: String): Int {
return if (inputFile.endsWith("sample")) {
NUM_CONNECTIONS_SAMPLE
} else {
NUM_CONNECTIONS
}
}
@JvmRecord
private data class JunctionBox(
val x: Int,
val y: Int,
val z: Int,
) {
fun distanceSquared(other: JunctionBox): Long {
val dx = (x - other.x).toLong()
val dy = (y - other.y).toLong()
val dz = (z - other.z).toLong()
return (dx * dx) + (dy * dy) + (dz * dz)
}
}
@JvmRecord
private data class Connection(
val boxIndex1: Int,
val boxIndex2: Int,
val distanceSquared: Long,
) : Comparable<Connection> {
override fun compareTo(other: Connection): Int {
return other.distanceSquared.compareTo(this.distanceSquared)
}
}
private fun IntArray.boundedFrequencies(upperBound: Int): IntArray {
require(this.isNotEmpty())
val frequencies = IntArray(upperBound)
var element = this[0]
var elementCount = 1
for (i in indices) {
val n = this[i]
if (element == n) {
elementCount++
} else {
frequencies[element] += elementCount
element = n
elementCount = 1
}
}
// Add the last run to the frequencies
frequencies[element] += elementCount
return frequencies
}
Kotlin
This one was a journey.
Part 1 is just a greedy search over all the corner pairs to find the largest area.
I began part 2 with just using Java AWT, which worked but was slow. I didn’t want to implement a proper polygon intersection algorithm and found a few patterns in the input.
Basically: All lines are axis aligned and all lines are orthogonal to the lines before and after them. This allows me to easily partition and sort the lists of lines. Because all the lines are axis-aligned and the lines are allowed to be on the edges of the rectangles, a smart check against all the lines can be constructed. Horizontal lines above and below and vertical lines to the left or to the right of the rectangle can be skipped entirely. This cuts the time down tremendously.
I needed to implement a custom binary search, though. The standard lib only supplies a search that gives any element that matches the target, not specifically the first one.
Code on GitHub
Code
class Day09 : AOCSolution { override val year = 2025 override val day = 9 override fun part1(inputFile: String): String { val corners = readCorners(inputFile) var largestRectangle = -1L for (i in 0 until corners.lastIndex) { val firstCorner = corners[i] for (j in i + 1 until corners.size) { largestRectangle = maxOf(largestRectangle, outsideArea(firstCorner, corners[j])) } } return largestRectangle.toString() } override fun part2(inputFile: String): String { val corners = readCorners(inputFile) val (horizontal, vertical) = buildAndPartitionLines(corners) // Sort the lines along their orthogonal axis // Horizontal lines are sorted top to bottom horizontal.sortBy { (from) -> from.y } // Vertical lines are sorted left to right vertical.sortBy { (from) -> from.x } var largestRectangleArea = -1L for (i in 0 until corners.lastIndex) { val first = corners[i] for (j in i + 1 until corners.size) { val second = corners[j] val area = outsideArea(first, second) if (area > largestRectangleArea) { val topLeft = Point(minOf(first.x, second.x), minOf(first.y, second.y)) val bottomRight = Point(maxOf(first.x, second.x), maxOf(first.y, second.y)) if (intersectsNone(horizontal, vertical, topLeft, bottomRight)) { largestRectangleArea = maxOf(largestRectangleArea, area) } } } } return largestRectangleArea.toString() } private companion object { private fun readCorners(inputFile: String): List<Point> { val corners = readResourceLines(inputFile).map { line -> val splitIndex = line.indexOf(',') val x = JavaLong.parseLong(line, 0, splitIndex, 10) val y = JavaLong.parseLong(line, splitIndex + 1, line.length, 10) Point(x, y) } return corners } /** * Builds two lists of lines from connected corners in [corners]. * The corners are required to construct lines that are orthogonal to their * predecessors and successors. * * @return two lists, the first one containing the horizontal lines and * the second one containing the vertical lines. */ private fun buildAndPartitionLines(corners: List<Point>): Pair<Array<Line>, Array<Line>> { require(corners.size >= 2) // Origin point of the next line var from = corners.last() val lines = buildList { corners.forEach { to -> add(Line(from, to)) from = to } } val (horizontal, vertical) = lines.partition { line -> line.from.y == line.to.y } return horizontal.toTypedArray() to vertical.toTypedArray() } private fun outsideArea(a: Point, b: Point): Long { val width = abs(a.x - b.x) + 1 val height = abs(a.y - b.y) + 1 return width * height } /** * Checks whether a rectangle intersects any line in the arrays of horizontal and vertical lines. * * @param horizontal the array of strictly horizontal lines * @param vertical the array of strictly vertical lines * @param topLeft the top-left corner of the rectangle to check * @param bottomRight the bottom-right corner of the rectangle to check * @return whether any of the lines intersect the rectangle */ private fun intersectsNone( horizontal: Array<Line>, vertical: Array<Line>, topLeft: Point, bottomRight: Point ): Boolean { // Find the index of the first horizontal line above the rectangle val beginHorizontal = horizontal.binarySearchFirst( target = topLeft.y ) { (from) -> from.y }.coerceAtLeast(0) for (i in beginHorizontal until horizontal.size) { if (horizontal[i].from.y >= bottomRight.y) { // End early, when encountering the first line on the bottom edge break } if (isLineInsideRect(horizontal[i], topLeft, bottomRight)) { return false } } // Find the index of the first vertical line on the left edge of the rectangle val beginVertical = vertical.binarySearchFirst( target = topLeft.x ) { (from) -> from.x }.coerceAtLeast(0) for (i in beginVertical until vertical.size) { if (vertical[i].from.x >= bottomRight.x) { // End early, when encountering the first line on the right edge break } if (isLineInsideRect(vertical[i], topLeft, bottomRight)) { return false } } return true } /** * Axis-aligned line to rectangle intersection test. * Lines are considered inside, if and only if, they are inside the horizontal * or vertical bounds of the rectangle. * They are not considered inside, if they are on the edges of the rectangle. * @param line the line to check the intersection for * @param topLeft the top-left corner of the rectangle to check * @param bottomRight the bottom-right corner of the rectangle to check * @return whether the line intersects the rectangle */ private fun isLineInsideRect( line: Line, topLeft: Point, bottomRight: Point ): Boolean { val (left, top) = topLeft val (right, bottom) = bottomRight val fromX = line.from.x val toX = line.to.x // Vertical if ((fromX <= left && toX <= left) || (fromX >= right && toX >= right)) { // Line is completely to the left or right of the rectangle return false } val fromY = line.from.y val toY = line.to.y // Horizontal if ((fromY <= top && toY <= top) || (fromY >= bottom && toY >= bottom)) { // Line is completely above or below the rectangle return false } return true } private fun <T> Array<T>.binarySearchFirst( from: Int = 0, to: Int = size, target: Long, extractor: ToLongFunction<T> ): Int { var low = from var high = to - 1 var result = -1 while (low <= high) { val mid = low + ((high - low) / 2) val comparison = extractor.applyAsLong(get(mid)).compareTo(target) if (comparison == 0) { result = mid high = mid - 1 } else if (comparison < 0) { low = mid + 1 } else { high = mid - 1 } } return result } } }