Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Break Rings by laharah
from collections import defaultdict
def break_rings(rings):
n = defaultdict(set) # build network as dictionary of nodes with set of connections
for a, b in rings:
n[a].add(b)
n[b].add(a)
broken = 0
while len(n) > 1:
leaf = min(n, key=lambda x: len(n.get(x))) # get least connected ring
to_break = n[leaf].pop() # remove arbitrary node connected to leaf
for ring in n[to_break]:
if ring is not leaf: # prevent KeyError
n[ring].remove(to_break) # remove connections to broken ring
if len(n[ring]) < 1:
del n[ring] # remove rings with no connections (freed rings)
del n[to_break] # get rid of broken ring
broken += 1
return broken
if __name__ == '__main__':
# These "asserts" using only for self-checking and not necessary for auto-testing
assert break_rings(({1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {4, 6})) == 3, "example"
assert break_rings(({1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4})) == 3, "All to all"
assert break_rings(({5, 6}, {4, 5}, {3, 4}, {3, 2}, {2, 1}, {1, 6})) == 3, "Chain"
assert break_rings(({8, 9}, {1, 9}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {8, 7})) == 5, "Long chain"
April 4, 2015