39 lines
1.4 KiB
Python
39 lines
1.4 KiB
Python
|
import bisect, math
|
||
|
|
from itertools import combinations
|
||
|
|
input = open("input", 'r')
|
||
|
|
|
||
|
|
points = []
|
||
|
|
for line in input:
|
||
|
|
points.append(tuple((int(cord) for cord in line.split(","))))
|
||
|
|
|
||
|
|
# distances = []
|
||
|
|
# distance_key = lambda d: d[0]
|
||
|
|
# for i, p in enumerate(points):
|
||
|
|
# for j, q in enumerate(points):
|
||
|
|
# if i<=j: continue # Avoid duplicates
|
||
|
|
# # we'll work with square distances because it won't matter
|
||
|
|
# dist = math.dist(*[p,q])
|
||
|
|
# bisect.insort(distances, (dist, i, j), key=distance_key)
|
||
|
|
|
||
|
|
distances = sorted(combinations(points,2), key=lambda p: math.dist(*p))
|
||
|
|
|
||
|
|
circuits = {frozenset([p]) for p in points}
|
||
|
|
|
||
|
|
def solution(distances, circuits, pairs=1000, part2=False):
|
||
|
|
for i, (p1, p2) in enumerate(distances):
|
||
|
|
if not part2 and i >= pairs:
|
||
|
|
circuits_by_len = sorted(circuits, key=len, reverse=True)
|
||
|
|
return math.prod([len(circuit) for circuit in circuits_by_len[:3]])
|
||
|
|
p1_group = [circuit for circuit in circuits if p1 in circuit][0]
|
||
|
|
p2_group = [circuit for circuit in circuits if p2 in circuit][0]
|
||
|
|
circuits -= {p1_group, p2_group}
|
||
|
|
circuits.add(p1_group | p2_group)
|
||
|
|
if part2 and len(circuits) == 1:
|
||
|
|
return p1[0] * p2[0]
|
||
|
|
return None # Impossible!
|
||
|
|
|
||
|
|
|
||
|
|
# print(solution(distances, circuits, points, pairs=10))
|
||
|
|
print(solution(distances, circuits))
|
||
|
|
print(solution(distances, circuits, part2=True))
|