Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dijkstra, equation and round functions solution in Clear category for Bats Bunker by Phil15
from math import ceil, floor, hypot, inf
from itertools import chain, product
distance = lambda xA, yA, xB, yB: hypot(xB - xA, yB - yA)
EMPTY, WALL, BAT, ALPHA_BAT = ".WBA"
def alert_line_boxes(xA, yA, xB, yB):
"""Generate the boxes through which the line from A to B passes."""
if xA == xB:
return ((xA, y) for y in range(min(yA, yB) + 1, max(yA, yB)))
elif yA == yB:
return ((x, yA) for x in range(min(xA, xB) + 1, max(xA, xB)))
else:
# Alert line have "y = m * x + p" / "x = (y - p) / m" for equation
m = (yB - yA) / (xB - xA)
p = yA - m * xA
# We look pts on the line between A and B, with x/y increasing of .5
x_pts = ((t/2, m * t/2 + p) # range(min + 0.5, max, 0.5)
for t in range(2 * min(xA, xB) + 1, 2 * max(xA, xB)))
y_pts = (((t/2 - p) / m, t/2) # range(min + 0.5, max, 0.5)
for t in range(2 * min(yA, yB) + 1, 2 * max(yA, yB)))
# We round those points to have integer coordinates of real boxes.
round_functions = lambda x: ceil(x - 0.5), lambda x: floor(x + 0.5)
return ((f(x), g(y)) for x, y in chain(x_pts, y_pts)
for f, g in product(round_functions, repeat=2))
def checkio(bunker):
"""Distance between (0, 0) and alpha bat (with Dijkstra on bats network)."""
if bunker[0][0] == ALPHA_BAT:
return 0
bats = {(i, j) for i, row in enumerate(bunker)
for j, cell in enumerate(row)
if cell in (BAT, ALPHA_BAT)}
alpha = next((i, j) for i, j in bats if bunker[i][j] == ALPHA_BAT)
neighbors = {bat1: {bat2 for bat2 in bats - {bat1}
if all(bunker[i][j] != WALL
for i, j in alert_line_boxes(*bat1, *bat2))}
for bat1 in bats}
dist = {bat: 0 if bat==(0, 0) else inf for bat in bats}
while bats:
batman = min(bats, key = lambda x: dist[x])
bats.remove(batman)
for bat in neighbors[batman]:
dist[bat] = min(dist[bat], dist[batman] + distance(*batman, *bat))
return round(dist[alpha], 2)
Sept. 21, 2018
Comments:
