70 lines
1.6 KiB
Python
70 lines
1.6 KiB
Python
graph = [[0 for _ in range(26**2)] for _ in range(26**2)]
|
|
|
|
edges = []
|
|
|
|
with open("day23") as f:
|
|
for l in f:
|
|
(a,b) = l.strip().split('-')
|
|
x = (ord(a[0])-ord('a'))*26 + (ord(a[1])-ord('a'))
|
|
y = (ord(b[0])-ord('a'))*26 + (ord(b[1])-ord('a'))
|
|
|
|
graph[x][y] = 1
|
|
graph[y][x] = 1
|
|
|
|
edges.append((x,y))
|
|
|
|
components = []
|
|
for edge in edges:
|
|
a = edge[0]
|
|
b = edge[1]
|
|
for c, e in enumerate(graph[b]):
|
|
if e == 1 and graph[c][a] == 1:
|
|
components.append((a,b,c))
|
|
|
|
t_components = set()
|
|
for component in components:
|
|
for c in component:
|
|
if c >= 494 and c<520:
|
|
t_components.add(tuple(sorted(component)))
|
|
|
|
print(len(t_components))
|
|
|
|
|
|
def find_component(start):
|
|
component = [start[0],start[1]]
|
|
|
|
changed = True
|
|
while changed:
|
|
changed = False
|
|
a = component[-1]
|
|
|
|
candidates = []
|
|
for b, e in enumerate(graph[a]):
|
|
if e == 1: candidates.append(b)
|
|
|
|
for candidate in candidates:
|
|
for comp in component:
|
|
if graph[comp][candidate] != 1: break
|
|
else:
|
|
component.append(candidate)
|
|
changed = True
|
|
return component
|
|
|
|
components = []
|
|
for edge in edges:
|
|
components.append(find_component(edge))
|
|
|
|
max_len = 0
|
|
max_idx = -1
|
|
for idx, c in enumerate(components):
|
|
if len(c) > max_len:
|
|
max_len = len(c)
|
|
max_idx = idx
|
|
|
|
max_component = components[max_idx]
|
|
max_component_alpha = []
|
|
for mc in max_component:
|
|
a = chr(ord('a')+(mc//26))
|
|
b = chr(ord('a')+(mc%26))
|
|
max_component_alpha.append(a+b)
|
|
print(','.join(sorted(max_component_alpha)))
|