Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Open Labyrinth by suic
def checkio(labyrinth):
vertices = compute_vertices(labyrinth)
path = lee(vertices, (1, 1), (10, 10))
return convert_to_directions(path)
def compute_vertices(labyrinth):
return [(i, j)
for i in range(len(labyrinth))
for j in range(len(labyrinth[0]))
if not labyrinth[i][j]]
def lee(V, s, t):
"""
Lee algorithm: http://en.wikipedia.org/wiki/Lee_algorithm
V: vertices
s: start vertice
t: target vertice
"""
s, t = t, s
vertices = [[v, 0] for v in V]
labelled = [s]
i = 1
for v in vertices:
if can_move_to(s, v[0]) and (v[0] not in labelled):
v[1] = i
labelled.append(v[0])
while True:
unlabelled_before = len([v[1] for v in vertices if v[1] != 0])
vert = (vs for vs in vertices if vs[1] == i)
for v in vert:
for vs in vertices:
if vs[0] not in labelled and can_move_to(v[0], vs[0]):
vs[1] = i + 1
labelled.append(vs[0])
if t in (vs[0] for vs in vertices if vs[1] == i + 1):
break
unlabelled_after = len([v[1] for v in vertices if v[1] != 0])
if unlabelled_before == unlabelled_after:
raise Exception("No connection")
i += 1
target, tindex = next(v for v in vertices if v[0] == (1, 1))
path = [target]
while s not in path:
tindex -= 1
next_node = next(v[0] for v in vertices
if v[1] == tindex and can_move_to(path[-1], v[0]))
path.append(next_node)
return path
def convert_to_directions(path):
result = []
for i, v in enumerate(path[:-1]):
result.append(get_direction(v, path[i + 1]))
return "".join(result)
def get_direction(fst, nxt):
drc = direction(fst, nxt)
dir_map = {(1, 0): "S",
(-1, 0): "N",
(0, 1): "E",
(0, -1): "W"}
return dir_map[drc]
def can_move_to(fc, tc):
return sum(map(abs, direction(fc, tc))) == 1
def direction(fst, nxt):
return (nxt[0] - fst[0], nxt[1] - fst[1])
Nov. 23, 2014
Comments:
