Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Network Loops by Vasily__Chibilyaev
def find_cycle(connections):
def get_max_cycle(connections, max_cycle=[], chain=[]):
# count number of possible paths through connection
p = lambda con: sum(1 for c in connections if con[0] in c and con!=c)*\
sum(1 for c in connections if con[1] in c and con!=c)
# estimate next origin
if len(chain)==0:
while True:
con_to_remove = next((c for c in connections if p(c)==0), None)
if con_to_remove!=None:
connections.remove(con_to_remove)
else:
break
origin = next((n for con in connections for n in con), None)
if origin!=None:
max_cycle = get_max_cycle(connections, max_cycle, [origin])
for con in [c for c in connections if origin in c]:
connections.remove(con)
return max_cycle
# cycle spotted!
elif len(chain)>3 and chain[0]==chain[-1]:
return max(chain, max_cycle, key = len)
# get next node for existing chain and continue
else:
for s, e in connections:
if chain[-1]==s and e not in chain[1:] or chain[-1]==e and s not in chain[1:]:
next_node = e if chain[-1]==s else s
if next_node==chain[0] and len(chain)+1==3: continue
max_cycle = get_max_cycle(connections, max_cycle, chain+[next_node])
return max_cycle
connections = list(connections)
return get_max_cycle(connections)
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"
April 10, 2018
Comments:
