Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
shortest_path solution in 3rd party category for Open Labyrinth by gyahun_dash
from itertools import accumulate
from scipy import argwhere, array
from scipy.linalg import norm
from scipy.sparse.csgraph import shortest_path
def checkio(maze):
nodes = argwhere(array(maze) == 0)
edges = array([[int(norm(m - n, 1) == 1) for m in nodes] for n in nodes])
dist, pred = shortest_path(edges, return_predecessors=True)
# nodes[0] = (1, 1), nodes[-1] = (10, 10)
steps = range(1 + int(dist[0, -1]))
route = nodes[list(accumulate(steps, func=lambda i, s: pred[-1, i]))]
dirs = {(-1, 0): 'N', (0, 1): 'E', (0, -1): 'W', (1, 0): 'S'}
return ''.join(dirs[tuple(diff)] for diff in route[1:] - route[:-1])
Jan. 6, 2017
