54 lines
1.3 KiB
Python
54 lines
1.3 KiB
Python
from math import prod, sqrt
|
|
from pathlib import Path
|
|
from typing import TypeAlias
|
|
|
|
Point: TypeAlias = tuple[int, int, int]
|
|
Circuit: TypeAlias = set[Point]
|
|
|
|
FILE = "input.txt"
|
|
|
|
def main():
|
|
lines = Path(FILE).read_text().splitlines()
|
|
points: list[Point] = [parse_point(line) for line in lines]
|
|
distances = sorted([
|
|
(distance(p1, p2), Circuit([p1, p2]))
|
|
for i, p1 in enumerate(points)
|
|
for p2 in points[i+1:]
|
|
], key=lambda x: x[0])
|
|
return prod(
|
|
p[0]
|
|
for p in last_circuit(
|
|
[c for _, c in distances], len(points)
|
|
)
|
|
)
|
|
|
|
|
|
def last_circuit(circuits: list[Circuit], total: int) -> Circuit:
|
|
all: list[Circuit] = []
|
|
for circuit in circuits:
|
|
connected = [
|
|
a
|
|
for a in all
|
|
if circuit & a
|
|
]
|
|
all = [a for a in all if a not in connected]
|
|
all.append(Circuit.union(circuit, *connected))
|
|
if len(all) == 1 and len(all[0]) == total:
|
|
return circuit
|
|
assert False, "unreachable"
|
|
|
|
|
|
def distance(p1: tuple[int, int, int], p2: tuple[int, int, int]):
|
|
x1, y1, z1 = p1
|
|
x2, y2, z2 = p2
|
|
return sqrt((x2-x1)**2+(y2-y1)**2+(z2-z1)**2)
|
|
|
|
|
|
def parse_point(line: str) -> Point:
|
|
x, y, z = line.split(",")
|
|
return (int(x), int(y), int(z))
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print(main())
|