Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Break Rings by kumaus
"""
Trying out all possibilities was too slow. This approach uses pruning
and avoids repeated removal of the same rings in different order.
"""
def break_ring(links, marked, depth, min_depth):
"""
Parameters:
links: remaining links between rings
marked: rings which have already been tried in previous iterations
depth: number of rings broken
min_depth: best solution so far
"""
if depth == min_depth: # no improvement possible
return min_depth
if len(links) == 0: # new optimum
return depth
# Rings available for breaking (avoiding repeats)
available_rings = set.union(*links) - marked
# Sorted list, with most likely candidates first
sorted_rings = sorted(available_rings, key=lambda x:sum(x in l for l in links), reverse = True)
# Try breaking different rings in order, removing any attached links
# After a ring has been tried, mark it to avoid repeating in a different iteration deeper down
for r in sorted_rings:
# Recursion with remaining links, updated set of marked rings over depth level
min_depth = break_ring([l for l in links if r not in l], marked.copy(), depth+1, min_depth)
marked |= {r}
return min_depth
def break_rings(links):
size = len(set.union(*links))
return break_ring(links, set(), 0, size)
def run():
# 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"
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},))
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},))
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},))
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},))
Sept. 17, 2015
