Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Bats Bunker by Flid
# migrated from python 2.7
import math
from heapq import heappop, heappush
sign = lambda x: 1 if x > 0 else (-1 if x < 0 else 0)
def dijkstra(graph, from_ind, to_ind):
"""
My brand new Dijkstra's algorithm implementation =)
"""
min_path = {i: float('inf') for i in graph}
min_path[from_ind] = 0
processed = set()
heap = [(0, from_ind)]
# To speed up the 'if x in heap' statement
heaped = set([from_ind])
while heap:
_, bat_ind = heappop(heap)
heaped.remove(bat_ind)
processed.add(bat_ind)
for adj_bat, weight in graph[bat_ind].items():
if adj_bat in processed:
continue
min_path[adj_bat] = min(
min_path[adj_bat],
min_path[bat_ind] + weight,
)
if adj_bat not in heaped:
heappush(heap, (min_path[adj_bat], adj_bat))
heaped.add(adj_bat)
if bat_ind == to_ind:
break
return min_path[to_ind]
def distance(bats, bat_index1, bat_index2, walls):
"""
Returns a distance between two bats, or 'inf', if there is a wall.
"""
# Every bat is located at the midle of the cell, so we add 0.5
x1 = bats[bat_index1][1] + 0.5
y1 = bats[bat_index1][0] + 0.5
x2 = bats[bat_index2][1] + 0.5
y2 = bats[bat_index2][0] + 0.5
if x1 == x2 and y1 == y2:
return 0
# Distance between bats.
dist = math.sqrt((x1 - x2)**2 + (y1-y2)**2)
# Lets' represent a line formed by two bats as a*x + b*y + c = 0
a = y2 - y1
b = x1 - x2
c = y1*x2 - x1*y2
# If two point are on one cide of the line, they'll have
# the same value of this function:
side_sign = lambda x, y: sign(a*x + b*y + c)
projection_len = lambda x, y: ((x2-x1)*(x-x1) + (y2-y1)*(y-y1)) / dist
# Let's check every wall, whether the interval between two bats
# crosses this wall. How can we do that? Look:
# Every wall has 4 points. If all the point are on the same side of the
# "bats-line", then line do not cross this wall.
# We should also discard all the walls, which are crossed by
# the "bats-line", but not "bats-interval".
for wy, wx in walls:
sides = []
for i in range(2):
for j in range(2):
plen = projection_len(wx+i, wy+j)
if plen < 0 or plen > dist:
# Wall doesn't intersect with "bats-interval"
continue
sides.append(side_sign(wx+i, wy+j))
# Check whether all the items in 'sides' are the same
if sum([j != sides[0] for j in sides]) > 0:
# "bats-interval" crosses this wall!
return float('inf')
return dist
def checkio(bunker):
bats = [None, (0, 0)]
walls = []
if bunker[0][0] == 'A':
return 0
# Search for all the bats and walls.
# Place Alpha-bat to bats[0]
for i, line in enumerate(bunker):
for j, cell in enumerate(line):
if i + j == 0:
continue
if cell == 'B':
bats.append((i, j))
elif cell == 'A':
bats[0] = (i, j)
elif cell == 'W':
walls.append((i, j))
# Compute the distance between every two bats.
N = len(bats)
bats_distances = {bat1: {
bat2: distance(bats, bat1, bat2, walls) for bat2 in range(N)
} for bat1 in range(N)}
for bat1 in range(N):
for bat2 in range(N):
if bats_distances[bat1][bat2] in (0, float('inf')):
del bats_distances[bat1][bat2]
# Find the shortest path between 0 (Alpha) and 1 (Target) bat.
return dijkstra(bats_distances, 0, 1)
July 17, 2014
