Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Disposable Teleports by PositronicLlama
"""
Find a (potentially non-simple) path over a graph that
visits each vertex at least once, and uses each edge no
more than once.
Note: This is not a Hamiltonian cycle because a vertex
may be visited more than once.
"""
import collections
# The starting and ending node.
GOAL = 1
def build_graph(edges):
"""
Return a mapping from node to a list of adjacent nodes.
edges: A comma-separated list of 'ab' strings, where
a and b are node numbers [1-8].
"""
graph = collections.defaultdict(list)
for edge in edges.split(','):
a, b = [ord(c) - ord('0') for c in edge]
graph[a].append(b)
graph[b].append(a)
return graph
def to_result(nodes):
"""
Return a string of node identifiers.
nodes: A sequence of node indices.
"""
return ''.join('{}'.format(ix) for ix in nodes)
def tuple_sort(a, b):
"""Return a sorted tuple of two items."""
# More than twice as fast as tuple(sorted((a, b)))
# according to 'timeit'
if a < b:
return (a, b)
return (b, a)
def checkio(teleports):
"""
Return a cycle that visits each vertex in the given graph.
The path starts at the first node, and each node must be
visited at least once. No edge may be used more than once.
teleports: A comma separated list of edges.
Return a string listing the nodes to visit in order.
"""
graph = build_graph(teleports)
num_nodes = len(graph)
# Each entry in 'pending' consists of a partial path and a set
# of explored edges.
pending = [((x, GOAL), frozenset([tuple_sort(x, GOAL)])) for x in graph[GOAL]]
# Use depth-first search to find the shortest path that does
# not reuse any edge and visits all nodes.
while pending:
path, edges = pending.pop(0)
initial = path[0]
adjacent = graph[initial]
for node in adjacent:
# Check whether this edge has already been used.
edge = tuple_sort(node, initial)
if edge in edges:
continue
# Return once we have found a path through all nodes
# which can start at the goal.
if node == GOAL and len(set(path)) == num_nodes:
return to_result((GOAL,) + path)
# Otherwise, push a new potential path onto pending.
new_path = (node,) + path
new_edges = edges | frozenset((edge,))
pending.append((new_path, new_edges))
# Failure, no path could be found.
raise AssertionError("Path expected for graph {}".format(graph))
if __name__ == "__main__":
print(checkio("12,23,34,45,56,67,78,81")) #"123456781"
print(checkio("12,28,87,71,13,14,34,35,45,46,63,65")) #"1365417821"
print(checkio("12,15,16,23,24,28,83,85,86,87,71,74,56")) #"12382478561"
print(checkio("13,14,23,25,34,35,47,56,58,76,68")) #"132586741"
April 25, 2013
Comments: