adventofcode2023/day25/sol.py

125 lines
3.0 KiB
Python

import sys
import random
from pprint import pprint
def main():
G = {}
for line in sys.stdin:
n, to = line.split(": ")
to = to.split()
G[n] = to
pprint(G)
# mke connections symmetric
for n in list(G):
for t in G[n]:
G.setdefault(t,[])
if n not in G[t]:
G[t].append(n)
G = {n:tuple(t) for n,t in G.items()}
pprint(G)
print([len(g) for g in connected_components(G, set())])
def key(e):
v,t = e
return sort2(len(G[v]),len(G[t]))
E = sorted(set(sort2(v,t) for v in G for t in G[v]), key=key)
print(connected_components(G, {sort2('hfx','pzl'), sort2('bvb','cmg'), sort2('jqt','nvd')}))
num = 100
while num > 3:
num, fwd = karger_stein(G, E)
P = {}
for v,t in fwd.items():
P.setdefault(v,[])
P.setdefault(t,[])
P[v].append(t)
P[t].append(v)
cc = connected_components(P, set())
print([len(x) for x in cc])
print(len(cc[0]) * len(cc[1]))
def karger_stein(G,E):
num = len(G)
fwd = {}
while num > 2:
# choose a random e
v,t = random.choice(E)
# contract the edge
fwd[v] = t
F = []
for v,t in E:
v = fwd.get(v,v)
t = fwd.get(t,t)
if v != t:
F.append((v,t))
E = F
num -= 1
print(len(E), E)
return len(E), fwd
def brute_force(x):
print([len(g) for g in connected_components(G, set())])
def key(e):
v,t = e
return sort2(len(G[v]),len(G[t]))
E = sorted(set(sort2(v,t) for v in G for t in G[v]), key=key)
E = [(v,t) for v,t in E if len(G[t]) <= 3 and len(G[v]) <= 3]
print(connected_components(G, {sort2('hfx','pzl'), sort2('bvb','cmg'), sort2('jqt','nvd')}))
#assert set(E) > {sort2('hfx','pzl'), sort2('bvb','cmg'), sort2('jqt','nvd')}
for i,e1 in enumerate(E):
print("#", i, e1)
for j,e2 in enumerate(E[i+1:], start=i+1):
for e3 in E[j+1:]:
cc = connected_components(G, {e1,e2,e3})
if len(cc) > 1 and not any(len(g) == 1 for g in cc):
#print(cc)
print(e1,e2,e3)
print([len(x) for x in cc])
print(len(cc[0]) * len(cc[1]))
def connected_components(G, nope):
V = [v for v in G]
mark = set()
cc = []
#print(nope)
while V:
node = V.pop()
if node in mark:
continue
group = []
def visit(node):
queue = [node]
while queue:
n = queue.pop()
if n in mark:
continue
mark.add(n)
group.append(n)
if n in G:
for t in G[n]:
if t not in mark and sort2(n,t) not in nope:
queue.append(t)
visit(node)
assert len(group) > 0
cc.append(group)
return cc
def sort2(a,b):
return min(a,b), max(a,b)
main()