Re: Jour 8

Ici, j'ai réfléchi au fait que si on a deux boîtes de dérivation qui ne sont pas reliées par le fil le plus petit existant, alors on peut raccourcir le réseau total.
Donc il apparaît clair qu'il faut ajouter les liens du plus petit au plus grand, jusqu'à compléter l'exercice.

J'ai un peu lutté sur la représentation des données, je voulais être intelligent, mais je me suis retrouvé avec des cas où des sous-graphes étaient encore référencés.
Là, j'aurais été plus à l'aise en C, à manipuler proprement des pointeurs, pour modifier directement les données à plusieurs endroits à la fois.
Bon, je le fais aussi en Python, mais j'ai des trucs qui m'ont embêté, et j'ai perdu l'élégance que j'espérais avoir.

Au final, j'ai quand même un truc pas super optimisé qui s'exécute en 3,5s, c'est très laid.
Et comme ça prend seulement 1s en PyPy, je sais que j'ai fait du mauvais travail :D

from dataclasses import dataclass
import math
import itertools
MAX=1000 # 10 pour l'exemple
data = sys.stdin.read().strip().splitlines()
@dataclass(frozen=True)
class Box:
 x:int
 y:int
 z:int
 def __mul__(self, x): # distance euclidienne: a*b
 return (self.x-x.x)**2+(self.y-x.y)**2+(self.z-x.z)**2
boxes={
 Box(*(int(_) for _ in l.split(",")))
 for l in data
}
dist=sorted({
 (a*b,frozenset((a,b)))
 for a,b in itertools.product(boxes,boxes)
 if b!=a
})
circuits={b:{b} for b in boxes}
for i,(d,(a,b)) in enumerate(dist):
 if b not in circuits[a]:
 c=circuits[a].union(circuits[b])
 if len(c)==len(boxes):
 break # On a fini
 for _ in c:
 circuits[_]=c
 if i==MAX-1:
 ex1={(len(_),frozenset(_)) for _ in circuits.values()}
ex1=math.prod(sorted(l for l,_ in ex1)[-3:])
ex2=a.x*b.x