Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Simple 4-liner solution in Clear category for Break Rings by BrianMcleod
from itertools import combinations
def break_rings(rings):
"""
Find the minimum number of rings to cut to separate all remaining rings
First, create a set that has all the rings to allow caculating combinations.
Test for all combinations of n rings cut. If the combination has at least 1 ring
in every link in the set, it will result in separating all remaining rings.
Return the smallest n that satisfies the test.
"""
r = {ring for link in rings for ring in link}
for n in range(1,len(r)):
if any(all(set(p)&ring for ring in rings) for p in combinations(r,n)):
return n
Oct. 18, 2018