Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dijkstra solution in Uncategorized category for Bats Bunker by Juge_Ti
def intersect(segment1, segment2):
'''Returns True iff segment1 and segment2 are intersecting.'''
a, b = segment1
c, d = segment2
det = (b[0]-a[0])*(c[1]-d[1]) - (b[1]-a[1])*(c[0]-d[0])
det1 = (c[0]-a[0])*(c[1]-d[1]) - (c[1]-a[1])*(c[0]-d[0])
det2 = (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
return det != 0 and 0 <= det1/det <= 1 and 0 <= det2/det <= 1
def intersect_cell(segment, cell):
'''Returns True iff segment intersects cell.'''
a, b = cell
corners = [(a-0.5, b-0.5), (a+0.5, b-0.5), (a+0.5, b+0.5), (a-0.5, b+0.5)]
return any(intersect(segment, (corners[i-1], corners[i])) for i in range(4))
def reachable(bat1, bat2, walls):
'''Return True iff bat1 and bat2 can alert each other.'''
return all(not intersect_cell((bat1, bat2), wall) for wall in walls)
def distance(a, b):
'''Euclidian distance between a and b.'''
return ((b[0]-a[0])**2 + (b[1]-a[1])**2) ** 0.5
def checkio(bunker):
bats, walls = set(), set()
for i, row in enumerate(bunker):
for j, cell in enumerate(row):
if cell == 'B':
bats.add((i, j))
elif cell == 'W':
walls.add((i, j))
elif cell == 'A':
alpha = (i, j)
bats.add((i, j))
bats.remove((0, 0))
d = {(0, 0): 0} # distances to (0, 0)
while alpha not in d:
minimal_distance = float('inf')
for bat1 in d:
for bat2 in bats:
if reachable(bat1, bat2, walls):
dist = d[bat1] + distance(bat1, bat2)
if dist < minimal_distance:
minimal_distance = dist
closest_bat = bat2
bats.remove(closest_bat)
d[closest_bat] = minimal_distance
return round(d[alpha], 2)
Oct. 25, 2013
Comments:
