Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Network Loops by brownie57
from collections import deque
from copy import copy
def find_cycle(connections):
loop_list = []
connection_list = list(connections)
queue = deque([[1]])
while queue:
loop = queue.pop()
for i in [x for x in connection_list if loop[-1] in x]:
copied_loop = copy(loop)
end = i[0] if copied_loop[-1] == i[1] else i[1]
if end in copied_loop:
if copied_loop[-2] != end:
copied_loop.append(end)
n = loop.index(end)
loop_list.append(copied_loop[n:])
else:
queue.append(copied_loop + [end])
if loop_list:
return max(loop_list, key=len)
else:
return loop_list
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, 4), (1, 5), (2, 4)), 5), "Second"
Feb. 13, 2019
Comments:
