Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Tremaux solution in Creative category for Dark Labyrinth by gyahun_dash
from itertools import groupby, product
dirs = dict(zip((-1j, 1, -1, 1j), 'NEWS'))
unit = lambda z: z / abs(z)
branches, route = {}, []
def find_path(maze):
coords = tuple(product(*map(range, map(len, (maze, maze[0])))))
find = lambda xs: set(complex(c, r) for r, c in coords if maze[r][c] in xs)
relp, goal, area = find('P').pop(), find('E'), find('.EP')
if not route: route.append(0)
absp = route[-1]
hasturn = lambda drs: any(d.real for d in drs) and any(d.imag for d in drs)
if absp not in branches:
cross = (z for z in area if z != relp and unit(z - relp) in dirs)
steps = {z: [d for d in dirs if z + d in area] for z in cross}
diffs = (z - relp for z in steps if z in goal or hasturn(steps[z]))
az = dict(key=lambda z: dirs[unit(z)])
mins = (min(g, key=abs) for i, g in groupby(sorted(diffs, **az), **az))
branches[absp] = set(d + absp for d in mins) - set(route)
getpath = lambda src, dst: dirs[unit(dst - src)] * int(abs(dst - src))
if not branches[absp]: return getpath(route.pop(), route[-1])
dst = branches[absp].pop()
route.append(dst)
if goal and dst == goal.pop() - relp + absp:
branches.clear()
route.clear()
return getpath(absp, dst)
Oct. 26, 2014