Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Top solution with explanation solution in Clear category for Break Rings by AdamToth
import itertools as it
def break_rings(links):
# get the number of rings
N = max(map(max, links));
# break an increasing number of links
for number_of_broken in range(1, N+1):
# iterate trough all combinations of breaking given a number
for broken_rings in it.combinations(range(1, N+1), number_of_broken):
# all links must have a broken one or we can still release more rings
# = all links have a shared element with a the current
# combination of broken links
if all(link & set(broken_rings) for link in links):
# we have already checked all possibilities with less rings broken
# so we can be certain that this is the most optimal
return number_of_broken
March 7, 2015
Comments:
