Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Network Loops by shima_x
from collections import defaultdict, deque
def get_node_set(connections):
result = []
for nodes in connections:
result += [nodes[0], nodes[1]]
return list(set(result))
def create_matrix(connections, nodes_matrix):
for n1,n2 in connections:
nodes_matrix[n1] += [n2]
nodes_matrix[n2] += [n1]
def find_path(max_node, nodes_matrix):
max_path = ()
for parent in range(1,max_node+1):
q = deque([(parent,)])
while q:
path = q.popleft()
for node in nodes_matrix[path[-1]]:
if node in path: continue
elif len(path)>=2 and len(path)>=len(max_path)-1 and parent in nodes_matrix[node]:
max_path = path + (node,parent,)
q.append(path+(node,))
return list(max_path)
def find_cycle(connections):
nodes = get_node_set(connections)
max_node = max(nodes)
nodes_matrix = defaultdict(list)
create_matrix(connections, nodes_matrix)
return find_path(max_node, nodes_matrix)
if __name__ == '__main__':
# These "asserts" using only for self-checking and not necessary for auto-testing
def checker(function, connections, best_size):
user_result = function(connections)
if not isinstance(user_result, (tuple, list)) or not all(isinstance(n, int) for n in user_result):
print("You should return a list/tuple of integers.")
return False
if not best_size and user_result:
print("Where did you find a cycle here?")
return False
if not best_size and not user_result:
return True
if len(user_result) < best_size + 1:
print("You can find a better loop.")
return False
if user_result[0] != user_result[-1]:
print("A cycle starts and ends in the same node.")
return False
if len(set(user_result)) != len(user_result) - 1:
print("Repeat! Yellow card!")
return False
for n1, n2 in zip(user_result[:-1], user_result[1:]):
if (n1, n2) not in connections and (n2, n1) not in connections:
print("{}-{} is not exist".format(n1, n2))
return False
return True, "Ok"
assert checker(find_cycle,
((1, 2), (2, 3), (3, 4), (4, 5), (5, 7), (7, 6),
(8, 5), (8, 4), (1, 5), (2, 4), (1, 8)), 6), "Example"
assert checker(find_cycle,
((1, 2), (2, 3), (3, 4), (4, 5), (5, 7), (7, 6), (8, 5), (8, 4), (1, 5), (2, 4)), 5), "Second"
Aug. 29, 2015
