1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#advent of code 2025
#day 08
def getDistance(j1,j2):
jx1,jy1,jz1=j1;
jx2,jy2,jz2=j2;
euclid=(jx2-jx1)*(jx2-jx1) + (jy2-jy1)*(jy2-jy1) + (jz2-jz1)*(jz2-jz1);
#no real need to take square root since if a^2 > b^2 then a > b
#no negatives since it's distance
return euclid;
#parsing
boxes=[];
limit=1000; #10 for example
PuzzleInput=open("08.in","r");
for line in PuzzleInput:
boxes.append(tuple([int(p) for p in line.split(",")]));
PuzzleInput.close();
numberOfBoxes=len(boxes);
distances=set();
for bi1,b1 in enumerate(boxes):
for bi2,b2 in enumerate(boxes):
if bi2==bi1:continue;
d1=getDistance(b1,b2);
distances.add((d1,tuple(sorted((b1,b2))) ) );
distances=sorted(distances,key=lambda m: m[0]);
circuits=dict();
for di in range(len(distances)):
d,boxtuple=distances[di];
box1,box2=boxtuple;
if box1 not in circuits and box2 not in circuits:
circuits[box1]=set([box1,box2]); #first box contains the circuit
circuits[box2]=box1; #second box links to first one
elif box1 in circuits and box2 not in circuits:
b3=box1; #find the box which has the circuit set assigned in dictionary
while type(circuits[b3])!=set:
b3=circuits[b3];
circuits[b3].add(box2);
circuits[box2]=b3;
elif box2 in circuits and box1 not in circuits:
b4=box2;
while type(circuits[b4])!=set:
b4=circuits[b4];
circuits[b4].add(box1);
circuits[box1]=b4;
elif box2 in circuits and box1 in circuits:
b3=box1;
while type(circuits[b3])!=set:
b3=circuits[b3];
b4=box2;
while type(circuits[b4])!=set:
b4=circuits[b4];
if b3==b4: continue;
circuits[b3].update(circuits[b4]);
circuits[b4]=b3;
clustering=sorted([len(circuits[cluster]) for cluster in circuits if type(circuits[cluster])==set],reverse=True);
if clustering[0]==numberOfBoxes:
part2=box1[0]*box2[0];
break;
if di==limit:
part1=1;
for i in range(3):
part1*=clustering[i];
print("part 1 =",part1, part1==103488);
print("part 2 =",part2, part2==8759985540);
|
