Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Bats Bunker by 1-more
# migrated from python 2.7
def checkio(bunker):
bets, walls, alpha = [], [], None
def is_visible(a, b):
ax,ay= min(a,b)
bx,by= max(a,b)
walls_between= [(wx,wy) for wx,wy in walls
if ax<=wx<=bx and min(ay,by)<=wy<=max(ay,by)]
if ax==bx or ay==by: return len(walls_between)==0
f= lambda x: (by-ay)*(x-ax)/(bx-ax) + ay
for wx,wy in walls_between:
if ((wy-0.5 <= f(wx+0.5) and f(wx-0.5) <= wy+0.5) or
(wy+0.5 >= f(wx+0.5) and f(wx-0.5) >= wy-0.5)): return False
return True
# Fill bets, walls and alpha from bunker
for i,row in enumerate(bunker):
for j,cell in enumerate(row):
if cell=='-': continue
pos= (i,j)
if cell=='W':
walls.append(pos)
else:
bets.append(pos)
if cell=='A': alpha= pos
# Calculations
stack= [(0,0)]
time= {(0,0):0}
visited= set()
while stack:
bet= stack.pop(0)
visited.add(bet)
betx,bety= bet
for b in [x for x in bets if x not in visited and is_visible(bet, x)]:
bx,by= b
time[b]= min(
time.get(b, float('inf')),
time[bet]+((betx-bx)**2+(bety-by)**2)**0.5
)
if b!=alpha: stack.append(b)
return time.get(alpha, float('inf'))
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
def almost_equal(checked, correct, significant_digits=2):
precision = 0.1 ** significant_digits
return correct - precision < checked < correct + precision
assert almost_equal(checkio([
"B--",
"---",
"--A"]), 2.83), "1st example"
assert almost_equal(checkio([
"B-B",
"BW-",
"-BA"]), 4), "2nd example"
assert almost_equal(checkio([
"BWB--B",
"-W-WW-",
"B-BWAB"]), 12), "3rd example"
assert almost_equal(checkio([
"B---B-",
"-WWW-B",
"-WA--B",
"-W-B--",
"-WWW-B",
"B-BWB-"]), 9.24), "4th example"
Jan. 27, 2015
Comments:
