https://adventofcode.com/2023/day/25

https://en.wikipedia.org/wiki/Karger%27s_algorithm

I turn the input into a graph annotated with the number of input nodes each node represents. As nodes are merged by Karger's algorithm, I update the node labels to account for the number of nodes each new node represents. This allows the final answer to be directly computed from the output of the algorithm.

I've implemented the Karger-Stein algorithm to produce an infinite list of candidate min-cuts. This list can then be searched for the one that has size 3 as required by the problem statement. This allows the algorithm to terminate as soon as the target cut is found without having to back that early exit into the algorithm itself.

>>> :{
:main +
"jqt: rhn xhk nvd
rsh: frs pzl lsr
xhk: hfx
cmg: qnr nvd lhk bvb
rhn: xhk bvb hfx
bvb: xhk hfx
pzl: lsr hfx nvd
qnr: nvd
ntq: jqt hfx bvb xhk
nvd: lhk
lsr: lhk
rzs: qnr cmg lsr rsh
frs: qnr lhk lsr
"
:}
54