Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
breadth-first search solution in Clear category for How to Find Friends by YanxiTan
def check_connection(network, first, second):
# Reconfigure network
network1 = []
for dronepair in network:
network1.append(dronepair.split("-"))
# setting up linkages in dictionary
links = {}
for drone_pair in network1:
if drone_pair[0] in links:
links[drone_pair[0]].append(drone_pair[1])
else:
links[drone_pair[0]] = [drone_pair[1]]
if drone_pair[1] in links:
links[drone_pair[1]].append(drone_pair[0])
else:
links[drone_pair[1]] = [drone_pair[0]]
# breadth-first search
queue = [first]
visited = [first]
while queue:
drone = queue.pop(0)
if second in links[drone]:
return True
else:
drone_links = links[drone]
for neighbor in drone_links:
if neighbor not in visited:
visited.append(neighbor)
queue.append(neighbor)
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."
March 24, 2015
