Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Enumerative Approach solution in Clear category for Break Rings by JamesArruda
# migrated from python 2.7
import collections
import itertools
from functools import reduce
# I had done a BFS type algorithm, but it was taking forever to run
# I found that an enumerative approach worked best for larger graphs
#
# Connected components are found with a BFS, though (and an outer loop over nodes)
#
def make_graph(rings,ignorelist):
"""
Make a network as a dictionary of: {nodes: [connected nodes]}
The ignorelist is a list of 0/1 to indicate if a node is being ignored
"""
edges = {}
for pair in rings:
p1,p2 = pair
if not p1 in edges:
edges[p1] = set()
if not p2 in edges:
edges[p2] = set()
if ignorelist[p1-1] == 1 and ignorelist[p2-1] == 1:
edges[p1].add(p2)
edges[p2].add(p1)
return edges
def connected_component(graph, start):
"""
BFS to get a connected component
"""
visited, queue = set(), [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
def connected_components(graph):
"""
Loop over all the nodes to get all the connected components
"""
nodes = list(graph.keys())
cons = []
while len(nodes) > 0:
testName = nodes.pop()
con = connected_component(graph,testName)
cons.append(con)
for c in con:
if c in nodes:
nodes.remove(c)
return cons
def break_rings(rings):
nr = max(reduce(set.union, rings))
sols = [c for c in itertools.product(*[[0,1] for x in range(nr)])]
# sort the sols by sum
ssols = sorted(sols,key=lambda x:sum(x),reverse=True)
for S in ssols:
# make the limited graph
GR = make_graph(rings,S)
nc = len(S)-sum(S)
if max([len(x) for x in connected_components(GR)]) == 1:
return nc
break
if __name__ == '__main__':
# 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"
Feb. 21, 2015