Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
frozenbat solution in Speedy category for Bats Bunker 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(bunker):
class Bat(Node, tuple):
def heuristic(self, goal):
return abs(complex(*self) - complex(*goal))
def neighbors(self):
for b in bats:
d = distance.get(frozenset({self, b}))
if d: yield b, d, d
s=lambda A,B,C: (A[0]-C[0])*(B[1]-C[1])-(A[1]-C[1])*(B[0]-C[0])
block = lambda A,B,C,D: s(A,B,C)*s(A,B,D)<=0>=s(C,D,A)*s(C,D,B)
walls, distance = set(), {}
for i, row in enumerate(bunker):
for j, cell in enumerate(row):
if cell in 'AB':
b = Bat((2*j + 1, -2*i - 1))
if i or j: bats.add(b)
else: bats, Entry = {b}, b
if cell == 'A': Alpha = b
if cell == 'W':
x, y, X, Y = 2*j, -2*i, 2*j + 2, -2*i - 2
walls |= {((x,y),(X,y)),((X,y),(X,Y)),((x,y),(x,Y))}
for b1, b2 in __import__("itertools").combinations(bats, 2):
if not any(block(b1, b2, *wall) for wall in walls):
distance[frozenset({b1,b2})] = b1.heuristic(b2)
return round(sum(Entry.astar(Alpha)) / 2, 2)
Feb. 22, 2014
Comments:
