Skip to main content

Day 8: Playground

by @mbovel

Puzzle description​

https://adventofcode.com/2025/day/8

Data Model​

To solve this puzzle, we use a class to represent junction boxes:

/** A junction box in 3D space with an associated circuit ID. */
case class Box(val x: Long, val y: Long, val z: Long, var circuit: Int):
  def distanceSquare(other: Box): Long =
    (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y) + (z - other.z) * (z - other.z)

Each Box has:

  • Three coordinates (x, y, z) representing its position in 3D space
  • A mutable circuit field to track which circuit the box belongs to (each circuit is identified by a distinct integer)
  • A distanceSquare method that computes the squared Euclidean distance to another box (we use squared distance to avoid computing square roots, since we only need to compare distances)

Data Loading​

The following functions parse the input into a sequence of boxes and compute all unique pairs sorted by distance:

/** Parses comma-separated coordinates from the given `line` into a `Box`
  * with the given `circuit` ID.
  */
def parseBox(line: String, circuit: Int): Box =
  val parts = line.split(",")
  Box(parts(0).toLong, parts(1).toLong, parts(2).toLong, circuit)

/** Parses the input, returning a sequence of `Box`es and all unique pairs
  * of boxes sorted by distance.
  */
def load(input: String): (Seq[Box], Seq[(Box, Box)]) =
  val lines = input.linesIterator.filter(_.nonEmpty)
  val boxes = lines.zipWithIndex.map(parseBox).toSeq
  val pairsByDistance = boxes.pairs.toSeq.sortBy((b1, b2) => b1.distanceSquare(b2))
  (boxes, pairsByDistance)

The pairs extension method generates all unique pairs from a sequence:

extension [T](self: Seq[T])
  /** Generates all unique pairs (combinations of 2) from the sequence. */
  def pairs: Iterator[(T, T)] =
    self.combinations(2).map(pair => (pair(0), pair(1)))

Part 1​

For Part 1, we process the 1000 closest pairs of boxes and merge their circuits. The algorithm iterates through pairs in order of increasing distance; when two boxes belong to different circuits, we merge them into one. Finally, we find the three largest circuits and return the product of their sizes.

def part1(input: String): Int =
  val (boxes, pairsByDistance) = load(input)
  for (b1, b2) <- pairsByDistance.take(1000) if b1.circuit != b2.circuit do
    merge(b1.circuit, b2.circuit, boxes)
  val sizes = boxes.groupBy(_.circuit).values.map(_.size).toSeq.sortBy(-_)
  sizes.take(3).product

The merge function updates all boxes in one circuit to belong to another:

/** Sets all boxes with circuit `c2` to circuit `c1`. */
def merge(c1: Int, c2: Int, boxes: Seq[Box]): Unit =
  for b <- boxes if b.circuit == c2 do b.circuit = c1

Part 2​

For Part 2, we continue merging circuits until only one remains. We track the number of distinct circuits and return the product of the x-coordinates of the two boxes in the final merge.

def part2(input: String): Long =
  val (boxes, pairsByDistance) = load(input)
  var n = boxes.length
  boundary:
    for (b1, b2) <- pairsByDistance if b1.circuit != b2.circuit do
      merge(b1.circuit, b2.circuit, boxes)
      n -= 1
      if n <= 1 then
        break(b1.x * b2.x)
    throw Exception("Should not reach here")

boundary and break provide a way to exit the loop early and return a value when only one circuit remains.

Potential Optimizations​

On my machine, both parts run in under two seconds, which is acceptable for this puzzle. Still, several optimizations are possible.

What we implemented is essentially the Euclidean minimum spanning tree (EMST) computed via Kruskal’s algorithm, after generating all pairwise distances.

This algorithm is normally paired with a union–find structure to maintain connected components efficiently. Using it would speed up our current merge step, which is O(n)\mathcal{O}(n) per merge, and reduce it to near-constant time.

We could also improve how we find the kk closest pairs. Computing all pairs and sorting them has O(n2log⁡n)\mathcal{O}(n^2 \log n) complexity. A spatial index such as a k-d tree would avoid generating all pairs and, in the average case, remove the quadratic blow-up. Another option is to restrict candidates to a geometric graph such as the relative neighborhood graph or the 3D Delaunay triangulation, both of which contain the EMST and are much sparser than the complete graph.

Final Code​

See the complete code on GitHub.

Run it in the browser​

Thanks to the Scala.js build, you can also experiment with this code directly in the browser.

Part 1​

Part 2​

Solutions from the community​

Share your solution to the Scala community by editing this page. You can even write the whole article! Go here to volunteer