Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Supercover line solution in Speedy category for Bats Bunker by DiZ
def supercover(p1, p2):
"""Returns all grid squares on line [p1, p2]
Based on Eugen Dedu's implementation
http://lifc.univ-fcomte.fr/home/~ededu/projects/bresenham/"""
cmp = lambda a, b: [-1, 1][a < b]
(x1, y1), (x2, y2), points = p1, p2, {p1, p2}
x, y = x1, y1
dx, dy = x2 - x1, y2 - y1
# Octant correction
step = cmp(abs(dx), abs(dy))
if step < 0:
x, dx, y, dy = y, dy, x, dx
xstep, ystep = cmp(0, dx), cmp(0, dy)
dx, dy = abs(dx), abs(dy)
ddy, ddx = 2 * dy, 2 * dx
# Mark neighbours of p1 in direction of p2
errorprev = error = dy
for _ in range(int(dy)):
y += ystep
error += ddx
if error > ddy:
x += xstep
error -= ddy
if error + errorprev <= ddy:
points.add((x - xstep, y)[::step])
if error + errorprev >= ddy:
points.add((x, y - ystep)[::step])
points.add((x, y)[::step])
errorprev = error
return points
def dijkstra(vertices, edges, start, alpha):
bag = {start: 0}
while bag:
# Find the m_node with the lowest distance
m_node = min(bag, key=bag.get)
dist = bag.pop(m_node)
if m_node in alpha:
return dist
# Update distances for nodes that are connected to m_node
for dest in vertices:
e = tuple(sorted((m_node, dest)))
if e in edges:
bag[dest] = min(bag.get(dest, float('inf')), dist + edges[e])
del edges[e]
def checkio(bunker_map):
from itertools import combinations
from math import hypot
# Initiate GRID
bunker = {char: set() for char in '-ABW'}
for y, row in enumerate(bunker_map):
for x, char in enumerate(row):
bunker[char].add((x + .5, y + .5))
bunker['B'] |= bunker['A']
# Get lines without obstacles
edges = [line for line in combinations(sorted(bunker['B']), 2)
if not bunker['W'] & supercover(*line)]
# Create graph with weights
graph = {(n1, n2): hypot(n1[0] - n2[0], n1[1] - n2[1]) for n1, n2 in edges}
# Call Dijkstra
return dijkstra(bunker['B'], graph, (.5, .5), bunker['A'])
Sept. 2, 2014
Comments:
