day08b.py

import heapq
import math

f = open('input.txt', 'r')
boxes = [list(map(int, line.split(','))) for line in f.read().split('\n')]
n = len(boxes)

def dist(a, b):
    return math.sqrt(sum((ea-eb)**2 for ea,eb in zip(a,b))) if a != b else float('inf')

tuples = []
for i in range(n):
    for j in range(i+1, n):
        tuples.append([dist(boxes[i], boxes[j]), i, j])

heapq.heapify(tuples)

par = {}
rank = {}
for i in range(n):
    par[i] = i
    rank[i] = 0

def find(a):
    while a != par[a]:
        a = par[a]
    return a

def union(a, b):
    pa = find(a)
    pb = find(b)

    if pa == pb:
        return 0

    if rank[pa] < rank[pb]:
        par[pa] = pb
    elif rank[pb] < rank[pa]:
        par[pb] = pa
    else:
        par[pb] = pa
        rank[pa] += 1
    return 1

groups = n
while groups > 1:
    _, a, b = heapq.heappop(tuples)
    groups -= union(a, b)

res = boxes[a][0] * boxes[b][0]
print(res)