Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Bats Bunker without dijkstra solution in Uncategorized category for Bats Bunker by capback250
# migrated from python 2.7
from math import hypot
def checkio(coorinates):
rotate = lambda a, b, c: (b[0]-a[0])*(c[1]-b[1])-(b[1]-a[1])*(c[0]-b[0])
euclidianDistance = lambda a, b: hypot(a[0] - b[0], a[1] - b[1])
walls, bats, alpha, graf = [], [], [], {}
combos = [[0, 0], [0, 1], [1, 0], [1, 1]]
for id1, val1 in enumerate(coorinates):
for id2, val2 in enumerate(val1):
if val2 == 'B':
bats.append([id1, id2])
if val2 == 'W':
walls.append([id1, id2])
if val2 == 'A':
bats.append([id1, id2])
alphaPos = (id1, id2)
if not ''.join(coorinates).count('W'):
return round(euclidianDistance((0, 0), alphaPos), 2)
for bat in bats:
visible = []
for neib in [x for x in bats if x != bat]:
xc = min([bat[0], neib[0]]) + abs(bat[0] - neib[0]) / 2.0
yc = min([bat[1], neib[1]]) + abs(bat[1] - neib[1]) / 2.0
r = hypot(bat[0] - neib[0], bat[1] - neib[1]) / 2.0
wallsinPolygon = [wall for wall in walls if hypot(xc - wall[0] + 0.5, yc - wall[1] + 0.5) <= r + 0.4]
innerCalc = [[rotate([bat[0] + 0.5, bat[1] + 0.5], [neib[0] + 0.5, neib[1] + 0.5], [fwal[0] + i, fwal[1] + j]) for i, j in combos] for fwal in wallsinPolygon]
if all([sum([int(x >= 0) for x in s]) in [0, 4] for s in innerCalc]) and not sum([1 for x in innerCalc if x.count(0)]):
visible.append((neib[0], neib[1]))
graf[(bat[0], bat[1])] = visible
return round(min([sum([euclidianDistance(x[i], x[i+1]) for i in range(len(x)-1)]) for x in find_all_paths(graf, (0, 0), alphaPos)]), 2)
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
Feb. 3, 2016
