Ever heard about Dijkstra's shallowest path algorithm? Me neither. But I can imagine what it would be.

You're hiking in the wilderness of Northern Canada and you must cross a large river. You have a map of one of the safer places to cross the river showing the depths of the water on a rectangular grid. When crossing the river you can only move from a cell to one of the (up to 8) neighboring cells. You can start anywhere along the left river bank, but you have to stay on the map.

An example of the depths provided on the map is 

```
[[2, 3, 2],
 [1, 1, 4],
 [9, 5, 2],
 [1, 4, 4],
 [1, 5, 4],
 [2, 1, 4],
 [5, 1, 2],
 [5, 5, 5],
 [8, 1, 9]]
```
If you study these numbers, you'll see that there is a path accross the river (from left to right) where the depth never exceeds 2. This path can be described by the list of pairs `[(1, 0), (1, 1), (2, 2)]`. There are also other paths of equal maximum depth, e.g., `[(1, 0), (1, 1), (0, 2)]`. The pairs denote the cells on the path where the first element in each pair is the row and the second element is the column of a cell on the path.

Your job is to write a function `shallowest_path(river)` that takes a list of lists of positive ints (or array of arrays, depending on language) showing the depths of the river as shown in the example above and returns a shallowest path (i.e., the maximum depth is minimal) as a list of coordinate pairs (represented as tuples, Pairs, or arrays, depending on language) as described above. If there are several paths that are equally shallow, the function shall return a shortest such path. All depths are given as positive integers.

Difficulty: interview

Starter code:

def shallowest_path(river):
	

Solutions:
from heapq import *

MOVES = tuple( (dx,dy) for dx in range(-1,2) for dy in range(-1,2) if dx or dy)


def shallowest_path(river):

    lX,lY   = len(river), len(river[0])
    pathDct = {}
    cost    = [ [(float('inf'),float('inf'))]*lY for _ in range(lX) ]
    for x in range(lX): cost[x][0] = (river[x][0],1)
    
    q = [ (river[x][0], lY==1, 1, (x,0)) for x in range(lX)]
    heapify(q)
    
    while not q[0][1]:
        c,_,steps,pos = heappop(q)
        x,y = pos
        for dx,dy in MOVES:
            a,b = new = x+dx,y+dy
            if 0<=a<lX and 0<=b<lY: 
                check = nC,nS = max(c, river[a][b]), steps+1
                if cost[a][b] > check:
                    cost[a][b] = check
                    pathDct[new] = pos
                    heappush(q, (nC, b==lY-1, nS, new))
    
    path, pos = [], q[0][-1]
    while pos:
        path.append(pos)
        pos = pathDct.get(pos)
    return path[::-1]

from heapq import *
from collections import defaultdict

MOVES = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))

def shallowest_path(river):
    q = [(river[x][0], 0, (x,0)) for x in range(len(river))]
    path = {}
    stored_steps = defaultdict(lambda : float('inf'))
    heapify(q)

    while q:
        cost, step, (x,y) = heappop(q)
        if (x,y) == (x,len(river[0])-1):
            end = (x,y)
            break

        for dx,dy in MOVES:
            xx = dx + x
            yy = dy + y

            if 0<=xx<len(river) and 0<=yy<len(river[0]):
                new_step = step + 1

                if new_step < stored_steps[(xx,yy)]:
                    stored_steps[(xx,yy)] = new_step
                    new_cost = max(cost, river[xx][yy])

                    path[(xx,yy)] = (x,y)
                    heappush(q, (new_cost, new_step, (xx,yy)))
        
    
    coords = [end]

    while coords[-1][1] != 0:
        coords.append(path[end])
        end = path[end]

    return coords[::-1]

def shallowest_path(river):    
    depth = {(r, c):d for r, row in enumerate(river) for c, d in enumerate(row)}    
    width = max(c for _, c in depth)

    for mx in sorted(set(depth.values())):
        D = {d for d in depth if depth[d] <= mx}
        paths, D = [[d] for d in D if d[1] == 0], {d for d in D if d[1]}
        
        while paths:
            newp = []        
            for p in paths:
                if p[-1][1] == width: return p
                for d in {(p[-1][0]+rr, p[-1][1]+cc) for rr in [-1, 0, 1] for cc in [-1, 0, 1]} & D:
                    newp, _ = newp + [p + [d]], D.discard(d)
            paths = newp

def shallowest_path(river):
    mx,my,crit=len(river[0]),len(river),lambda e:e[0]+len(e[1])
    M=[[(r[0]*mx*my,[(i,0)])]+[(99999*mx*my,[])]*(mx-1) for i,r in enumerate(river)]
    Q=set(((j,1),(i,0)) for i in range(my) for j in [i-1,i,i+1] if 0<=j<my and mx>1)
    while(Q):
      Q,R=set(),Q
      for (u,v),(i,j) in R:
          if crit(M[u][v])>max(M[i][j][0],river[u][v]*mx*my)+len(M[i][j][1])+1:
              M[u][v]=(max(M[i][j][0],river[u][v]*mx*my),M[i][j][1]+[(u,v)])
              Q.update(((a,b),(u,v)) for a in [u-1,u,u+1] for b in [v,v-1,v+1][a==u:] if 0<b<mx and 0<=a<my)
    return(min(M,key=lambda e:crit(e[-1]))[-1][1])

