Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for How to Find Friends by Kurush
from collections import deque
def check_connection(network, first, second):
network = sorted(network)
network_dict = dict()
visited_dict = dict()
for node in network:
values = node.split("-")
if (values[0] not in network_dict):
network_dict[values[0]] = set()
visited_dict[values[0]] = 0
if (values[1] not in network_dict):
network_dict[values[1]] = set()
visited_dict[values[1]] = 0
network_dict[values[0]].add(values[1])
network_dict[values[1]].add(values[0])
current = first
PosQueue = deque()
PosQueue.append(current);
while True:
if not PosQueue: break
current = PosQueue.popleft()
visited_dict[current] = 1
for elem in network_dict[current]:
if elem == second:
return True
else:
if visited_dict[elem] == 0:
PosQueue.append(elem)
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."
June 9, 2014
