with open(r'day8/input.txt', 'r') as input:
    lines = list(map(lambda x: list(map(lambda y: int(y),x.split(','))),input.read().split('\n')[:-1]))

def dist(a,b):
    return (a[0]-b[0])**2 + (a[1]-b[1])**2 + (a[2]-b[2])**2

excluded_neigbors = [set([i]) for i in range(len(lines))]

def find_best(i):
    best_distances[i] = [10**15,-1]
    for j,node2 in enumerate(lines):
        if j in excluded_neigbors[i]: continue
        distance = dist(lines[i],node2)
        best_distances[i] = min([distance,j], best_distances[i],key=lambda x : x[0])

best_distances = []

idx_circuit = list(range(len(lines)))

for i in range(len(lines)):
    best_distances.append(0)
    find_best(i)

for _ in range(1000):
    min_idx = best_distances.index(min(best_distances, key = lambda x:x[0]))
    if (old_idx := idx_circuit[min_idx]) != (new_idx := idx_circuit[(ass_idx := best_distances[min_idx][1])]): 
        for i in range(len(lines)):
            if idx_circuit[i] == old_idx:
                idx_circuit[i] = new_idx
    excluded_neigbors[min_idx].add(ass_idx)
    excluded_neigbors[ass_idx].add(min_idx)
    find_best(min_idx)
    find_best(ass_idx)

counts = []
for circuit in set(idx_circuit):
    count = len(list(filter(lambda x: idx_circuit[x] == circuit,idx_circuit)))
    counts.append(count)
counts.sort(reverse=True)
print(counts)
print("score:",counts[0]*counts[1]*counts[2])