from collections import namedtuple
import heapq

def shallowest_path(river):
    rows = len(river)
    if rows == 0:
        return []
    cols = len(river[0])
    if cols == 0:
        return []

    Solution = namedtuple('Solution', ['depth', 'path'])
    State = namedtuple('State', ['depth', 'path_length', 'path'])

    best_solution = None
    left_bank_q = [(river[row][0], row, 0) for row in range(rows)]
    heapq.heapify(left_bank_q)

    while left_bank_q:
        visited = set()
        initial_depth, row, col = heapq.heappop(left_bank_q)
        walk_q = [State(depth=initial_depth, path_length=1, path=[(row, col)])]
        while walk_q:
            depth, path_length, path = heapq.heappop(walk_q)
            current_row, current_col = path[-1]
            if (current_row, current_col) in visited or (current_col == 0 and path_length > 1):
                continue
            if current_col == cols - 1: # We reached the right bank
                if depth == 1 and len(path) == cols:
                    return path # Optimal path
                if best_solution is None or depth < best_solution.depth or (depth == best_solution.depth and len(path) < len(best_solution.path)):
                    best_solution = Solution(depth, path)
                continue
            visited.add((current_row, current_col))
            best_depth = float('inf') if best_solution is None else best_solution.depth
            for row, col in neighbours(river, current_row, current_col):
                if (row, col) not in visited and river[row][col] <= best_depth:
                    heapq.heappush(walk_q, State(depth=max(depth, river[row][col]), path_length=path_length+1, path=path+[(row, col)]))

    return best_solution.path

def neighbours(river, row, col):
    rows = len(river)
    cols = len(river[0])

    return ((row + drow, col + dcol)
            for drow in [-1, 0, 1]
            for dcol in [-1, 0, 1]
            if drow != 0 or dcol != 0
            if 0 <= row+drow < rows
            if 0 <= col+dcol < cols)


from itertools   import product
from collections import defaultdict
from heapq       import *

def dijkstra(edges, f, t):
    g = defaultdict(list)
    for l,r,c in edges:
        g[l].append((c,r))

    q, seen, mins = [(0,f,())], set(), {f: 0}
    while q:
        (cost,v1,path) = heappop(q)
        if v1 not in seen:
            seen.add(v1)
            path = (v1, path)
            if v1 == t: return (cost, path)

            for c, v2 in g.get(v1, ()):
                if v2 in seen: continue
                prev = mins.get(v2, None)
                next = cost + c
                if prev is None or next < prev:
                    mins[v2] = next
                    heappush(q, (next, v2, path))

    return float("inf"),()

def shallowest_path(river):
    d={(y,x):v for y,line in enumerate(river) for x,v in enumerate(line)}
    width=len(river[0])
    height=len(river)
    depthmin=max([min(d[y,x] for y in range(height)) for x in range(width)])
    depths=sorted(set([v for v in list(d.values()) if v>=depthmin]))
    start=(0,-1)
    end  =(0,width)
    for depth in depths:
        edges =[(start,(y,0),0)      for y in range(height) if d[y,0]      <=depth]
        edges+=[((y,width-1), end,0) for y in range(height) if d[y,width-1]<=depth]
        for k in product(list(range(height)),list(range(width))):
            if not k in d or d[k]>depth:continue
            y,x=k
            for k1 in [(y-1,x-1),(y-1,x),(y-1,x+1),(y,x-1),(y,x+1),(y+1,x-1),(y+1,x),(y+1,x+1)]:
                if not k1 in d or d[k1]>depth:continue
                edges.append((k,k1,1))
        dist,res0=dijkstra(edges, start, end)
        if dist==float("inf"): continue
        res=[]
        while res0:
            p,res0=res0
            res.insert(0,p)      
        return res[1:-1]
    return []


from heapq import *
from collections import defaultdict

MOVES = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))

def shallowest_path(river):
    q = [(river[x][0], 0, (x,0)) for x in range(len(river))]
    path = {}
    stored_steps = defaultdict(lambda : float('inf'))
    heapify(q)

    while q:
        cost, step, (x,y) = heappop(q)
        if (x,y) == (x,len(river[0])-1):
            end = (x,y)
            break

        for dx,dy in MOVES:
            xx = dx + x
            yy = dy + y

            if 0<=xx<len(river) and 0<=yy<len(river[0]):
                new_step = step + (abs(dx)+abs(dy))**.5

                if new_step < stored_steps[(xx,yy)]:
                    stored_steps[(xx,yy)] = new_step
                    new_cost = max(cost, river[xx][yy])

                    path[(xx,yy)] = (x,y)
                    heappush(q, (new_cost, new_step, (xx,yy)))
        
    
    coords = [end]

    while coords[-1][1] != 0:
        coords.append(path[end])
        end = path[end]

    return coords[::-1]

