Problem description

This is a graph problem, about connected components. The input data is a list of points coordinates in a 3-dimensional euclidean space. The task is to connect every node with the shortest connections.

Part 1

In the part, we look for the 1000 shortest connections, before computing the connected components sizes.

A reminder for non-math people : the euclidean distance between two points A (coordinates (x, y, z)) and B, of coordinates (x’, y’, z’), is :

(x′−x) 2+(y′−y) 2+(z′−z) 2\sqrt{(x' - x)^{2} + (y' - y)^{2} + (z' - z)^{2}}

Thanks to the following property :

x 2Unknown charactery 2xUnknown characteryxUnknown character=0,yUnknown character=0x ^{2} > y^{2} x > y x >= 0, y >= 0

this is not even necessary to calculate distances. As we only need to sort connections by distance, we can skip the square root part, and only compute squares of distances.

The code for square distances calculation is shown below :

private def squareDistance(a: (Long, Long, Long), b: (Long, Long, Long)): Long =
    val x = b(0) - a(0)
    val y = b(1) - a(1)
    val z = b(2) - a(2)
    x * x + y * y + z * z

val boxes = input.map(line => line.split(',')).map(x => (x(0).toLong, x(1).toLong, x(2).toLong)).toArray
val sqDists = (0 until boxes.length)
  .map(i => (i+1 until boxes.length).map(j => (i, j, squareDistance(boxes(i), boxes(j)))))
  .flatten
  .sortBy((i, j, dist) => dist)

Then, I calculated the connected components with the following algorithm :

The list of components is initialized. Each node Get the first connection, and determine if the connected nodes it connects are already in the same connected component. If this not the case, the components are merged. This process is repeated for the first 1000 connections.

var circuits = (0 until boxes.length).map(i => Set(i)).toSet
for (a, b, sqDist) <- sqDists.slice(0, connections) do
  val c1 = circuits.find(x => x.contains(a)).get
  val c2 = circuits.find(x => x.contains(b)).get

  if c1 != c2 then
    circuits += c1.union(c2) 
    circuits -= c1
    circuits -= c2

Finally, the 3 biggest components are extracted, and their sizes are multiplied together.

circuits.toArray.map(c => c.size).toArray.sorted.reverse.slice(0, 3).product

Part 2

This part is straightforward. The component merging process explained earlier is repeated until all the nodes are connected.

var idx = 0
while circuits.size > 1 do
  val (a, b, sqDist) = sqDists(idx)
  val c1 = circuits.find(x => x.contains(a)).get
  val c2 = circuits.find(x => x.contains(b)).get

  if c1 != c2 then
    circuits = circuits + c1.union(c2)
    circuits -= c1
    circuits -= c2
  idx += 1

The last connection needed to connect is extracted, and the X coordinates of the two connected nodes are multiplied together.

val (a, b, sqDist) = sqDists(idx - 1)
boxes(a)(0) * boxes(b)(0)

Performances

Most of the execution time was spent in computing and sorting squares of distances. For n nodes, there are n*(n-1)/2 squares of distances to compute, and those distances must be sorted (complexity O(n * log(n))), so the complexity of the problem is O(n^2 * log(n))