Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
38-liner: clean solution in Clear category for Climbing Route by przemyslaw.daniel
def find_tops(terrain, valid):
for x, y in valid:
stack, (x_top, y_top), visited = [(x, y)], (x, y), set()
while stack:
i, j = stack.pop()
if (i, j) in visited or terrain[i][j] == '0':
continue
if int(terrain[i][j]) > int(terrain[x_top][y_top]):
x_top, y_top = i, j
visited |= {(i, j)}
stack += list({(i+1, j), (i-1, j), (i, j+1), (i, j-1)} & valid)
yield from [(x_top, y_top)]*(terrain[x][y] == '1' and len(visited) > 1)
def calc_shortest(start, stop, terrain, valid):
from heapq import heappush, heappop
queue, visited = [(0, *start)], set()
while queue:
length, x, y = heappop(queue)
if (x, y) == stop:
return length
if (x, y) in visited:
continue
visited |= {(x, y)}
for i, j in {(x+1, y), (x-1, y), (x, y+1), (x, y-1)} & valid:
if abs(int(terrain[x][y])-int(terrain[i][j])) <= 1:
heappush(queue, (length+1, i, j))
def climbing_route(terrain):
from itertools import permutations, combinations
height, width = len(terrain), len(terrain[0])
valid = {(x, y) for x in range(height) for y in range(width)}
tops, calc, result = set(find_tops(terrain, valid)), {}, 1e9
for a, b in combinations(tops | {(0, 0), (height-1, width-1)}, 2):
calc[(a, b)] = calc[(b, a)] = calc_shortest(a, b, terrain, valid)
for perm in permutations(tops):
perm = ((0, 0),)+perm+((height-1, width-1),)
result = min(result, sum([calc[(a, b)] for a, b in zip(perm, perm[1:])]))
return result
May 7, 2019
Comments:
