You have an elevation map and you want to know the shortest climbing route

checkio-climbing-route.py

# -*- coding: UTF-8 -*-

# https://py.checkio.org/mission/climbing-route/

# https://py.checkio.org/mission/climbing-route/publications/schcriher/python-3/persistence/

# You have an elevation map and you want to know the shortest climbing route.
# 
# The map is given as a list of strings.
#   -  0  : plain (elevation is 0)
#   - 1-9 : hill (number is elevation)
# 
# "mountain" is adjacent (only 4 directions) hill group.
#   - It consists of two or more hills.
#   - Isolated hill is not mountain.
# 
# Start is top-left. Goal is bottom-right. You have to go over all the 
# mountaintops. You can only move vertical and horizontal. And you can only 
# move to the same or one elevation difference. You should look for the shortest 
# route and return Number of steps. (if mountains do not exist, You may go to 
# the goal at the shortest from the start).

from math import inf
from itertools import permutations

def get_neighbors(fun, nrow, ncol, r, c):
    for dr, dc in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        rr = r + dr
        cc = c + dc
        if 0 <= rr < nrow and 0 <= cc < ncol:
            if fun(r, c, rr, cc):
                yield (rr, cc)

def get_mountains(emap, nrow, ncol):
    hills = [(r, c) for r in range(nrow) for c in range(ncol) if emap[r][c] > 0]
    is_hill = lambda r, c, rr, cc: emap[rr][cc] > 0
    while hills:
        adjacent = []
        to_visit = [hills[0]]
        while to_visit:
            rc = to_visit.pop()
            if rc in hills:
                hills.remove(rc)
                r, c = rc
                adjacent.append((emap[r][c], rc))
                for pos in get_neighbors(is_hill, nrow, ncol, r, c):
                    if pos in hills:
                        to_visit.append(pos)
        adjacent.sort()
        if len(adjacent) > 1 and adjacent[-2][0] != adjacent[-1][0]:
            yield adjacent[-1][1]

def reconstruct_path(path, current):
    route = [current]
    while current in path:
        current = path[current]
        route.append(current)
    return route

class SearchPathCache:

    def __init__(self, fun):
        self.fun = fun
        self.cache = {}

    def __call__(self, emap, nrow, ncol, start, end):
        key = (start, end)
        if key not in self.cache:
            self.cache[key] = self.fun(emap, nrow, ncol, start, end)
        return self.cache[key]

@SearchPathCache
def search_path(emap, nrow, ncol, start, end):
    # Pseudo A* algorithm
    passable = lambda r, c, rr, cc: abs(emap[r][c] - emap[rr][cc]) < 2

    opened = [start]    # nodes discovered but not evaluated
    closed = []         # nodes already evaluated
    cost = {start: 0}   # cost of getting from the start node to that node
    path = {}           # travelling of nodes

    while opened:
        min_cost = sorted((cost[i], i) for i in opened if i in cost)
        if min_cost:
            current = min_cost[0][1]
        else:
            current = opened[0]

        opened.remove(current)
        closed.append(current)

        if current == end:
            return reconstruct_path(path, current)

        for neighbor in get_neighbors(passable, nrow, ncol, *current):

            if neighbor in closed:
                continue

            if neighbor not in opened:
                opened.append(neighbor)

            tentative = cost[current] + 1
            if neighbor in cost and tentative >= cost[neighbor]:
                continue

            path[neighbor] = current
            cost[neighbor] = tentative

def climbing_route(elevation_map):
    emap = tuple(tuple(map(int, row)) for row in elevation_map)
    nrow = len(emap)
    ncol = len(emap[0])
    start = (0, 0)
    end = (nrow - 1, ncol - 1)
    mountains = list(get_mountains(emap, nrow, ncol))
    search_path.cache.clear()
    min_steps = inf
    for objectives in permutations(mountains, len(mountains)):
        steps = 0
        a = start
        for b in (*objectives, end):
            path = search_path(emap, nrow, ncol, a, b)            
            if path:
                steps += (len(path) - 1)
                if steps >= min_steps:
                    steps = 0
                    break
                a = b
            else:
                steps = 0
                break
        if steps and steps < min_steps:
            min_steps = steps
    return min_steps

if __name__ == '__main__':
    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'
    assert climbing_route([
        '0000000000000',
        '0232021202320',
        '0222022202220',
        '0212023202120',
        '0000000000000',
        '0232021202320',
        '0222022202220',
        '0212023202120',
        '0000000000000',
        '0232021202320',
        '0222022202220',
        '0212023202120',
        '0000000000000']) == 110, 'extra test 1'
    assert climbing_route([
        '01220000122332332',
        '12343000023443211',
        '11232100000232100',
        '11110000001223121',
        '11011002223333443',
        '21002023334454564',
        '10000234556678752',
        '10000046778898531',
        '10000004555677642',
        '11000000001234532',
        '22112211000123421',
        '11234432210002321',
        '22345443321012210',
        '33456554332111210']) == 37, 'extra test 2'