Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
dfs-algo solution in Clear category for Disposable Teleports by iggymas
# migrated from python 2.7
from collections import defaultdict
from copy import deepcopy
all_nodes = {str(i) for i in range(1, 9)}
def checkio(teleports_string):
nodes_bind = defaultdict(list)
for line in teleports_string.split(","):
if not line[1] in nodes_bind[line[0]]:
nodes_bind[line[0]].insert(0, line[1])
if not line[0] in nodes_bind[line[1]]:
nodes_bind[line[1]].append(line[0])
full_path = '1' + get_dfs('1', nodes_bind, {'1'})
return full_path
#using dfs algorithm
def get_dfs(current_node, graph, visited_nodes):
for available in graph[current_node]:
possible_way = visited_nodes.copy()
possible_way.add(available)
possible_graph = deepcopy(graph)
possible_graph[current_node].remove(available)
possible_graph[available].remove(current_node)
if available == '1' and possible_way == all_nodes:
return available
path = get_dfs(available, possible_graph, possible_way)
if path is not None:
return available + path
return
#This part is using only for self-testing
if __name__ == "__main__":
def check_solution(func, teleports_str):
route = func(teleports_str)
teleports_map = [tuple(sorted([int(x), int(y)])) for x, y in teleports_str.split(",")]
if route[0] != '1' or route[-1] != '1':
print("The path must start and end at 1")
return False
ch_route = route[0]
for i in range(len(route) - 1):
teleport = tuple(sorted([int(route[i]), int(route[i + 1])]))
if not teleport in teleports_map:
print(("No way from {0} to {1}".format(route[i], route[i + 1])))
return False
teleports_map.remove(teleport)
ch_route += route[i + 1]
for s in range(1, 9):
if not str(s) in ch_route:
print(("You forgot about {0}".format(s)))
return False
return True
assert check_solution(checkio, "12,23,34,45,56,67,78,81"), "First"
assert check_solution(checkio, "12,28,87,71,13,14,34,35,45,46,63,65"), "Second"
assert check_solution(checkio, "12,15,16,23,24,28,83,85,86,87,71,74,56"), "Third"
assert check_solution(checkio, "13,14,23,25,34,35,47,56,58,76,68"), "Fourth"
March 31, 2014
