Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First - Open Labyrinth solution in Clear category for Open Labyrinth by AQiccl135
def checkio(maze_map, start = (1, 1), end = (10, 10), path_value = 0):
"""
This function searches each step of a maze until the end is found, or
until all steps have been searched. If the end was found, a string of
compass directions for the shortest path from start to end is returned.
Algorithm from Amit Patel
http://www.redblobgames.com/pathfinding/a-star/introduction.html
"""
cross = [[-1,0], [0,1], [1,0], [0,-1]]
steps = [start]
past = {}
past[start] = None
while steps:
cell = steps[0]
del steps[0]
if cell == end:
break
placeholder = [(cell[0] + d[0], cell[1] + d[1]) for d in cross]
for next in placeholder:
x, y = next[0], next[1]
if next not in past and maze_map[x][y] == path_value:
steps.append(next)
past[next] = (cell, "NESW"[placeholder.index(next)])
if cell == end:
path = [cell]
while cell != start:
cell = past[cell][0]
path.append(cell)
path = path[::-1]
return ''.join([past[c][1] for c in path[1:]])
else:
return ""
Dec. 16, 2014
