Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Bats Bunker by Moff
from collections import namedtuple, defaultdict
from math import hypot
Cell = namedtuple('Cell', 'x y')
def intersertions(p1, p2):
cells = set()
for x in range(min(p1.x, p2.x), max(p1.x, p2.x)):
y = (x + 0.5 - p1.x) * (p2.y - p1.y) / (p2.x - p1.x) + (p1.y + 0.5)
iy = int(y)
cells |= {Cell(x, iy), Cell(x+1, iy)}
if iy == y:
cells |= {Cell(x, iy - 1), Cell(x+1, iy -1)}
for y in range(min(p1.y, p2.y), max(p1.y, p2.y)):
x = (y + 0.5 - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + (p1.x + 0.5)
ix = int(x)
cells |= {Cell(ix, y), Cell(ix, y+1)}
if ix == x:
cells |= {Cell(ix-1, y), Cell(ix-1, y+1)}
return sorted(cells)
def dijkstra(graph, start, end):
distance = dict.fromkeys(graph, float('inf'))
distance[start] = 0
vertex = set(graph)
while vertex:
v = min(vertex, key=distance.get)
vertex.remove(v)
for w, weight in graph[v].items():
distance[w] = min(distance[w], distance[v] + weight)
return distance.get(end)
def checkio(m):
bats = []
for i, row in enumerate(m):
for j, v in enumerate(row):
if v in 'AB':
bats.append(Cell(i, j))
if v == 'A':
alpha_bat = Cell(i, j)
graph = defaultdict(dict)
for i, b1 in enumerate(bats):
for b2 in bats[i+1:]:
if all(m[cell.x][cell.y] != 'W' for cell in intersertions(b1, b2)):
d = hypot(b1.x - b2.x, b1.y - b2.y)
graph[b1][b2] = d
graph[b2][b1] = d
return dijkstra(graph, Cell(0, 0), alpha_bat)
Aug. 26, 2015
Comments:
