Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
4D solution in Clear category for Haunted House by veky
class Node:
"mixin class for A*"
heuristic = lambda self, goal: 0 #must be monotonic
def astar(self, goal):
cl, op, parent, kls = set(), {self}, {}, type(self)
g, f = {self: 0}, {self: self.heuristic(goal)}
while op:
t = min(op, key=f.get)
op.remove(t)
if t == goal:
path = []
while t is not self:
t, way = parent[t]
path.append(way)
path.reverse()
return path
cl.add(t)
for u, way, dist in t.neighbors():
if u not in cl:
gu = g[t] + dist
if u not in op or gu < g[u]:
parent[u] = t, way
g[u] = gu
f[u] = gu + u.heuristic(goal)
op.add(u)
def checkio(house, stephan, ghost):
from collections import namedtuple
walls = list(map(set, house))
for w in walls[:4]: w.add("N")
for w in walls[12:]: w.add("S")
for w in walls[::4]: w.add("W")
for w in walls[3::4]: w.add("E")
class Room(Node, namedtuple("_", "Stefan ghost")):
def neighbors(room):
eS, eg = ({r + d: way for way, d in zip("EWSN", (1, -1, 4, -4))
if way not in walls[r - 1]} for r in room)
if room.Stefan != room.ghost:
if room.Stefan == 1: yield Room(StopIteration, ...), "N", 1
for escape in eS:
def far(pursue):
coor = lambda x: divmod(x - 1, 4)
(Sx, Sy), (gx, gy) = coor(escape), coor(pursue)
return (Sx - gx)**2 + (Sy - gy)**2
yield Room(escape, min(eg, key=far)), eS[escape], 1
return Room(stephan, ghost).astar(Room(StopIteration, ...))[0]
March 6, 2014
Comments: