Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Climbing Route by Rounin
import math
def findNeighbours(elevation_map, start):
neighbours = list()
for y in range(-1, 2):
for x in range(-1, 2):
if (y == 0) == (x == 0):
continue # Filter diagonals and the point itself
neighbour = [start[0]+y, start[1]+x]
if neighbour[0] < 0 or neighbour[0] >= len(elevation_map) or neighbour[1] < 0 or neighbour[1] >= len(elevation_map[0]):
continue
neighbours.append(neighbour)
return neighbours
distanceMaps = dict()
shortestRoutes = dict()
# A* shortest path algorithm.
def findShortest(elevation_map, start, end, cutOff = math.inf):
if start == end:
return 0
if abs(end[0]-start[0]) + abs(end[1]-start[1]) >= cutOff:
return math.inf
if str([start,end]) in shortestRoutes:
return shortestRoutes[str([start,end])]
if str([end,start]) in shortestRoutes:
return shortestRoutes[str([end,start])]
if str(start) in distanceMaps:
distanceMap = distanceMaps[str(start)]
else:
distanceMap = list()
for row in range(len(elevation_map)):
distanceMap.append(list())
for col in range(len(elevation_map[row])):
distanceMap[row].append(math.inf)
distanceMap[start[0]][start[1]] = 0
queue = [start]
visited = set()
while len(queue) > 0:
queue = sorted(queue, key=lambda x: -distanceMap[x[0]][x[1]]-abs(end[0]-x[0])+abs(end[1]-x[1]))
currentNode = queue.pop()
if str(currentNode) in visited:
continue
neighbours = findNeighbours(elevation_map, currentNode)
for neighbour in neighbours:
if str(neighbour) in visited:
continue
distanceToNeighbour = (math.inf if abs(elevation_map[neighbour[0]][neighbour[1]] - elevation_map[currentNode[0]][currentNode[1]]) > 1 else 1)
distanceMap[neighbour[0]][neighbour[1]] = min(distanceMap[neighbour[0]][neighbour[1]],
distanceMap[currentNode[0]][currentNode[1]] + distanceToNeighbour)
queue.append(neighbour)
visited.add(str(currentNode))
distanceMaps[str(start)] = distanceMap
shortestRoutes[str([start,end])] = distanceMap[end[0]][end[1]]
return distanceMap[end[0]][end[1]]
def findMountainGroup(elevation_map, row=0, col=0, visited=dict()):
if elevation_map[row][col] == 0 or str([row, col]) in visited:
return None
nodesInGroup = [[row, col]]
visited.add(str([row, col]))
neighbours = findNeighbours(elevation_map, [row, col])
for neighbour in neighbours:
if str(neighbour) in visited or elevation_map[neighbour[0]][neighbour[1]] == 0:
continue
nodesInGroup.append(neighbour)
neighboursOfNeighbour = findMountainGroup(elevation_map, neighbour[0], neighbour[1], visited)
visited.add(str(neighbour))
if neighboursOfNeighbour != None:
nodesInGroup += neighboursOfNeighbour
return nodesInGroup if len(nodesInGroup) > 1 else None
def findMountainGroups(elevation_map):
mountainGroups = list()
visited = set()
for row in range(len(elevation_map)):
for col in range(len(elevation_map[0])):
mountainGroup = findMountainGroup(elevation_map, row, col, visited)
if mountainGroup != None:
mountainGroups.append(mountainGroup)
return mountainGroups
def findMountainTops(elevation_map):
mountainGroups = findMountainGroups(elevation_map)
mountainTops = list()
for mountainGroup in mountainGroups:
height = -1
top = None
for t in mountainGroup:
if(elevation_map[t[0]][t[1]] > height):
height = elevation_map[t[0]][t[1]]
top = t
mountainTops.append(top)
return mountainTops
def findMinRoute(elevation_map, start, end, distance, cutOff, waypoints):
if distance >= cutOff or start == end:
return distance
if len(waypoints) == 0:
return distance + findShortest(elevation_map, start, end, cutOff)
minDistance = math.inf
for waypoint in waypoints:
distanceToNextPoint = findShortest(elevation_map, start, waypoint, cutOff)
newWayPoints = waypoints.copy()
del newWayPoints[newWayPoints.index(waypoint)]
distanceThroughNextPoint = findMinRoute(elevation_map, waypoint, end, distance+distanceToNextPoint, min(minDistance, cutOff), newWayPoints)
if distanceThroughNextPoint < minDistance:
minDistance = distanceThroughNextPoint
return minDistance
def climbing_route(elevation_map):
global shortestRoutes
global distanceMaps
shortestRoutes = dict()
distanceMaps = dict()
for row in range(len(elevation_map)):
elevation_map[row] = list(map(int, list(elevation_map[row])))
mountainTops = findMountainTops(elevation_map)
if len(mountainTops) == 0:
return findShortest(elevation_map, [0,0], [len(elevation_map)-1, len(elevation_map[0])-1])
return findMinRoute(elevation_map, [0,0], [len(elevation_map)-1, len(elevation_map[0])-1], 0, math.inf, mountainTops)
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert climbing_route([
'000',
'210',
'000']) == 6, 'basic'
assert climbing_route([
'00000',
'05670',
'04980',
'03210',
'00000']) == 26, 'spiral'
assert climbing_route([
'000000001',
'222322222',
'100000000']) == 26, 'bridge'
assert climbing_route([
'000000002110',
'011100002310',
'012100002220',
'011100000000']) == 26, 'two top'
assert climbing_route([
'000000120000',
'001002432100',
'012111211000',
'001000000000']) == 16, 'one top'
assert climbing_route([
'00000000111111100',
'00000000122222100',
'00000000123332100',
'00000000123432100',
'00000000123332100',
'00000000122222100',
'00000000111111100',
'00011111000000000',
'00012221000000000',
'00012321000000000',
'00012221000000012',
'00011111000000000',
'11100000000000000',
'12100000000000000',
'11100000000000000']) == 52, 'pyramids'
Oct. 8, 2017