Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for How to Find Friends by Sarina
from collections import defaultdict
def check_connection(network, first, second):
# build neighbors
neighbors = defaultdict(set)
for node in network:
n1,n2 = tuple(node.split('-'))
neighbors[n1].add(n2)
neighbors[n2].add(n1)
found = False
visited = set([first])
future = set(neighbors[first])
while not found and len(future):
neighbor = future.pop()
if neighbor == second:
found = True
else:
visited.add(neighbor)
future = future.union([n for n in neighbors[neighbor] if n not in visited])
if found:
return True
return False
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert check_connection(
("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
"scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
"scout2", "scout3") == True, "Scout Brotherhood"
assert check_connection(
("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
"scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
"super", "scout2") == True, "Super Scout"
assert check_connection(
("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
"scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
"dr101", "sscout") == False, "I don't know any scouts."
Nov. 24, 2019
Comments:
