Find the longest rectilinear path in a matrix with descending entries

Question

Problem (Skiing):

Each number represents the elevation of that area of the mountain.

From each area (i.e. box) in the grid, you can go north, south, east, west - but only if the elevation of the area you are going into is less than the one you are in (i.e. you can only ski downhill).

You can start anywhere on the map and you are looking for a starting point with the longest possible path down as measured by the number of boxes you visit.

And if there are several paths down of the same length, you want to take the one with the steepest vertical drop, i.e. the largest difference between your starting elevation and your ending elevation.

Goal:

• Find the longest path following these rules. Longest path means the maximum number of nodes where we are always going down.
  • If we have many longest paths with equal distance (number of nodes), then we should get the one with the maximum drop (value of 1st node - value of the last node).

The aim is to run this code for a 1000 x 1000 matrix. As for now, running for just a 4 x 4, it's taking minutes. Any idea on how to reduce the complexity regarding time and space?

myMatrix = [[4, 5, 2],[1, 1, 6],[8, 7, 5]]
def getAllValidSkiingPathsFrom(myMatrix): 
    dctOfMatrix = {}
    for row in range(len(myMatrix)):
        for column in range(len(myMatrix[0])):
            currPoint = (column, row)
            dctOfMatrix[currPoint] = myMatrix[row][column]

    lstIndicesOfAllMatrixPoints = list(dctOfMatrix.keys())
    setAllPossiblePaths = set()

    from itertools import permutations
    for pathCandidate in permutations(lstIndicesOfAllMatrixPoints): 
        lstPossiblePath = []
        prevIndexTuple = pathCandidate[0]
        lstPossiblePath.append(prevIndexTuple)
        for currIndexTuple in pathCandidate[1:]:
            if abs(currIndexTuple[0]-prevIndexTuple[0]) + abs(currIndexTuple[1]-prevIndexTuple[1]) > 1:
                break # current path indices not allowed in path (no diagonals or jumps)
            else:
                if dctOfMatrix[currIndexTuple] >= dctOfMatrix[prevIndexTuple]: 
                    break # only "down" is allowed for "skiing" 
                else:
                    lstPossiblePath.append(currIndexTuple)
                    prevIndexTuple = currIndexTuple
        if len(lstPossiblePath) > 1 and tuple(lstPossiblePath) not in setAllPossiblePaths: 
            setAllPossiblePaths.add(tuple(lstPossiblePath))

    return setAllPossiblePaths, dctOfMatrix

setAllPossiblePaths, dctOfMatrix = getAllValidSkiingPathsFrom(myMatrix)

printedPath = []
bestPath = []
for path in setAllPossiblePaths:
    for point in path:
        printedPath.append(dctOfMatrix[point])
    if len(printedPath) > len(bestPath): # Looking for the path with a maximum distance
        bestPath = printedPath
    if len(printedPath) == len(bestPath): # If we have more than one path with a maximum distance we look for the drop
        if (printedPath[0]-printedPath[-1]) > (bestPath[0]-bestPath[-1]):
            bestPath = printedPath
    printedPath = []

print("Path -->", bestPath)
print("Distance -->", len(bestPath))
print("Drop -->", bestPath[0]-bestPath[-1])

Sample input matrix:

4 5 2
1 1 6
8 7 5

Output:

Path --> [8, 7, 1]
Distance --> 3
Drop --> 7

Explanation:

The longest path would be 8-7-1 as it has the maximum distance = 3.

There are other paths with the same maximum distance which are 8-7-5 and 5-4-1. However, 8-7-1 has the maximum drop = 7 (8-1).

Answer 1

As I said in the comment, it's probably faster to get the local minima and check the paths that start from those points. You can then get the path with the maximum length and reverse the points if you want the descending path.

I haven't tested this a lot, but it takes less than a second on my pc with a 4x4 matrix.

Here's the code (again, I've only tested this with a few inputs and there's a bit of code duplication, take it as a general guideline):

def get_next_ascending_value(row, column, matrix, size):
    current_value = matrix[row][column]
    max_steepness = -1
    coords = []
    if (column > 0) and (matrix[row][column-1] > current_value):
        if max_steepness < matrix[row][column-1]:
            max_steepness = matrix[row][column-1]
            coords = [row, column-1]
    if (row > 0) and (matrix[row-1][column] > current_value):
        if max_steepness < matrix[row-1][column]:
            max_steepness = matrix[row-1][column]
            coords = [row-1, column]
    if (column < size - 1) and (matrix[row][column+1] > current_value):
        if max_steepness < matrix[row][column+1]:
            max_steepness = matrix[row][column+1]
            coords = [row, column+1]
    if (row < size - 1) and (matrix[row+1][column] > current_value):
        if max_steepness < matrix[row+1][column]:
            max_steepness = matrix[row+1][column]
            coords = [row+1, column]

    return coords


