Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Third solution in Speedy category for Break Rings by yukirin
from bisect import insort_left
def break_rings(rings):
queue = [(0, rings)]
while queue:
count, rings = queue.pop(0)
while True:
nums = set().union(*rings)
try:
edge_num = next(n for n in nums if sum(True for r in rings if n in r) == 1)
except StopIteration:
break
delete_num = next(r - set((edge_num,)) for r in rings if edge_num in r).pop()
rings = [r for r in rings if delete_num not in r]
count += 1
if not rings: return count
count += 1
for n in nums:
insort_left(queue, (count, [r for r in rings if n not in r]))
April 13, 2015
Comments:
