Advent of Code 2025: 8
El problema consiste en encontrar que coordenadas estan más cerca entre si y conectarlas formando redes donde la regla es que si una esta cerca a una que ya forma parte de una red esta se une a la red si dos estan cerca y estas no estan cerca de otra red ya formada, estas forman una nueva red
Solucion
Mi primera solucion fue crear un array de sets donde cada set va a contener una red y buscamos que nodo esta más cerca del nodo actual y si ese nodo ya se encuentra en una red lo agregamos a la red, si no se crea una nueva red
import math
class Box():
def __init__(self, x, y, z):
self.x = x
self.y = y
self.z = z
def distancia(self, otro):
return math.sqrt((self.x-otro.x)**2 + (self.y-otro.y)**2 + (self.z-otro.z)**2)
def __str__(self):
return f"X: {self.x} Y: {self.y} Z: {self.z}"
def __repr__(self):
return f"{{ X: {self.x} Y: {self.y} Z: {self.z} }}"
# with open("./input_test.txt", "r") as f:
with open("./input.txt", "r") as f:
boxes = []
lines = f.readlines()
for line in lines:
line = line.split(",")
box = Box(*[int(x) for x in line])
boxes.append(box)
max_redes = 1000
def obtener_n_redes(max):
total = []
le = len(boxes)
for i in range(1, le):
for j in range(i+1, le):
prev = boxes[i]
actual = boxes[j]
dist = prev.distancia(actual)
total.append((dist, prev, actual))
total.sort(key=lambda x: x[0])
# for i in total:
# print(i)
redes = []
conexiones_hechas = 0
for i in total:
if conexiones_hechas >= max:
break
dist = i[0]
caja1 = i[1]
caja2 = i[2]
idx1 = None
idx2 = None
for k, s in enumerate(redes):
if caja1 in s:
idx1 = k
if caja2 in s:
idx2 = k
if idx1 is None and idx2 is None:
redes.append({caja1, caja2})
elif idx1 is not None and idx2 is None:
redes[idx1].add(caja2)
elif idx1 is None and idx2 is not None:
redes[idx2].add(caja1)
elif idx1 is not None and idx2 is not None and idx1 != idx2:
redes[idx1].update(redes[idx2])
redes.remove(redes[idx2])
conexiones_hechas += 1
cajas_en_redes = set()
for s in redes:
cajas_en_redes.update(s)
for b in boxes:
if b not in cajas_en_redes:
redes.append({b})
tamanios = [len(s) for s in redes]
tamanios.sort(reverse=True)
# print(f"Tamaños de circuitos encontrados: {tamanios}")
res = 1
top_k = tamanios[:3]
for s in top_k:
res *= s
# pprint.pprint(redes)
return res
# print(boxes)
for i in range(10000):
t = obtener_n_redes(max_redes)
Existe un problema con esto, es que si ambos nodos se encuentran en redes distintas esta redes se tienen que combinar,
La solución eficiente usa un mapa donde cada caja apunta a su caja ‘origen’. Al conectar dos cajas, rastreamos el origen de cada una; si son distintos, simplemente enlazamos un origen con el otro, uniendo ambas redes completas en un solo paso sin tener que mover elementos de un set a otro.
import math
class Box():
def __init__(self, x, y, z):
self.x = x
self.y = y
self.z = z
def distancia(self, otro):
return math.sqrt((self.x - otro.x)**2 + (self.y - otro.y)**2 + (self.z - otro.z)**2)
def __repr__(self):
return f"Box({self.x}, {self.y}, {self.z})"
def __hash__(self):
return hash((self.x, self.y, self.z))
def __eq__(self, other):
return (self.x, self.y, self.z) == (other.x, other.y, other.z)
class UnionFind:
def __init__(self, items):
self.parent = {item: item for item in items}
self.size = {item: 1 for item in items}
def find(self, item):
if self.parent[item] != item:
self.parent[item] = self.find(self.parent[item])
return self.parent[item]
def union(self, item1, item2):
root1 = self.find(item1)
root2 = self.find(item2)
if root1 != root2:
if self.size[root1] < self.size[root2]:
root1, root2 = root2, root1
self.parent[root2] = root1
self.size[root1] += self.size[root2]
del self.size[root2]
return True
return False
def resolver_eficiente(archivo, limite_conexiones):
boxes = []
with open(archivo, "r") as f:
for line in f:
coords = [int(x) for x in line.strip().split(",")]
boxes.append(Box(*coords))
pares = []
n = len(boxes)
for i in range(n):
for j in range(i + 1, n):
d = boxes[i].distancia(boxes[j])
pares.append((d, boxes[i], boxes[j]))
pares.sort(key=lambda x: x[0])
dsu = UnionFind(boxes)
conexiones_hechas = 0
for _, box1, box2 in pares:
if conexiones_hechas >= limite_conexiones:
break
dsu.union(box1, box2)
conexiones_hechas += 1
tamanios = list(dsu.size.values())
tamanios.sort(reverse=True)
res = 1
for s in tamanios[:3]:
res *= s
return tamanios, res
ruta_archivo = "./input.txt"
limite = 1000
for i in range(10000):
sizes, resultado = resolver_eficiente(ruta_archivo, limite)
print(f"Tamaños de los circuitos más grandes: {sizes[:5]}...")
print(f"Resultado final: {resultado}")
Pero al ejecutarlo casi no note diferencia en la velocidad, asi que medi cuanto tiempo se tardo cada uno en resolver el mismo problema n numero de veces
La diferencia de tiempo de ejecución entre cada uno quedaria como:
Por las veces que se ejecuto se puede concluir que el tiempo ahorrado crece el doble de rápido que la cantidad de datos. Es un crecimiento super-lineal.