day08a.py

from collections import defaultdict
import heapq
import math

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

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


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

heapq.heapify(tuples)

neighs = defaultdict(list)
for _ in range(1000):
    _, a, b = heapq.heappop(tuples)
    neighs[a].append(b)
    neighs[b].append(a)

group_sizes = []
visited = [0]*len(boxes)
for i in range(len(boxes)):
    if visited[i]:
        continue

    group_size = 0
    q = [i]
    while q:
        curr = q.pop()
        if visited[curr]:
            continue
        visited[curr] = 1
        group_size += 1

        for neigh in neighs[curr]:
            q.append(neigh)

    group_sizes.append(group_size)


res = 1
heapq._heapify_max(group_sizes)
for _ in range(3):
    res *= heapq._heappop_max(group_sizes)

print(res)