# Find the longest rectilinear path in a matrix with descending entries

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:

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).

• You could think of going the other way round, finding first the local minima and walking back to the top. This way you'd only have to check a few paths. – ChatterOne Apr 13 '17 at 7:45
• I suppose the lowest point might not be at the end of the longest path – kezzos Apr 13 '17 at 8:57
• @kezzos Yes, but at least you'd check only the paths starting from those points instead of generating every path for every point – ChatterOne Apr 13 '17 at 9:15
• @RoyaumeIX OK fair enough, thanks for clarifying, I will restore your edits. – Phrancis Apr 15 '17 at 20:50
• But that is part of the problem. Your edits has invalidated the answers, making their editors stand in a bad light (even though that is not your intentions). My belief, is therefore that it would be better to take the current answers into account, improve your code, and make another post with the better explanations. – holroy Apr 15 '17 at 20:52

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('---')


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:
elif v1 > v0:

# 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.

• This approach is very interesting, this is what I needed! running it on 1000 x 1000 array took me just 45 seconds. – RoyaumeIX Apr 13 '17 at 13:19
• I'd be really curious to see the results if you tried my code on your machine. That's because using the same generation (100 reshaped to 10x10), I get 0.0019... with your code and 0.00036... with my code. I find it hard to believe my code is 10x faster. There must be something I'm missing. – ChatterOne Apr 13 '17 at 14:41
• There's no steepness requirement on individual moves -- only on the whole path, and only as a tie-breaker. You could adapt the code of nx.dag_longest_path accordingly, though. – Janne Karila Apr 13 '17 at 16:30
• Only the steepest edges are kept before applying nx.dag_longest, not sure what you mean sorry. Creating a big graph and then pruning it is not very efficient however hence the slowish speed. Would be Better to loop over the array and construct the graph as you go – kezzos Apr 13 '17 at 17:59
• Ah yes I can see, I misread the question sorry. I'll fix at some point – kezzos Apr 14 '17 at 5:52