#!/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))