Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Break Rings by tarasenkoa
import copy
def break_rings(links):
rings = {}
for link in links:
r1,r2 = link
rings[r1] = rings.get(r1,[]) + [r2]
rings[r2] = rings.get(r2,[]) + [r1]
n0 = len(rings)
rings = doit(rings, 0)
broken = n0 - len(rings)
return broken
def doit(rings, to_remove = 0):
if to_remove > 0:
rings = breakone(rings, to_remove)
# first consider one-linked rings, we definitely need to chop them
while True:
list = [(vs,i) for i,vs in rings.items() if len(vs) == 1]
if len(list) == 0:
break
vs, i = list.pop()
# break the nearest to the one-linked ring
rings = breakone(rings, rings[i][0])
# sort the rings from least linked to most linked
sortedlist = sorted([(len(vs),i) for i,vs in rings.items() if len(vs) > 0])
# if we're done, return
if len(sortedlist) == 0:
return rings
# pop the most linked
n, i = sortedlist.pop()
# 1st case - break it
rs0 = copy.deepcopy(rings)
rs0 = doit(rs0,i)
# 2nd case - check the-most-linked's neighbours and break one of them
n,j = sorted([(len(vs),j) for j,vs in rings.items() if j in rings[i]]).pop()
rs1 = copy.deepcopy(rings)
rs1 = doit(rs1,j)
# consider 1st and 2nd cases result and return the best
if len(rs0) > len(rs1):
return rs0
return rs1
# breaks one ring, returns resulted rings
def breakone(rings, to_remove):
# remove this rings from its neighbors' definitions
for r in rings[to_remove]:
rings[r].remove(to_remove)
rings.pop(to_remove)
return rings
if __name__ == '__main__':
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"
assert break_rings(({1,2},{1,3},{1,4},{2,3},{2,4},{3,4})) == 3, "test 2/2"
assert break_rings(({1,9},{1,2},{8,5},{4,6},{5,6},{8,1},{3,4},{2,6},{9,6},{8,4},{8,3},{5,7},{9,7},{2,3},{1,7},
)) == 5, "extra 4/4"
assert break_rings(({1,2}, {2,3}, {3,4}, {4,5}, {5,2}, {1,6}, {6,7}, {7,8},
{8,9}, {9,6}, {1,10}, {10,11},{11,12},{12,13},{13,10},{1,14},
{14,15},{15,16},{16,17},{17,14},
)) == 8, "extra 13/13"
assert break_rings(({3,4},{5,6},{2,7},{1,5},{2,6},{8,4},{1,7},{4,5},{9,5},{2,3},{8,2},{2,4},{9,6},{5,7},{3,6},{1,3})) == 5, "extra 8/8"
assert break_rings(({1,3},{3,4},{3,5},{4,6},{6,7},{8,3},{8,1},{2,6},{8,4},{9,5},{4,5},{1,7},)) == 5, "extra 5/5"
Feb. 22, 2015
Comments: