105 lines
3.4 KiB
Python
105 lines
3.4 KiB
Python
#!/usr/bin/env python
|
|
|
|
# https://adventofcode.com/2025/day/8
|
|
|
|
import math
|
|
|
|
f = open("day08input.txt", "r")
|
|
#f = open("testinput.txt", "r")
|
|
jbox = []
|
|
for line in f.readlines():
|
|
line = line.strip().split(",")
|
|
jbox.append(list(map(int, line)))
|
|
|
|
|
|
def print2d(field):
|
|
for line in field:
|
|
print("\t".join(["{:6.2f}".format(el) if el else "None" for el in line]))
|
|
|
|
|
|
def get_distance(a: list[int], b: list[int]) -> float:
|
|
assert len(a) == len(b)
|
|
return math.sqrt(sum([(a[i] - b[i]) ** 2 for i in range(len(a))]))
|
|
|
|
|
|
|
|
def solve(jbox: list[list[int]], connections: int) -> int:
|
|
if connections >= 0:
|
|
print(f"Solving part 1: Adding {connections} connections")
|
|
else:
|
|
print(f"Solving part 2: Adding connections until all boxes are on the same circuit")
|
|
|
|
l = len(jbox)
|
|
|
|
# calculate all distances
|
|
distance = [[None] * l] * l
|
|
for p in range(l):
|
|
distance[p] = [get_distance(jbox[p], jbox[q]) if q > p else None for q in range(l)]
|
|
|
|
# start with one-box circuits
|
|
circuits = [[i] for i in range(l)]
|
|
|
|
# connect junction boxes to form circuits
|
|
conn_count = 0
|
|
while True:
|
|
print(f"{conn_count=}")
|
|
|
|
# find current shortest distance
|
|
min_pq = None
|
|
for p in range(l - 1):
|
|
line = [distance[p][q] for q in range(p + 1, l)]
|
|
min_q = distance[p].index(min(list(filter(lambda x: x, line))))
|
|
# check if distance wasn't used before
|
|
if min_q:
|
|
# check if distance is shorter than the shortest distance found so far
|
|
if not min_pq or distance[p][min_q] < distance[min_pq[0]][min_pq[1]]:
|
|
min_pq = (p, min_q)
|
|
assert min_pq is not None
|
|
|
|
# find the circuits the two boxes with the shortest distance to each other belong to
|
|
circuit_p, circuit_q = None, None
|
|
for i in range(len(circuits)):
|
|
if min_pq[0] in circuits[i]:
|
|
circuit_p = i
|
|
if min_pq[1] in circuits[i]:
|
|
circuit_q = i
|
|
if circuit_p and circuit_q:
|
|
break
|
|
|
|
# make sure both boxes are on any circuits
|
|
assert circuit_p is not None and circuit_q is not None
|
|
|
|
# make new connection
|
|
if circuit_p == circuit_q:
|
|
print(f"Boxes {min_pq[0]} and {min_pq[1]} are on the same circuit -> there are still {len(circuits)} circuits")
|
|
else:
|
|
print(f"Boxes {min_pq[0]} and {min_pq[1]} are on different circuits -> combining circuits {circuit_p} and {circuit_q} -> there are now {len(circuits) - 1} circuits")
|
|
if circuit_p < circuit_q:
|
|
circuits[circuit_p] += circuits.pop(circuit_q)
|
|
else:
|
|
circuits[circuit_q] += circuits.pop(circuit_p)
|
|
assert sum([len(c) for c in circuits]) == l
|
|
|
|
# set distance to None so it won't be considered going forward
|
|
distance[min_pq[0]][min_pq[1]] = None
|
|
|
|
# increment counter
|
|
conn_count += 1
|
|
|
|
# check if while loop is finished or not
|
|
if connections >= 0:
|
|
# break condition for part 1: break if number of connection is reached
|
|
if conn_count == connections:
|
|
print("Finished solving part 1! Returning product of the highest three circuit lengths …")
|
|
circuits.sort(reverse=True, key=len)
|
|
return len(circuits[0]) * len(circuits[1]) * len(circuits[2])
|
|
else:
|
|
# break condition for part 2: break if there is only one circuit
|
|
if len(circuits) == 1:
|
|
print("Finished solving part 2! Returning product of the final two boxes' X coordinates …")
|
|
return jbox[min_pq[0]][0] * jbox[min_pq[1]][0]
|
|
|
|
#print(solve(jbox, 1000))
|
|
print(solve(jbox, -1))
|
|
|