#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);