from heapq import heappush, heappop


def shallowest_path(river):
    ls_o_res, hippo, dc = {}, [], {(i, 0): {} for i in range(len(river))}
    if len(river[0]) > 1:
        for i in range(len(river)):
            dc[(i, 0)][(i, 0)] = ((river[i][0], len([river[i][0]])),
                                  (i, 0), [(i, 0)], [river[i][0]])
            heappush(
                hippo, (((river[i][0], len([river[i][0]])), (i, 0), [(i, 0)], [river[i][0]])))
    else:
        for i in range(len(river)):
            ls_o_res[river[i][0]] = [(i, 0)]
        return ls_o_res[min(ls_o_res.keys())]
    yb, xb = len(river), len(river[0])
    mito = (float("inf"), float("inf"))
    while hippo:
        vara = heappop(hippo)
        moves, parent = [(1, 0), (-1, 0), (0, 1),
                         (1, 1), (-1, 1), (-1, -1), (1, -1), (0, -1)], vara[1]
        for y, x in moves:
            i, j = parent
            i, j = i+y, j+x
            if 0 <= i < yb and 0 <= j < xb:
                path = vara[2] + [(i, j)]
                pathowar = vara[3]+[river[i][j]]
                dist = (max(pathowar), len(pathowar))
                if (i, j) not in dc[(i, 0)]:
                    dc[(i, 0)][(i, j)] = (dist, (i, j), path, pathowar)
                    heappush(hippo, (dist, (i, j), path, pathowar))
                elif (i, j) in dc[(i, 0)] and dist < dc[(i, 0)][(i,j)][0]:
                    dc[(i, 0)][(i, j)] = (dist, (i, j), path, pathowar)
                    heappush(hippo, (dist, (i, j), path, pathowar))
                if j == xb-1:
                    print(dist)
                    if dist < mito:
                        mito = dist
                        ls_o_res[mito] = path
    return ls_o_res[min(ls_o_res.keys())]



import math
def shallowest_path(river):
    maxsize = 999999999
    steps = [
        (-1,-1),(-1, 0),(-1, 1),
        ( 0,-1),        ( 0, 1),
        ( 1,-1),( 1, 0),( 1, 1)
    ]
    h, w = len(river), len(river[0])
    res = [[]] * h
    for r in range(h):
        res[r] = [(maxsize, [(r,0)])] * w                        
    
    points = []
    for r in range(h):
        res[r][0] = (river[r][0], [(r,0)])
        points.append((r, 0))
    
    while len(points) > 0:
        p = points.pop(0)
        r, c = p[0], p[1]
        deep = res[r][c][0]
        path = res[r][c][1]
        length = len(path)
        if c < w - 1: 
            for s in steps:
                nr = r + s[0]
                nc = c + s[1]                
                if nr >= 0 and nr < h and nc >= 0 and nc < w and (nr,nc) not in path:
                    tdeep = res[nr][nc][0]
                    tpath = res[nr][nc][1]
                    tlength = len(tpath)
                    ndeep = max(deep, river[nr][nc])
                    if tdeep > ndeep or (tdeep == ndeep and tlength > length + 1):
                        npath = path.copy()
                        npath.append((nr, nc))
                        res[nr][nc] = (ndeep, npath)
                        if (nr, nc) not in points:
                            points.append((nr, nc))
                        
    min_deep, min_path = maxsize, []
    for r in range(h):
        p = res[r][-1]
        if p[0] < min_deep:
            min_deep,  min_path = p[0], p[1]
        elif p[0] == min_deep and len(p[1]) < len(min_path):
            min_deep, min_path = p[0], p[1]
    return min_path

import heapq

def get_path(river):
    big_num = 10992312321
    nodes = []
    b = {}
    for y in range(len(river)):
        heapq.heappush(nodes, [river[y][0] * big_num, (y, 0)])
    while nodes[0][1][1] != len(river[0])-1:
        weight, node = heappop(nodes)
        ly, lx = node
        for dy, dx in [(0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1)]:
            if 0 <= ly+dy < len(river) and 0 <= lx+dx < len(river[0]) and (ly+dy, lx+dx) not in b:
                b[(ly+dy, lx+dx)] = (ly, lx)
                new_weight = max([weight // big_num, river[ly+dy][lx+dx]]) * big_num + weight % big_num + 1
                heapq.heappush(nodes, [new_weight, (ly+dy, lx+dx)])
    path = [nodes[0][1]]
    while path[-1][1] != 0:
        path.append(b[path[-1]])
    return nodes[0][0] // big_num, path

def shallowest_path(river):
    cost, path = get_path(river)
    for y in range(len(river)):
        for x in range(len(river[0])):
            if river[y][x] < cost:
                river[y][x] = 0
    cost, path = get_path(river)
    return path[::-1]