Nim

::: spoiler view code

type
  AOCSolution[T,U] = tuple[part1: T, part2: U]
  Vec3 = tuple[x,y,z: int]
  Node = ref object
    pos: Vec3
    cid: int

proc dist(a,b: Vec3): float =
  sqrt(float((a.x-b.x)^2 + (a.y-b.y)^2 + (a.z-b.z)^2))

proc solve(input: string, p1_limit: int): AOCSolution[int, int] =
  let boxes = input.splitLines().mapIt:
    let parts = it.split(',')
    let pos = Vec3 (parseInt parts[0], parseInt parts[1], parseInt parts[2])
    Node(pos: pos, cid: -1)

  var dists: seq[(float, (Node, Node))]
  for i in 0 .. boxes.high - 1:
    for j in i+1 .. boxes.high:
      dists.add (dist(boxes[i].pos, boxes[j].pos), (boxes[i], boxes[j]))

  var curcuits: Table[int, HashSet[Node]]
  var curcuitID = 0

  dists.sort(cmp = proc(a,b: (float, (Node, Node))): int = cmp(a[0], b[0]))

  for ind, (d, nodes) in dists:
    var (a, b) = nodes
    let (acid, bcid) = (a.cid, b.cid)

    if acid == -1 and bcid == -1: # new curcuit
      a.cid = curcuitID
      b.cid = curcuitID
      curcuits[curcuitId] = [a, b].toHashSet
      inc curcuitID
    elif bcid == -1: # add to a
      b.cid = acid
      curcuits[acid].incl b
    elif acid == -1: # add to b
      a.cid = bcid
      curcuits[bcid].incl a
    elif acid != bcid: # merge two curcuits
      for node in curcuits[bcid]:
        node.cid = acid
      curcuits[acid].incl curcuits[bcid]
      curcuits.del bcid

    if ind+1 == p1_limit:
      result.part1 = curcuits.values.toseq.map(len).sorted()[^3..^1].prod

    if not(acid == bcid and acid != -1): result.part2 = a.pos.x * b.pos.x

:::

Runtime: 364 ms

Part 1:
I compute all pairs of Euclidean distances between 3D points, sort them, then connect points into circuits, using, what I think is called a Union‑Find algorithm (circuits grow or merge). After exactly 1000 connections (including redundant ones), I take the three largest circuits and multiply their sizes.

Part 2:
While iterating through the sorted connections, I also calculate the product of each pair x‑coordinates. The last product is a result for part 2.

Problems I encountered while doing this puzzle:

• I've changed a dozen of data structures, before settled on curcuitIDs and ref objects stored in a HashTable (~ 40 min)
• I did a silly mistake of mutating the fields of an object and then using new fields as keys for the HashTable (~ 20 min)
• I am stil confused and don't understand why do elves count already connected junction boxes (~ 40 min, had to look it up, otherwise it would be a lot more)

Time to solve Part 1: 1 hour 56 minutes
Time to solve Part 2: 4 minutes

Full solution at Codeberg: solution.nim

Uiua

