Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Simple Recursion solution in Clear category for How to Find Friends by JeremyJustus
def check_connection(network, first, second):
"""
This base function builds a dictionary to hold each node and a list
of all the nodes it connects to.
"""
# Each dictionary has the node name as the key, and a list of adjacent
# nodes as its value.
dronebook = dict()
for connection in network:
# Grab each pair and split it into two strings, splitting at the '-'.
node1 = connection.split('-', 1)[0]
node2 = connection.split('-', 1)[1]
# If each value isn't already in the book, add it. Then, add the new
# neighbor to its list.
if node1 not in dronebook:
dronebook[node1] = list()
dronebook[node1].append(node2)
if node2 not in dronebook:
dronebook[node2] = list()
dronebook[node2].append(node1)
# Create a second list to hold which values we've checked so far.
checked = list()
checked.append(first)
# Initiate our recursive function, starting with the first node
# given as our current node.
return checker(dronebook, first, second, checked)
def checker(dronebook, current, goal, checked):
"""
This recursive helper function checks each value in the dictionary key and
does the same for all of the neighbors in its list.
"""
# print("Current: {}\nGoal: {}\nChecked:{}\n".format(current, goal, checked))
for entry in dronebook[current]:
if entry == goal: # Horray! Found it!
return True
elif entry not in checked: # We haven't checked this one yet.
checked.append(entry)
# This return makes this a recursive method, doing this same process
# for the next item in the list (and doing this same process for the
# next item in the list, (and...))
return checker(dronebook, entry, goal, checked)
else: # We've already checked this one from another node; skip it.
continue
# We only reach this point if we've gone over the full set of linked
# nodes. If we haven't returned True before now, these two can't be linked.
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."
Feb. 18, 2015
