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
70
71
72
73
|
#advent of code 2024
#day 23
#this is rewritten to adapt for part 2. All possible sets of computers
#are searched for recursively (with FindNetwork function)
#and stored in subnetworks set. Then it iterates over all elements of
#subnetworks set. If the element has 3 computers, then it iterates over
#all computers in the set. If at least one computer starts with "t",
#it is counted towards part 1. We keep track of the longest set of
#computers and update part2 variable when it changes.
#The way FindNetwork works is that it takes a name of PC and a set of previously
#visited computers that are all iterconnected. Then the given PC is added
#to the set, the set is sorted (to avoid duplicates) and added to
#subnetworks set. It iterates over all computers connected to PC from argument
#according to Connections dictionary. If the computer is already in
#the cluster, it is skipped. Then, we nest another loop to check if the
#connections of the computer match the computers in the cluster.
#if not, it's skipped. if yes, it call the FindNetwork function again
#with the computer and updated cluster (NextCluster) as arguments.
#infinite loop is prevented while checking whether or not the computer
#is already in the cluster. Runtime is sped up due to discarding already
#visited clusters accoroding to subnetworks set.
#the password for part2 is just a string of computer names separated with commas
#similar to previous day
#I think the correct term is "ring" or "topology" but that's completely irrelevant
#for the puzzle
Connections = {};
f = open("23.in","r");
for l in f:
PC1, PC2 = l.strip().split("-");
if PC1 not in Connections: Connections[PC1] = set();
if PC2 not in Connections: Connections[PC2] = set();
Connections[PC1].add(PC2);
Connections[PC2].add(PC1);
f.close();
subnetworks = set();
def FindNetwork(PC,Cluster):
NextCluster = Cluster.copy();
NextCluster.add(PC);
NextCluster = sorted(NextCluster);
if tuple(NextCluster) in subnetworks: return;
subnetworks.add(tuple(NextCluster));
for NextPC in Connections[PC]:
ok = True;
if NextPC in Cluster: continue;
for OtherPCs in NextCluster:
if OtherPCs not in Connections[NextPC]: ok = False;
if not ok: continue;
FindNetwork(NextPC, set(NextCluster));
for i,computer in enumerate(Connections):
print(i, "/", len(Connections));
FindNetwork(computer,set());
part1 = 0;
part2 = None;
LargestNetworkSize = 0;
for subnet in subnetworks:
SubnetSize = len(subnet)
if SubnetSize == 3:
for computer in subnet:
if computer[0] == "t":
part1 += 1;
break;
LargestNetworkSize = max(LargestNetworkSize,SubnetSize);
if LargestNetworkSize == SubnetSize: part2 = subnet;
part2 = ",".join(part2);
print("part 1 =",part1);
print("part 2 =",part2);
|
