Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Graph It solution in Clear category for How to Find Friends by maximusderango
import collections
def check_connection(network, first, second):
"""
Function take start and end members, create usable graph from network and determine if connection
with "recursive()" function.
Boolean
"""
graph = collections.defaultdict(list)
relations = [a.split("-") for a in network] # unpack the strings into pair lists
for i in relations: # populate the graph with each member as a key and all
graph[i[0]].append(i[1]) # of the surrounding neighbors in a list as its value
graph[i[1]].append(i[0])
return recursive(graph, first, second, path = [])
def recursive(graph, f, s, path = []):
"""
Recursive function take start and end members, the graph from "check_connection()" and determine
if there is a connection.
Boolean
"""
path = path + [f] # update the current path
if f == s:
return True
elif f not in graph: # catches members that don't exist in the graph
return False
for node in graph[f]:
if node not in path:
return recursive(graph, node, s, path)
else: 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."
July 29, 2014
