Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
3D solution in Speedy category for Express Delivery by veky
class Node: #mixin 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(field):
class EDNode(Node, tuple):
heuristic = lambda *l: sum(abs(a - b) for a, b in zip(*l))
def neighbors(self):
i, j, k = self
if i < 0 or j < 0: return
try: c = field[i][j]
except IndexError: return
if c == 'B': yield EDNode((i, j, not k)), c, 1
if c != 'W':
for e, f, w in ((1,0,"D"),(-1,0,"U"),(0,1,"R"),(0,-1,"L")):
yield EDNode((i + e, j + f, k)), w, k + 1
def locate(what):
for i, row in enumerate(field):
try: return EDNode((i, row.index(what), True))
except ValueError: pass
return "".join(locate("S").astar(locate("E")))
Feb. 22, 2014
Comments:
