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 marcelina.gorzelana
def to_dictionary(network):
tmp = ""
val = 0
for i in range(len(network)):
pair = network[i].split('-')
if tmp.find(pair[0]) == -1:
tmp+= pair[0] + "-" + str(val) + ","
val+= 1
if tmp.find(pair[1]) == -1:
tmp+= pair[1] + "-" + str(val) + ","
val+= 1
s = tmp[: len(tmp) - 1]
return dict((k, int(v)) for k,v in
(item.split('-') for item in s.split(',')))
def check_connection(network, first, second):
dict = to_dictionary(network)
adjacencylist = []
visited = []
for n in range(len(list(dict.items()))):
adjacencylist.append([])
visited.append(0)
for p in network:
pair = p.split('-')
adjacencylist[ dict[ pair[0]]].append(dict[ pair[1]])
adjacencylist[ dict[ pair[1]]].append(dict[ pair[0]])
cur = dict[first]
sought = dict[second]
stack = [cur]
while cur != sought and len(stack) > 0:
cur = stack[len(stack) - 1]
stack.pop()
if visited[cur] == 0:
visited[cur] = 1
while len(adjacencylist[cur]) > 0:
if visited[ adjacencylist[cur][ len(adjacencylist[cur]) - 1]] == 0:
stack.append(adjacencylist[cur][ len(adjacencylist[cur]) - 1])
adjacencylist[cur].pop()
if cur == sought:
return True
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."
Dec. 4, 2016