Just a messy part1 so far. Plus a moment of pure rage when I realised the trap. (I have no idea what algorithm Lemmy uses to highlight Uiua code, but it's always a surprise.)

(edit: part 2 now added. I had a stupid error earlier. Takes 12s native or 20+s in the pad.)

::: spoiler Stupid error I added elements just until the set first hit size 1, rather than continuing until total number of elements equalled number of points. :::

Run it here(for what it's worth)

# AOC 2025 Day 08
"162,817,812\n57,618,57\n906,360,560\n592,479,940\n352,342,300\n466,668,158\n542,29,236\n431,825,988\n739,650,466\n52,470,668\n216,146,977\n819,987,18\n117,168,530\n805,96,715\n346,949,466\n970,615,88\n941,993,340\n862,61,35\n984,92,344\n425,690,689"
N ← 10
L ← 20
# &fras"AOC2025day08.txt"◌ # Uncomment these three lines,
# N ← 1000                 # drop your file onto this pane and correct that
# L ← 1000                 # filename, to run this against your data.
# You will need to change settings>execution time to 30s or more.

Row ← (
  ⊙(⊃⊢↘₁)
  ⊚◡≡⌟◇(/+˜∊)
  ⨬(⊂⊙□◌                     # Not found: new circuit
  | ⍜⊡(⍜°□(◴⊂))⊢             # One found: add
  | ▽>₀⊸≡◇⧻⍜(⊏|⊂{[]}{∘}◴/◇⊂) # Connect two
  )⊸⧻◴
)
Parse     ← ⍆⋕°csv
Sort      ← ⊏⍏/+ⁿ2/-⊸⍉⊸⧅>2
IndexPrep ← {[°⊟]}⊸°⊂⊸≡⌟₁˜⨂
Part₁     ← ⊙◌/×↙3⇌⍆≡◇⧻⍥Row(-1N)
Part₂     ← /×⊢⍉⊏⊣↘¯⧻◌⍢(Row|<L/+≡◇⧻)

⊃(&p⍜nowPart₁)(&p⍜nowPart₂) &p⍜now(IndexPrep Sort Parse)

Kotlin

First tricky puzzle today, instantly leading me to more or less brute force for part2. I took a lot of time to understand which data structures I needed today, and how to compute my matrix.

Runtimes:
part1: 141ms
part2: 45.9 seconds .-.

::: spoiler Solution

class Day08 : Puzzle {

    lateinit var boxes: List<Point3D>
    lateinit var edges: List<Pair<List<Point3D>, Double>>

    override fun readFile() {
        val input = readInputFromFile(2025, 8, false)
        boxes = input.lines().filter { it.isNotBlank() }
            .map { it.split(",") }
            .map { Point3D(it[0].toInt(), it[1].toInt(), it[2].toInt()) }
        edges = calculateEdges(boxes)
    }

    private fun calculateEdges(boxes: List<Point3D>): List<Pair<List<Point3D>, Double>> {
        val edges = mutableListOf<Pair<MutableList<Point3D>, Double>>()
        for (i in boxes.indices) {
            for (j in i + 1 until boxes.size) {
                edges.add(Pair(mutableListOf(boxes[i], boxes[j]), boxes[i].dist(boxes[j])))
            }
        }
        return edges.sortedBy { it.second }
    }

    override fun solvePartOne(): String {
        val connections = buildEmptyConnectionMatrix(boxes.size)
        val mutableEdges = edges.toMutableList()
        for (i in 0..<1000) {
            connectNextEdge(mutableEdges, connections)
        }

        val connectionSet = buildConnectionSet(boxes, connections)

        return connectionSet.map { it.size }
            .sortedByDescending { it }
            .take(3)
            .reduce(Int::times)
            .toString()
    }

    override fun solvePartTwo(): String {
        val connections = buildEmptyConnectionMatrix(boxes.size)
        val mutableEdges = edges.toMutableList()

        var result: Long? = null
        while (result == null) {
            result = connectNextEdge(mutableEdges, connections, true)
        }

        return result.toString()
    }

    // size: width & height of (square) matrix
    private fun buildEmptyConnectionMatrix(size: Int): Array<Array<Boolean>> {
        val connections = Array(size) { Array(size) { false } }
        for (i in connections.indices) {
            connections[i][i] = true
        }
        return connections
    }

    private fun connectNextEdge(mutableEdges: MutableList<Pair<List<Point3D>, Double>>, connections: Array<Array<Boolean>>, part2: Boolean = false): Long? {
        if (mutableEdges.isEmpty()) return null
        val next = mutableEdges[0]

        val point = next.first[0]
        val other = next.first[1]
        connectAll(boxes.indexOf(point), boxes.indexOf(other), connections)
        mutableEdges.remove(next)

        // all nodes are connected, assume that this is happening for the first time
        return if (part2 && connections[0].all { it }) {
            next.first[0].x.toLong() * next.first[1].x.toLong()
        } else {
            null
        }
    }

    private fun connectAll(index: Int, other: Int, connections: Array<Array<Boolean>>) {
        fun connectHelper(hIndex: Int) {
            val newConnections = mutableSetOf<Int>()
            for (i in connections[hIndex].indices) {
                if (connections[hIndex][i]) newConnections.add(i)
            }
            for (boxIndex in newConnections.filter { it != hIndex }) {
                for (conn in newConnections.filter { it != boxIndex }) {
                    connections[boxIndex][conn] = true
                }
            }
        }
        connections[index][other] = true

        connectHelper(index) // update matrix with all values from node at [index]
        connectHelper(other) // update matrix with all values from node at [other]
    }

    // returns 2D-list of all indices of currently active connections
    private fun buildConnectionSet(boxes: List<Point3D>, connections: Array<Array<Boolean>>): Set<List<Int>> {
        val connectionSet = mutableSetOf<List<Int>>()
        val indices = (0 until boxes.size).toMutableList()
        while (indices.isNotEmpty()) {
            val list = mutableListOf<Int>()
            val curr = indices.removeFirst()
            val array = connections[curr]
            for (j in array.indices) {
                if (array[j]) list.add(j)
            }
            connectionSet.add(list)
        }
        return connectionSet
    }

    data class Point3D(val x: Int, val y: Int, val z: Int) {
        fun dist(other: Point3D): Double {
            return sqrt(
                (x - other.x).toDouble().pow(2) +
                        (y - other.y).toDouble().pow(2) +
                        (z - other.z).toDouble().pow(2)
            )
        }
    }
}

:::

full code on Codeberg

Futhark

As always, futhark does not support arbitrary inputs, so I have a sed script to transform the input to something readable.

::: spoiler input transformer it produces a textual representation of [][3]u32, try it on your example or input :]

1i [
1,$ {
	s/^/[/
	s/$/]/
}
2,$i,
$i ]
$d

:::

Calculate all the distances (even the redundant ones, I had no idea on how to filter them out). Sort them, keep only the first 1000 for part 1. Keep all for part two. Initialize all boxes to be in no component. Add them to components as time goes on. When connecting two boxes already in a component. Mark all boxes in the second component as part of the first one. Stop when everything is connected.

After improving my implementation of concatMap (preallocate the entire array), the overall performance improved greatly. My end stats are

• Time: 7s -> 0.35s
• Memory: 2GB -> 66MB

::: spoiler Program Source

Basic

import "lib/github.com/diku-dk/sorts/radix_sort"

type position = (u32, u32, u32)
def positionFromArray (p: [3]u32): position
  = (p[0], p[1], p[2])
def pair_iota (n: i64): [n](i64, i64)
  = map (\ j -> (n, j)) (iota n)
def gaussian_sum (n: i64) = n * (n + 1) / 2

def euclidean_distance (a: position) (b: position): f64
  = f64.sqrt 
    ( (f64.u32 a.0 - f64.u32 b.0) ** 2
    + (f64.u32 a.1 - f64.u32 b.1) ** 2
    + (f64.u32 a.2 - f64.u32 b.2) ** 2
    )

def distance_table [n] (positions: [n]position): [n][n]f64
  = let distance_function = \ i j -> euclidean_distance positions[i] positions[j] in
    tabulate_2d n n distance_function

def existsLength 'a 'b (f: a -> ?[l].[l]b) (x: a): i64
  = length (f x)

def concatMap [n] 'a 'b (f: a -> ?[l].[l]b) (placeholder: b) (xs: [n]a): *[]b
  = let totalLength = reduce (+) 0 <| map (\ x -> length (f x)) xs in
    ( loop (results, offset) = (replicate totalLength placeholder, 0)
      for x in xs
      do
        let bs = f x in
        let scatterIndices = indices bs |> map (+offset) in
        (scatter results scatterIndices bs, offset + length bs)
    ).0

def distance_array [n] (positions: [n]position): []((i64, i64), f64)
  = let table = distance_table positions in
    let triangle_indices = concatMap pair_iota (i64.highest, i64.highest) (iota n |> drop 1) in
    map (\ (i, j) -> ((i, j), table[i, j])) triangle_indices

def sort_distances (distances: []((i64, i64), f64)): []((i64, i64), f64)
  = radix_sort_float_by_key (.1) f64.num_bits f64.get_bit distances

type option 'a
  = #Empty
  | #Present a

def empty 'a : option a = #Empty

def overrideWith (old: u16) (new: u16) (x: option u16): option u16
  = match x
      case #Empty -> #Empty
      case #Present inner -> 
        if inner == old
        then #Present new
        else #Present inner

def orElse 'a (o: option a) (d: a): a
  = match o
      case #Empty -> d
      case #Present x -> x

def is_present 'a (o: option a): bool
  = match o
      case #Empty -> false
      case #Present _ -> true

def connect (circuits: *[](option u16)) (newCircuitId: u16) (connection: (i64, i64)): (u16, *[](option u16))
  = let circuitA = circuits[connection.0] in
    let circuitB = circuits[connection.1] in
    match (circuitA, circuitB)
      case (#Empty, #Empty) -> 
        ( newCircuitId + 1
        , scatter circuits [connection.0, connection.1] (rep (#Present newCircuitId))
        )
      case (#Present a, #Empty) -> 
        ( newCircuitId
        , scatter circuits [connection.1] [#Present a]
        )
      case (#Empty, #Present b) -> 
        ( newCircuitId
        , scatter circuits [connection.0] [#Present b]
        )
      case (#Present a, #Present b) ->
        ( newCircuitId
        , map (b `overrideWith` a) circuits
        )

def countCircuit (counts: *[]u64) (o: option u16): *[]u64 
  = match o
    case #Empty -> counts 
    case #Present i -> scatter counts [i64.u16 i] [counts[i64.u16 i] + 1]

def countCircuits (c: u16) (circuits: [](option u16)): *[i64.u16 c]u64
  = let circuitCounts = replicate (i64.u16 c) 0 in
    loop counts = circuitCounts
    for circuit in circuits
    do countCircuit counts circuit

def exampleConnectionCount = 10i64
def inputConnectionCount = 1000i64

def part1 (positions: i64) (connectionCount: i64) (distances: []((i64, i64), f64))
  = let connections = take connectionCount distances |> map (.0) in
    let circuitMap: *[positions](option u16) = replicate positions empty in
    ( loop (circuitCount, circuits) = (0, circuitMap)
      for connection in connections
      do
        connect circuits circuitCount connection
    ) |> uncurry countCircuits 
      |> radix_sort u64.num_bits u64.get_bit
      |> reverse
      |> take 3
      |> foldl (*) 1

def part2 (positionCount: i64) (distances: []((i64, i64), f64)) (positions: []position)
  = let circuitMap: *[positionCount](option u16) = replicate positionCount empty in
    ( loop (circuitCount, connectionIndex, circuits) = (0, 0, circuitMap)
      while not
        ( and (map is_present circuits)
        && and (map (== circuits[0]) circuits)
        )
      do
        let connection = distances[connectionIndex].0 in
        let (newCircuitId, circuits') = connect circuits circuitCount connection in
        (newCircuitId, connectionIndex+1, circuits')
    ).1
    |> \ i -> distances[i-1].0
    |> \ (a, b) -> positions[a].0 * positions[b].0

def main [n] (position_array: [n][3]u32)
  = let positions = map positionFromArray position_array in
    let unsorted_distances = distance_array positions in
    let sorted_distances = sort_distances unsorted_distances in
    ( part1 n inputConnectionCount sorted_distances
    , part2 n sorted_distances positions
    )

:::

Haskell

They're getting interesting now!

import Control.Monad  
import Data.List  
import Data.List.Split  
import Data.Ord  
import Data.Set qualified as Set  

readPos = (\([x, y, z] :: [Int]) -> (x, y, z)) . map read . splitOn ","  

pairs = init . tails >=> (\(x : xs) -> map (x,) xs)  

dist (x1, y1, z1) (x2, y2, z2) =  
  (x2 - x1) ^ 2 + (y2 - y1) ^ 2 + (z2 - z1) ^ 2  

connect circuits (a, b) =  
  let (joined, rest) =  
        partition (\c -> a `Set.member` c || b `Set.member` c) circuits  
   in Set.unions joined : rest  

main = do  
  boxes <- map readPos . lines <$> readFile "input08"  
  let steps =  
        (zip <*> tail . scanl' connect (map Set.singleton boxes)) $  
          sortOn (uncurry dist) (pairs boxes)  
  print . product . take 3 . sortOn Down . map Set.size $  
    (snd . last . take 1000 $ steps)  
  let Just (((x1, _, _), (x2, _, _)), _) =  
        find ((== 1) . length . snd) steps  
   in print $ x1 * x2  

Python

Both of my solutions make use of a Heap and a Disjoint-Set-Union / Union-Find data structure

Part 1: Use a heap to keep 1000 shortest connections, then union them all in DSU and get the 3 largest connected components.
Part 2: Use a heap to keep all connections, then union the shortest ones until all components are connected.

::: spoiler click to view code

import heapq as hq
from itertools import combinations
from collections import Counter

# Disjoint Set Union (or Union-Find) data structure
#   with path compression and union by rank
class DSU:
    def __init__(self, size: int) -> None:
        self.parent = list(range(size)) # ith value is the parent node to node i
        self.rank = [1] * size          # max depth of subtree rooted here (used for union by rank)
        
    def find(self, x: int) -> int:
        # if the node is not its own parent, we need to recurse on parent
        if x != self.parent[x]:
            # path compression
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def isConnected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    
    # returns a boolean whether or not union was needed
    def union(self, x: int, y: int) -> bool:
        rootX = self.find(x)
        rootY = self.find(y)        
        
        if rootX == rootY:
            # no union needed
            return False
        
        if self.rank[rootX] > self.rank[rootY]:
            # rootX has deeper subtree, therefore set it as parent to rootY (and its subtree)
            self.parent[rootY] = rootX
        elif self.rank[rootX] < self.rank[rootY]:
            # rootY has deeper subtree, therefore set it as parent to rootX (and its subtree)
            self.parent[rootX] = rootY
        else:
            # both subtrees are of equal depth, therefore choose either one of them as the parent of the other
            # here we chose rootX as the parent of rootY, therefore rootX depth increases by 1
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
        
        # union complete
        return True

# parse puzzle input into junction coordinates (x, y, z)
def parse_junctions(data: str):
    return [tuple(map(int, line.split(','))) for line in data.splitlines()]

# get distance between two points in 3D space
# skipping the sqrt because we only care about relative distances
def get_dist(p1, p2):
    x1, y1, z1 = p1
    x2, y2, z2 = p2
    return (x2 - x1) ** 2 + (y2 - y1) ** 2 + (z2 - z1) ** 2

def part1(data: str, max_connections: int = 1000):
    junctions = parse_junctions(data)
    n = len(junctions)

    # <max_connections> shortest connections
    closest_connections = []
    # iterate over all pairs of junctions
    # combinations is just some syntactic sugar to avoid a nested for loop (still O(n^2))
    for i, j in combinations(range(n), 2):
        dist = get_dist(junctions[i], junctions[j])
        # keep <max_connections> closest connections
        #   have to use -dist to simulate max heap
        if len(closest_connections) < max_connections:
            hq.heappush(closest_connections, (-dist, i, j))
        else:
            hq.heappushpop(closest_connections, (-dist, i, j))

    # union all the closest connections
    dsu = DSU(n)
    for _, i, j in closest_connections:
        dsu.union(i, j)

    # count all circuit sizes
    circuit_sizes = Counter()
    for i in range(n):
        circuit_sizes[dsu.find(i)] += 1

    # multiply the sizes of the 3 largest circuits
    ans = 1
    for _, f in circuit_sizes.most_common(3):
        ans *= f
    return ans

def part2(data: str):
    junctions = parse_junctions(data)
    n = len(junctions)

    # all n^2 junction connections
    all_connections = []
    # combinations is just some syntactic sugar to avoid a nested for loop (still O(n^2))
    for i, j in combinations(range(n), 2):
        dist = get_dist(junctions[i], junctions[j])
        all_connections.append((dist, i, j))
    
    # create min heap of all connections
    # Heapify later to benefit from the heapify algorithm (O(n) instead of O(n log n))
    hq.heapify(all_connections)
    
    # connect junctions until all are connected
    dsu = DSU(n)
    unions = 0
    while all_connections:
        _, i, j = hq.heappop(all_connections)
        unions += dsu.union(i, j)
        # if we have n-1 unions, that means all n junctions are connected
        if unions == n-1:
            return junctions[i][0] * junctions[j][0]
    
    assert False, "It's not possible that all junctions never connect"

sample = """162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689"""
assert part1(sample, max_connections=10) == 40
assert part2(sample) == 25272

:::

Haskell

import Control.Arrow
import Control.Monad
import Data.Char
import Data.List
import Data.Maybe
import Data.Ord
import Text.ParserCombinators.ReadP

import Data.Array.Unboxed qualified as A
import Data.Map.Strict qualified as M

parse = fst . last . readP_to_S (endBy (sepBy (read <$> munch1 isDigit) (char ',')) (char '\n'))

sortedPairs l = sortOn dist [(x, y) | (x : ys) <- tails l, y <- ys]
  where
    dist = uncurry $ (sum .) . zipWith (\a b -> (b - a) ^ 2)

merge l = scanl' f (initialAssocs, initialSizes)
  where
    f s@(assocs, sizes) (a, b) = case compare ia ib of
        GT -> f s (b, a)
        LT ->
            ( M.map (\x -> if x == ib then ia else x) assocs
            , sizes A.// [(ib, 0), (ia, (sizes A.! ia) + (sizes A.! ib))]
            )
        EQ -> s
      where
        (ia, ib) = (assocs M.! a, assocs M.! b)

    initialAssocs = M.fromList $ zip l [1 ..]
    initialSizes = A.listArray (1, length l) $ repeat 1 :: A.UArray Int Int

main = do
    contents <- parse <$> getContents
    let pairs = sortedPairs contents
        merged = merge contents pairs
        n = findIndex ((== length contents) . (A.! 1) . snd) merged

    print $ product . take 3 . sortBy (comparing Down) . A.elems . snd <$> merged !? 1000
    print $ uncurry (*) . (head *** head) . (pairs !!) . pred <$> n

Rust

It's getting spicier, luckily part 2 wasn't really much additional complexity this time. There exists a pretty fancy union-find data structure which would have made representing the subcircuits much faster, but I went with a lazy approach.

View on github

::: spoiler Code

use euclid::default::Point3D;
use euclid::point3;

fn parse_input(input: &str) -> Vec<Point3D<i64>> {
    input
        .lines()
        .map(|l| {
            let mut parts = l.split(',').map(|p| p.parse::<i64>().unwrap());
            let (x, y, z) = (
                parts.next().unwrap(),
                parts.next().unwrap(),
                parts.next().unwrap(),
            );
            point3(x, y, z)
        })
        .collect()
}

// Distances between all points. Reflexive and symmetric pairs are skipped,
// so the Vec's have increasing size, starting at 0.
fn dists(points: &[Point3D<i64>]) -> Vec<Vec<i64>> {
    points
        .iter()
        .enumerate()
        .map(|(idx, &p1)| {
            points
                .iter()
                .take(idx)
                .map(|&p2| (p2 - p1).square_length())
                .collect::<Vec<i64>>()
        })
        .collect()
}

fn sorted_distances(dists: &[Vec<i64>]) -> Vec<(usize, usize, i64)> {
    let mut sorted: Vec<(usize, usize, i64)> = dists
        .iter()
        .enumerate()
        .flat_map(|(i, row)| row.iter().enumerate().map(move |(j, d)| (i, j, *d)))
        .collect();
    sorted.sort_by_key(|(_, _, d)| *d);
    sorted
}

fn part1(input: String) {
    let points = parse_input(&input);
    let d = dists(&points);
    let sorted = sorted_distances(&d);

    let mut circuits: Vec<u32> = (0..points.len() as u32).collect();
    for (i, j, _) in sorted.into_iter().take(1000) {
        let new_circuit = circuits[i];
        let old_circuit = circuits[j];
        if new_circuit != old_circuit {
            for c in circuits.iter_mut() {
                if *c == old_circuit {
                    *c = new_circuit;
                }
            }
        }
    }
    let mut sizes: Vec<u32> = vec![0; points.len()];
    for c in circuits {
        sizes[c as usize] += 1
    }
    sizes.sort_unstable();
    let result = sizes.iter().rev().take(3).product::<u32>();
    println!("{result}");
}

fn part2(input: String) {
    let points = parse_input(&input);
    let d = dists(&points);
    let sorted = sorted_distances(&d);

    let mut circuits: Vec<u32> = (0..points.len() as u32).collect();
    for (i, j, _) in sorted.into_iter() {
        let new_circuit = circuits[i];
        let old_circuit = circuits[j];
        if new_circuit != old_circuit {
            let mut all_connected = true;
            for c in circuits.iter_mut() {
                if *c == old_circuit {
                    *c = new_circuit;
                }
                if *c != new_circuit {
                    all_connected = false;
                }
            }
            if all_connected {
                let result = points[i].x * points[j].x;
                println!("{result}");
                return;
            }
        }
    }
}

util::aoc_main!();

:::

C++

Both parts in 40 ms. As always, the real AoC with C++ is parsing the input, although having a number that changes in the puzzle messes up my test/ solution runners.

Uses Boost's implementations of sets, since they're just plain faster than the STL ones.

::: spoiler Code

#include <boost/log/trivial.hpp>
#include <boost/unordered/unordered_flat_set.hpp>
#include <filesystem>
#include <fstream>
#include <stdexcept>

namespace {

struct Point {
  int x, y, z;
};

auto distance(const Point &a, const Point &b) {
  auto &[ax, ay, az] = a;
  auto &[bx, by, bz] = b;
  ssize_t dx = ax - bx;
  ssize_t dy = ay - by;
  ssize_t dz = az - bz;
  return size_t(dx * dx + dy * dy + dz * dz);
}

using PList = std::vector<Point>;
using DMap = std::vector<std::pair<std::pair<size_t, size_t>, size_t>>;
using DSet = boost::unordered::unordered_flat_set<size_t>;

auto read() {
  auto rval = PList{};
  auto ih = std::ifstream{"08.txt"};
  auto line = std::string{};
  while (std::getline(ih, line)) {
    auto c1 = line.find(',');
    auto c2 = line.find(',', c1 + 1);
    rval.emplace_back(
        std::stoi(line.substr(0, c1)),
        std::stoi(line.substr(c1 + 1, c2 - c1 - 1)),
        std::stoi(line.substr(c2 + 1))
    );
  }
  return rval;
}

auto dmap(const PList &t) {
  auto rval = DMap{};
  for (auto a = size_t{}; a < t.size() - 1; ++a)
    for (auto b = a + 1; b < t.size(); ++b)
      rval.emplace_back(std::make_pair(a, b), distance(t.at(a), t.at(b)));
  return rval;
}

auto find(size_t c, std::vector<DSet> &sets) {
  for (auto i = sets.begin(); i != sets.end(); ++i)
    if (i->contains(c))
      return i;
  throw std::runtime_error{"can't find"};
}

auto part1(const PList &t, size_t count, const DMap &d) {
  auto circuits = std::vector<DSet>{};
  for (auto i = size_t{}; i < t.size(); ++i) {
    auto c = DSet{t.size()};
    c.insert(i);
    circuits.push_back(std::move(c));
  }

  for (auto i = size_t{}; i < count; ++i) {
    auto a = d.at(i).first.first;
    auto b = d.at(i).first.second;
    auto ac = find(a, circuits);
    auto bc = find(b, circuits);
    if (ac == bc)
      continue;
    ac->insert(bc->begin(), bc->end());
    circuits.erase(bc);
  }

  std::sort(circuits.begin(), circuits.end(), [](auto &a, auto &b) {
    return a.size() > b.size();
  });
  auto total = size_t{1};
  for (auto i = size_t{}; i < 3; ++i)
    total *= circuits.at(i).size();

  return total;
}

auto part2(const PList &t, const DMap &d) {
  auto circuits = std::vector<DSet>{};
  for (auto i = size_t{}; i < t.size(); ++i) {
    auto c = DSet{t.size()};
    c.insert(i);
    circuits.push_back(std::move(c));
  }

  for (auto i = size_t{}; i < d.size(); ++i) {
    auto a = d.at(i).first.first;
    auto b = d.at(i).first.second;
    auto ac = find(a, circuits);
    auto bc = find(b, circuits);
    if (ac == bc)
      continue;
    ac->insert(bc->begin(), bc->end());
    circuits.erase(bc);
    if (circuits.size() == 1) {
      return ssize_t(t.at(a).x) * ssize_t(t.at(b).x);
    }
  }
  throw std::runtime_error{"never joins?"};
}

} // namespace

auto main() -> int {
  auto t = read();
  BOOST_LOG_TRIVIAL(info) << "Day 8: read " << t.size();
  auto test = std::filesystem::current_path().filename().string() ==
              std::string{"test"};

  auto d = dmap(t);
  std::sort(d.begin(), d.end(), [](auto &a, auto &b) {
    return a.second < b.second;
  });

  BOOST_LOG_TRIVIAL(info) << "1: " << part1(t, test ? 10 : 1000, d);
  BOOST_LOG_TRIVIAL(info) << "2: " << part2(t, d);
}

:::

I went here for graphs (to find connected components) and binary search (for efficiency)

#!/usr/bin/env python3
from pathlib import Path

import numpy as np
import networkx as nx

cwd = Path(__file__).parent.resolve()


def parse_input(file_path):
  with file_path.open("r") as fp:
    coords = list(map(lambda x: list(map(int, x.split(','))), fp.readlines()))

  return np.array(coords)


def binary_search(G, dist):

  Itriu = np.triu_indices(dist.shape[0], k=1)
  dist = dist[Itriu]

  components = list(nx.connected_components(G))
  Isort = [(Itriu[0][i], Itriu[1][i]) for i in np.argsort(dist)]

  icurrent =  0
  ihist = []
  nhist =  []

  while len(ihist)<2 or ihist[-1]!=ihist[-2]:

    ihist.append(icurrent)
    G.add_edges_from(Isort[:icurrent])
    components = list(nx.connected_components(G))
    nhist.append(len(components))

    G.remove_edges_from(Isort[:icurrent])

    if len(components)>1:
      # if >1 component, go between this and closest next index with 1 component
      I = [ind for ind,n in enumerate(nhist) if n==1]

      if len(I)==0:
        inext = len(Isort)
      else:
        inext = min(np.array(ihist)[I])

      icurrent = icurrent + int(np.ceil((inext-icurrent)/2))

    else: 
      # if 1 component, go between nearest previous >1 components and this index
      I = [ind for ind,n in enumerate(nhist) if n>1]

      if len(I)==0:
        iprev = 0
      else:
        iprev = max(np.array(ihist)[I])

      icurrent = iprev + int(np.ceil((icurrent-iprev)/2))

  return Isort[icurrent-1]


def solve_problem(file_name, nconnect):

  coordinates = parse_input(Path(cwd, file_name))
  G = nx.Graph()
  G.add_nodes_from(range(coordinates.shape[0]))

  dist = np.sqrt(np.sum((coordinates[None,:] - coordinates[:,None])**2,
                        axis=-1))

  if nconnect != -1: # part 1
    Itriu = np.triu_indices(dist.shape[0], k=1)
    dist = dist[Itriu]
    Isort = [(Itriu[0][i], Itriu[1][i]) for i in np.argsort(dist)[:nconnect]]

    G.add_edges_from(Isort)
    components = sorted(list(nx.connected_components(G)), key=len)[::-1]

    return np.prod(list(map(len, components[:3])))
  else: # part 2
    indices = binary_search(G, dist)
    return np.prod(coordinates[indices,:],axis=0)[0]


if __name__ == "__main__":

  assert solve_problem("test_input", 10) == 40
  assert solve_problem("input", 1000) == 115885
  assert solve_problem("test_input", -1) == 25272
  assert solve_problem("input", -1) == 274150525

C

Got stuck for a bit on part 1 on a silly mistake in the group (circuit) merging code, where the nodes from one group are reassigned to the other:

for (i=0; i < nnodes; i++)
        if (nodes[i].group == pair->b->group)
                nodes[i].group = pair->a->group;

At some point in the loop pair->b.group itself is updated, from then on the check is against the new group value. Oops.

In the end, my solution's runtime on my (10 year old!) PC is about 160 ms for both parts, which is more than I would like, so maybe I'll look into better set representations.

::: spoiler Code

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <assert.h>

#define LEN(a)		(sizeof(a)/sizeof(*(a)))
#define NPAIRS(x)	((x)*((x)-1)/2)

#define MAXN	1024

struct node { int x,y,z, group; };
struct pair { struct node *a, *b; int64_t dist_sq; };
struct group { int count; };

static struct node nodes[MAXN];
static struct pair pairs[NPAIRS(MAXN)];
static struct group groups[MAXN];

static int nnodes;
static int ngroups;

static int64_t
node_dist_sq(const struct node *a, const struct node *b)
{
	return
	    (int64_t)(a->x - b->x) * (a->x - b->x) +
	    (int64_t)(a->y - b->y) * (a->y - b->y) +
	    (int64_t)(a->z - b->z) * (a->z - b->z);
}

static int
cmp_pairs(const void *va, const void *vb)
{
	const struct pair *a = va;
	const struct pair *b = vb;

	return
	    a->dist_sq < b->dist_sq ? -1 :
	    a->dist_sq > b->dist_sq ?  1 : 0;
}

static int
cmp_groups_asc(const void *va, const void *vb)
{
	const struct group *a = va;
	const struct group *b = vb;

	return b->count - a->count;
}

static void
merge_groups(int group_a, int group_b)
{
	int i;

	if (group_a == group_b)
		return;

	groups[group_a].count += groups[group_b].count;
	groups[group_b].count = 0;

	for (i=0; i<nnodes; i++)
		if (nodes[i].group == group_b)
			nodes[i].group = group_a;
	
	ngroups--;
}

int
main()
{
	int p1=0,p2=0, p1_limit, i,j, n,p;

	for (; ; nnodes++) {
		assert(nnodes < MAXN);
		n = scanf(" %d,%d,%d",
		    &nodes[nnodes].x,
		    &nodes[nnodes].y,
		    &nodes[nnodes].z);
		if (n < 3)
			break;
		nodes[nnodes].group = nnodes;
		groups[nnodes].count = 1;
	}

	ngroups = nnodes;

	for (p=0, i=0; i<nnodes-1; i++)
	for (j=i+1; j<nnodes; j++, p++) {
		pairs[p].a = &nodes[i];
		pairs[p].b = &nodes[j];
		pairs[p].dist_sq = node_dist_sq(&nodes[i], &nodes[j]);
	}

	qsort(pairs, NPAIRS(nnodes), sizeof(*pairs), cmp_pairs);

	p1_limit = nnodes <= 100 ? 10 : 1000;

	for (i=0; ngroups > 1; i++) {
		merge_groups(pairs[i].a->group, pairs[i].b->group);

		if (ngroups == 1)
			p2 = pairs[i].a->x * pairs[i].b->x;

		if (i == p1_limit) {
			qsort(groups, LEN(groups), sizeof(*groups),
			    cmp_groups_asc);

			p1 = groups[0].count *
			     groups[1].count *
			     groups[2].count;
		}
	}

	printf("08: %d %d\n", p1, p2);
}

:::

Go

God damn it, I thought I would never see the end of part 1. I had a hard time finding a good representation and then I failed at not eliminating valid distances etc. The code is quite messy, but I did it!!!

::: spoiler day08.go

package main

import (
	"aoc/utils"
	"cmp"
	"math"
	"slices"
	"strconv"
	"strings"
)

type pos3D struct {
	x, y, z int
}

func (p pos3D) Compare(other pos3D) int {
	dx := cmp.Compare(p.x, other.x)
	if dx != 0 {
		return dx
	}

	dy := cmp.Compare(p.y, other.y)
	if dy != 0 {
		return dy
	}

	return cmp.Compare(p.z, other.z)
}

func (p pos3D) distance(other pos3D) float64 {
	dx := float64(other.x - p.x)
	dy := float64(other.y - p.y)
	dz := float64(other.z - p.z)

	d2 := math.Pow(dx, 2.0) + math.Pow(dy, 2.0) + math.Pow(dz, 2.0)
	return math.Sqrt(d2)
}

func getPosChannel(input chan string) chan pos3D {
	ch := make(chan pos3D, cap(input))

	go func() {
		for line := range input {
			parts := strings.Split(line, ",")
			x, _ := strconv.Atoi(parts[0])
			y, _ := strconv.Atoi(parts[1])
			z, _ := strconv.Atoi(parts[2])
			ch <- pos3D{x, y, z}
		}
		close(ch)
	}()

	return ch
}

type circuits struct {
	circuits map[pos3D]int
	nextID   int
}

func (cc *circuits) newCircuit() (id int) {
	id = cc.nextID
	cc.nextID++
	return id
}

func (cc *circuits) mergeCircuits(id1, id2 int) {
	for p, id := range cc.circuits {
		if id == id2 {
			cc.circuits[p] = id1
		}
	}
}

func createSingletonCircuits(points []pos3D) (cc circuits) {
	cc.circuits = make(map[pos3D]int)
	for _, p := range points {
		id := cc.newCircuit()
		cc.circuits[p] = id
	}
	return cc
}

func (cc circuits) reverseMap() (m map[int][]pos3D) {
	m = make(map[int][]pos3D)

	for p, id := range cc.circuits {
		if _, ok := m[id]; !ok {
			m[id] = []pos3D{}
		}

		m[id] = append(m[id], p)
	}

	return m
}

func (cc circuits) sizeMap() map[int]int {
	circuitSizeMap := make(map[int]int)
	for _, id := range cc.circuits {
		circuitSizeMap[id]++
	}
	return circuitSizeMap
}

type targetedDistance struct {
	distance float64
	p1, p2   pos3D
}

func (p pos3D) distanceWithAll(
	points []pos3D,
	alreadyVisited *map[pos3D]any,
) (tds []targetedDistance) {
	tds = []targetedDistance{}
	for _, op := range points {
		if _, ok := (*alreadyVisited)[op]; ok {
			continue
		}

		var td targetedDistance
		td.distance = math.MaxFloat64
		td.p1 = p
		d := p.distance(op)
		if d < td.distance {
			td.distance = d
			td.p2 = op
		}
		tds = append(tds, td)
	}
	return tds
}

type pointPair [2]pos3D

func (pp pointPair) equals(other pointPair) bool {
	pp1 := pp[0]
	pp2 := pp[1]
	o1 := other[0]
	o2 := other[1]
	return (pp1 == o1 && pp2 == o2) || (pp1 == o2 && pp2 == o1)
}

var IterationCount = 1000

func stepOne(input chan string) (int, error) {
	ch := getPosChannel(input)

	points := []pos3D{}
	for p := range ch {
		points = append(points, p)
	}
	slices.SortFunc(points, pos3D.Compare)
	cc := createSingletonCircuits(points)

	alreadyVisited := make(map[pos3D]any)
	tds := []targetedDistance{}
	for _, p := range points {
		alreadyVisited[p] = nil
		dsts := p.distanceWithAll(points, &alreadyVisited)
		tds = append(tds, dsts...)
	}

	slices.SortFunc(tds, func(a, b targetedDistance) int {
		return cmp.Compare(a.distance, b.distance)
	})

	for idx := range IterationCount {
		td := tds[idx]
		cc.mergeCircuits(cc.circuits[td.p1], cc.circuits[td.p2])
	}

	circuitSizeMap := cc.sizeMap()

	circuitSizes := []int{}
	for _, v := range circuitSizeMap {
		circuitSizes = append(circuitSizes, v)
	}
	slices.Sort(circuitSizes)
	largestThree := circuitSizes[len(circuitSizes)-3:]

	product := 1
	for _, v := range largestThree {
		product *= v
	}

	return product, nil
}

func stepTwo(input chan string) (int, error) {
	ch := getPosChannel(input)

	points := []pos3D{}
	for p := range ch {
		points = append(points, p)
	}
	slices.SortFunc(points, pos3D.Compare)
	cc := createSingletonCircuits(points)

	alreadyVisited := make(map[pos3D]any)
	tds := []targetedDistance{}
	for _, p := range points {
		alreadyVisited[p] = nil
		dsts := p.distanceWithAll(points, &alreadyVisited)
		tds = append(tds, dsts...)
	}

	slices.SortFunc(tds, func(a, b targetedDistance) int {
		return cmp.Compare(a.distance, b.distance)
	})

	idx := 0
	var lastConnection pointPair

	for {
		td := tds[idx]
		idx++
		cc.mergeCircuits(cc.circuits[td.p1], cc.circuits[td.p2])

		circuitSizeMap := cc.sizeMap()
		if len(circuitSizeMap) == 1 {
			lastConnection = pointPair{td.p1, td.p2}
			break
		}
	}

	return lastConnection[0].x * lastConnection[1].x, nil
}

func main() {
	inputFile := utils.FilePath("day08.txt")
	utils.RunStep(utils.ONE, inputFile, stepOne)
	utils.RunStep(utils.TWO, inputFile, stepTwo)
}

:::

Uiua

Not really proud of this one. Part 1's still ok, just calculated all distances between boxes after realizing it's not that many (499500, a reasonable amount I think, relatively speaking).
The dumbest thing I did this time was manually implementing the function to take the first n rows of an array by using a loop. Only when I was working on part 2 did I realize that I can just use the "take" function Uiua provides. Additionally, I even had some mistake in my reimplementation of it that only caused issues in part 2 somehow.
For anyone interested, it's the commented out line in P₁ below.
Part 2 is just a brute force. For the actual input, I searched manually until I got to the pair number just before the actual solution because I didn't want it to run that long and it takes long enough as is.

Run with example input

:::spoiler Code

$ 162,817,812
$ 57,618,57
$ 906,360,560
$ 592,479,940
$ 352,342,300
$ 466,668,158
$ 542,29,236
$ 431,825,988
$ 739,650,466
$ 52,470,668
$ 216,146,977
$ 819,987,18
$ 117,168,530
$ 805,96,715
$ 346,949,466
$ 970,615,88
$ 941,993,340
$ 862,61,35
$ 984,92,344
$ 425,690,689

Dist ← ⍜(≡°√)/+⌵-°⊟
Prep ← (
  ⊜(⊜⋕⊸≠@,)⊸≠@\n
  ⧅<2
  ⊏⍏⊸≡Dist
)

Merge ← (
  ⍜♭₂⊛
  {}
  ⍥(⍣(⊙(°⊂
        □⍥(
          ⟜⊸˜≡⌟(>/+⊃⨂(×₂⋅⧻))
          ◴⊂⊙(♭∩⌟▽⟜¬)
        )∞
      )
      ⊂
    | ∘)
  )∞
  ⊙◌
)

P₁ ← (
  Prep
  # ⍥₁₀(⊙⤙⊡°˜⊂)
  ↙₁₀
  Merge
  ⍆≡◇⧻
  /×↙₋₃
)

P₂ ← (
  Prep
  1_0
  ⊸⍢(
    ⍜°˜⊟(
      ⊙+₁
      ⋅⟜↙
      ⊙(Merge
        ◇⧻⊢)
    )
  | <20⊣)
  -₁⊢
  ⊡
  ×°⊟⊡₀⍉
)

[⊃P₁P₂]
≡(&p $"Part _: _") 1_2

:::

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 with comments on GitHub ::: spoiler 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
        }

:::

Unoptimized: 27ms and 32ms
Optimized (100 runs): 4ms and 6.5ms

Rust

Not an easy one, mostly because I messed up my merge circuits function (Pop/remove first circuit, load into second, but the pop/remove messed up the indexes, so I was merging the wrong thing).

After getting that it was all good. Pt2 was trivial once pt1 was solved.

::: spoiler spoiler

    #[derive(Debug)]
    struct Circuits {
        circuits: Vec<Vec<usize>>,
    }

    impl Circuits {
        fn find_circuit(&mut self, i: usize) -> Option<usize> {
            for (j, c) in &mut self.circuits.iter().enumerate() {
                if c.contains(&i) {
                    return Some(j);
                }
            }
            None
        }

        fn new_circuit(&mut self, i: usize, j: usize) {
            self.circuits.push(vec![i, j]);
        }

        fn join_circuits(&mut self, i: usize, j: usize) {
            let mut other = self.circuits.get(j).unwrap().clone();
            self.circuits.get_mut(i).unwrap().append(&mut other);
            self.circuits.remove(j);
        }

        fn append_circuit(&mut self, c: usize, x: usize) {
            self.circuits.get_mut(c).unwrap().push(x);
        }

        fn top_three(&mut self) -> Vec<usize> {
            let mut sizes = self
                .circuits
                .iter()
                .map(|c| c.len())
                .collect::<Vec<usize>>();
            sizes.sort();
            sizes.reverse();
            sizes[0..3].to_vec()
        }
    }

    type Pole = (isize, isize, isize);

    fn dist_poles(p1: &Pole, p2: &Pole) -> f32 {
        sqrt(
            ((p1.0 - p2.0) * (p1.0 - p2.0)) as f32
                + ((p1.1 - p2.1) * (p1.1 - p2.1)) as f32
                + ((p1.2 - p2.2) * (p1.2 - p2.2)) as f32,
        )
    }

    #[test]
    fn test_y2025_day8_part1() {
        let input = include_str!("../../input/2025/day_8.txt");
        let poles = input
            .lines()
            .map(|l| {
                let [x, y, z] = l
                    .splitn(3, ",")
                    .map(|c| c.parse::<isize>().unwrap())
                    .collect::<Vec<isize>>()[..]
                else {
                    panic!();
                };
                (x, y, z)
            })
            .collect::<Vec<Pole>>();
        let len = poles.len();

        let mut circuits: Circuits = Circuits { circuits: vec![] };

        let mut pairs = vec![];

        for i in 0..len {
            let first = poles.get(i).unwrap();
            for j in i + 1..len {
                if i == j {
                    continue;
                }
                let second = poles.get(j).unwrap();
                let dist = dist_poles(first, second);
                pairs.push((dist, i, j));
            }
        }

        pairs.sort_by(|a, b| {
            if a.0 < b.0 {
                Ordering::Less
            } else {
                Ordering::Greater
            }
        });

        for (dist, a, b) in pairs[0..1000].iter() {
            let first_circuit = circuits.find_circuit(*a);
            let second_circuit = circuits.find_circuit(*b);

            match (first_circuit, second_circuit) {
                (None, None) => {
                    circuits.new_circuit(*a, *b);
                }
                (Some(c), None) => {
                    circuits.append_circuit(c, *b);
                }
                (None, Some(c)) => {
                    circuits.append_circuit(c, *a);
                }
                (Some(c1), Some(c2)) => {
                    if c1 != c2 {
                        circuits.join_circuits(c1, c2);
                    }
                }
            }
        }

        assert_eq!(circuits.top_three().iter().product::<usize>(), 66640)
    }

:::

Rust

Part 1 took a decent while, partly life getting in the way, partly as I was struggling with some Rust things like floats not being sortable without mucking around, plus some weird bugs trying to get collect to do everything that I eventually just rewrote to avoid.

I found the noisy_float crate which let me wrap f64 as a "real" r64 which meant no NaN which meant Ord which meant sort_by_cached_key() and the rest worked.

I'd planned how to partition the closest neighbour search, but the whole thing runs in 24ms so I didn't bother.

::: spoiler other types

type Id = usize;
type Connection = (Id, Id);
type Circuit = HashSet<Id>;

#[derive(PartialEq)]
struct Point {
    x: usize,
    y: usize,
    z: usize,
}

impl FromStr for Point {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self> {
        let mut parts = s.split(',');
        Ok(Point {
            x: parts.next().ok_or_eyre("missing x")?.parse()?,
            y: parts.next().ok_or_eyre("missing y")?.parse()?,
            z: parts.next().ok_or_eyre("missing z")?.parse()?,
        })
    }
}

impl Point {
    fn distance(&self, other: &Point) -> R64 {
        let dist = ((
            self.x.abs_diff(other.x).pow(2) +
            self.y.abs_diff(other.y).pow(2) +
            self.z.abs_diff(other.z).pow(2)) as f64)
            .sqrt();
        r64(dist)
    }
}

:::

struct Boxes(Vec<Point>);

impl Boxes {
    fn closest(&self) -> Vec<Connection> {
        let mut closest = (0..self.0.len())
            .flat_map(|a| ((a + 1)..self.0.len()).map(move |b| (a, b)))
            .collect::<Vec<_>>();

        closest.sort_by_cached_key(|&(a, b)| self.0[a].distance(&self.0[b]));
        closest
    }

    fn connect_all(&self, p1_threshold: usize) -> Result<(usize, usize)> {
        let mut circuits: Vec<Circuit> = (0..self.0.len())
            .map(|id| HashSet::from_iter(iter::once(id)))
            .collect();

        let mut closest = self.closest().into_iter();
        let mut p1 = 0;
        let mut n = 0;
        loop {
            n += 1;
            let (a, b) = closest.next().ok_or_eyre("All connected already")?;
            let a_circ = circuits.iter().position(|c| c.contains(&a));
            let b_circ = circuits.iter().position(|c| c.contains(&b));
            match (a_circ, b_circ) {
                (None, None) => {
                    circuits.push(vec![a, b].into_iter().collect());
                }
                (None, Some(idx)) => {
                    circuits[idx].insert(a);
                }
                (Some(idx), None) => {
                    circuits[idx].insert(b);
                }
                (Some(a_idx), Some(b_idx)) if a_idx != b_idx => {
                    let keep_idx = a_idx.min(b_idx);
                    let rem_idx = a_idx.max(b_idx);

                    let drained = circuits.swap_remove(rem_idx);
                    // this position is still valid since we removed the later set
                    circuits[keep_idx].extend(drained);
                }
                _ => { /* already connected to same circuit */ }
            };

            if n == p1_threshold {
                circuits.sort_by_key(|set| set.len());
                circuits.reverse();
                p1 = circuits.iter().take(3).map(|set| set.len()).product();
            }
            if circuits.len() == 1 {
                let p2 = self.0[a].x * self.0[b].x;
                return Ok((p1, p2));
            }
        }
    }
}

(Browser-based) Javascript

My initial approach was to consider each junction as a circuit, and then merge the closest circuits. Took me way to long to realize the problem statement for part 1 made this unworkable (as you need to count redundant connections as "attempts"). Thankfully part 2 doesn't care about how many connections you make, so I was able to reuse that code to solve part 2.

To solve part 1 "the right way", I first thought I had to store a circuit as a collection of pairs of junctions (literally, the collection of connections). Oh god was that messy code; 3 layers of nested for-loops and it still wasn't getting close to the answer. I eventually realized I could reference the junctions' indices in the input to simplify things, allowing me to manipulate simple sets of ints. Combine with pre-calculating the distances once before starting the connecting/merging and you end up with a surprisingly simple and snappy algorithm.

Given I realized these optimizations after restarting part 1, my solution for part 2 doesn't take advantage of any of them and takes an eye-watering 22 seconds to terminate on average. It probably re-computes more distances than it computes new ones, for each iteration...

::: spoiler Code

function getExampleText() {
  return `162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689
`
}
function part1(inputText, maxConnections) {
  const junctions = inputText.trimEnd().split('\n')
    .map(line => line.split(',')
      .map(strValue => Number.parseInt(strValue, 10)));
  // compute the distance between each junction exactly once
  const annotatedDistances = Array(Math.ceil(((junctions.length - 1) ** 2) / 2));
  let counter = 0;
  for (let i = 0; i < junctions.length; i++) {
    const [xI, yI, zI] = junctions[i];
    for (let j = i + 1; j < junctions.length; j++) {
      const [xJ, yJ, zJ] = junctions[j];
      const distanceSquared = (xJ - xI) ** 2 + (yJ - yI) ** 2 + (zJ - zI) ** 2;
      annotatedDistances[counter] = [distanceSquared, i, j];
      counter++;
    }
  }
  // sort the pairs of junctions by closest to farthest
  annotatedDistances.sort(([dA], [dB]) => dA - dB);
  // connect the maxConnections-closest junctions
  const circuits = [];
  for (const [_, i, j] of annotatedDistances.slice(0, maxConnections)) {
    // find any existing circuit(s) that already contain(s) one of the junctions
    let existingCircuits = [];
    for (let circuitIndex = 0; circuitIndex < circuits.length; circuitIndex++) {
      const circuit = circuits[circuitIndex];
      if (circuit.has(i) || circuit.has(j)) {
        existingCircuits.push(circuitIndex);
      }
    }
    // 3 possible cases:
    // the junctions are not part of any existing circuits => connecting them creates a new circuit
    if (existingCircuits.length === 0) {
      circuits.push(new Set([i, j]));
    }
    // the junctions are part of 1 existing circuit => connecting them extends this existing circuit to encompass an additional junction (if only 1 junction is already in this circuit)
    else if (existingCircuits.length === 1) {
      const circuitToExtend = circuits[existingCircuits[0]];
      circuitToExtend.add(i);
      circuitToExtend.add(j);
    }
    // the junctions are part of 2 distinct existing circuits => connecting them merges these two circuits
    else if (existingCircuits.length === 2) {
      // merge circuit(s) with new connection between junctions i and j
      const circuitMergerIndex = existingCircuits.shift();
      for (const circuitToBeMergedIndex of existingCircuits) {
        circuits[circuitMergerIndex] = circuits[circuitMergerIndex].union(circuits[circuitToBeMergedIndex]);
        circuits.splice(circuitToBeMergedIndex, 1);
      }
    }
  }
  circuits.sort((a, b) => b.size - a.size);
//console.debug({ sortedCircuits: structuredClone(circuits) });
  return circuits.slice(0, 3).reduce((accu, next) => accu * next.size, 1)
}
{
  const start = performance.now();
//const result = part1(getExampleText(), 10);
  const result = part1(document.body.textContent, 1_000);
  const end = performance.now();
  console.info({
    day: 7,
    part: 1,
    time: end - start,
    result
  });
}

function part2(inputText) {
  const circuits = inputText
    .trimEnd()
    .split('\n')
    .map(line => ([
      line.split(',')
      .map(strVal => Number.parseInt(strVal, 10))
    ]))
  let junctionA, junctionB;
  while (circuits.length > 1) {
    let smallestSquaredDistance = Number.POSITIVE_INFINITY;
    let toConnectA, toConnectB;
    for (const circuitA of circuits) {
      for (const circuitB of circuits) {
        if (circuitA === circuitB) {
          continue;
        }
        let squaredCircuitDistance = Number.POSITIVE_INFINITY;
        for (const [xA, yA, zA] of circuitA) {
          for (const [xB, yB, zB] of circuitB) {
            const distance = (xB - xA) ** 2 + (yB - yA) ** 2 + (zB - zA) ** 2;
            if (distance < squaredCircuitDistance) {
              squaredCircuitDistance = distance;
              junctionA = [xA, yA, zA];
              junctionB = [xB, yB, zB];
            }
          }
        }
        if (squaredCircuitDistance < smallestSquaredDistance) {
          smallestSquaredDistance = squaredCircuitDistance;
          toConnectA = circuitA;
          toConnectB = circuitB;
        }
      }
    }
    if (toConnectA.length > toConnectB.length) {
      toConnectA.push(...toConnectB);
      const bIndex = circuits.indexOf(toConnectB);
      circuits.splice(bIndex, 1);
    } else {
      toConnectB.push(...toConnectA);
      const aIndex = circuits.indexOf(toConnectA);
      circuits.splice(aIndex, 1);
    }
  }
  return junctionA[0] * junctionB[0];
}
{
  const start = performance.now();
//  const result = part2(getExampleText());
  const result = part2(document.body.textContent);
  const end = performance.now();
  console.info({
    day: 7,
    part: 2,
    time: end - start,
    result
  });
}

:::