def is_local_minimum(row, column, matrix, size):
    current_value = matrix[row][column]
    if (column > 0) and (matrix[row][column-1] < current_value):
        return False
    if (row > 0) and (matrix[row-1][column] < current_value):
        return False
    if (column < size - 1) and (matrix[row][column+1] < current_value):
        return False
    if (row < size - 1) and (matrix[row+1][column] < current_value):
        return False

    return True

def get_local_minimum(matrix, size):
    for row in range(len(matrix)):
        for column in range(size):
            if is_local_minimum(row, column, matrix, size):
                yield [row, column]

# [4, 5, 6]
# [1, 1, 6]
# [4, 5, 6]

# starting_matrix = [[4, 5, 6],[1, 1, 6],[4, 5, 6]]
# size = 3

# [4, 5]
# [1, 1]

# starting_matrix = [[4, 5],[1, 1]]
# size = 2


# [4, 5, 7, 9]
# [1, 1, 2, 5]
# [4, 5, 7, 9]
# [1, 1, 2, 5]

starting_matrix = [[4, 5, 7, 9],[1, 1, 2, 5],[4, 5, 7, 9],[1, 1, 2, 5]]
size = 4

for coords in get_local_minimum(starting_matrix, size):
    print(coords, starting_matrix[coords[0]][coords[1]])
    next_coords = get_next_ascending_value(coords[0], coords[1], starting_matrix, size)
    while (len(next_coords) > 0):
        print(next_coords, starting_matrix[next_coords[0]][next_coords[1]])
        next_coords = get_next_ascending_value(next_coords[0], next_coords[1], starting_matrix, size)
    print('---')

Answer 2

If you don't mind using an external module, I think you can simplify the problem by treating your landscape as a directed graph. If I haven't missed something, you can think of this as solving the longest path problem. However as you said the steepest path must be taken if there is a choice, this involves removing unwanted edges before hand.

np.random.seed(1)
a = np.random.randint(0, 100, 100)
a = a.reshape((10, 10))


def find_path(a):

    # Use a 2d grid graph for convenience to set up the edges
    diG = nx.DiGraph()
    for (n0, n1, data) in nx.grid_2d_graph(*a.shape).edges(data=True):
        v0 = a[n0]
        v1 = a[n1]

        # Add a differential to each edge to calculate the drop
        if v0 > v1:
            diG.add_edge(n0, n1, diff=v0-v1)
            diG.add_node(n0, {"val": v0})
            diG.add_node(n1, {"val": v1})
        elif v1 > v0:
            diG.add_edge(n1, n0, diff=v1-v0)
            diG.add_node(n0, {"val": v0})
            diG.add_node(n1, {"val": v1})

    # Need to remove paths which are not possible, i.e. if there is a steeper slop, this must be chosen

    nodes = sorted(diG.nodes(data=True), key=lambda x: x[1]["val"], reverse=True)
    edges = {(n0, n1): data["diff"] for (n0, n1, data) in diG.edges(data=True)}

    for n, data in nodes:
        neigh = [(n, i) for i in nx.neighbors(diG, n)]
        slopes = [edges[e] for e in neigh]
        [diG.remove_edge(*e) for e, s in zip(neigh, slopes) if s != max(slopes)]

    # Longest drop is the longest path problem
    path = nx.dag_longest_path(diG)

    # Find the drop using a list of allowed edges
    edge_names = set(zip(path, path[1:]))
    drop = sum(edges[e] for e in edge_names)

    return path, drop


t0 = time.time()
path, drop = find_path(a)

print time.time() - t0
print len(path)
print drop

>>> 0.00356292724609
[(5, 6), (5, 7), (4, 7), (3, 7)]
4
76

The path taken is indicated by a dot here:

[[37 12 72  9 75  5 79 64 16  1]
 [76 71  6 25 50 20 18 84 11 28]
 [29 14 50 68 87 87 94 96 86 13]
 [ 9  7 63 61 22 57  1  0. 60 81]
 [ 8 88 13 47 72 30 71  3. 70 21]
 [49 57  3 68 24 43 76. 26. 52 80]
 [41 82 15 64 68 25 98 87  7 26]
 [25 22  9 67 23 27 37 57 83 38]
 [ 8 32 34 10 23 15 87 25 71 92]
 [74 62 46 32 88 23 55 65 77  3]]

Running this for a 1000x1000 array takes 80 seconds on my machine.