Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Bats Bunker solution in 3rd party category for Bats Bunker by JimmyCarlos
import numpy as np
def checkio(bunker):
adjDistance,rootNode,destinationNode = create_adjDistance(bunker)
distanceToAlphaBat = dijkstras(adjDistance,rootNode,destinationNode)
return distanceToAlphaBat
def create_adjDistance(bunker):
W,H = len(bunker[0]),len(bunker)
nodes = [(R,C) for R in range(H) for C in range(W) if bunker[R][C] in "AB"]
nodeAmount = len(nodes)
adjDistance = [[float("inf") for C in range(nodeAmount)] for R in range(nodeAmount)]
for a in range(nodeAmount):
for b in range(a+1,nodeAmount):
(aR,aC),(bR,bC) = nodes[a],nodes[b]
if not is_clearRoute(aR,aC,bR,bC,bunker): continue
edgeWeight = ((bR-aR)**2 + (bC-aC)**2)**0.5
adjDistance[a][b],adjDistance[b][a] = edgeWeight,edgeWeight
alphaBatLocation = [i for i,(R,C) in enumerate(nodes) if bunker[R][C] == "A"][0]
rootNode,destinationNode = 0,alphaBatLocation
return adjDistance,rootNode,destinationNode
def is_clearRoute(aR,aC,bR,bC,bunker):
# I feel like there could be a better way to do this?
if aR == bR: return not any(bunker[aR][C] == "W" for C in range(min(aC,bC),max(aC,bC)+1))
if aC == bC: return not any(bunker[R][aC] == "W" for R in range(min(aR,bR),max(aR,bR)+1))
if aR > bR: aR,aC,bR,bC = bR,bC,aR,aC
dR = bR-aR
dC = bC-aC
for R in np.arange(aR,bR+0.01,0.01):
C = aC + (R-aR)/(dR) * dC
if round(R-0.5,5).is_integer() and round(C-0.5,5).is_integer():
if any(bunker[int(round(r,0))][int(round(c,0))] == "W" for r,c in ((R-0.5,C-0.5),(R-0.5,C+0.5),(R+0.5,C-0.5),(R+0.5,C+0.5))): return False
else:
if bunker[int(round(R,0))][int(round(C,0))] == "W": return False
else:
return True
def dijkstras(adjDistance,rootNode,destinationNode) -> int:
"""Finds the weight between two nodes on a network."""
N = len(adjDistance)
finalValues,workingValues = {},{i:float("inf") for i in range(N)}
workingValues[rootNode] = 0
while len(workingValues) > 0:
nodeToLockIndex,nodeToLockValue = min(workingValues.items(), key=lambda x:x[1])
finalValues[nodeToLockIndex] = nodeToLockValue
for outNodeIndex in range(N):
if outNodeIndex in finalValues: continue
totalDistanceToOutNode = nodeToLockValue + adjDistance[nodeToLockIndex][outNodeIndex]
workingValues[outNodeIndex] = min(workingValues[outNodeIndex], totalDistanceToOutNode)
workingValues.pop(nodeToLockIndex)
if nodeToLockIndex == destinationNode: break
return finalValues[destinationNode]
April 27, 2019
Comments: