CODEWITHSUNDEEP
pythonrecursionmatrixlongest-path
Ramesh R
Ramesh R

Reputation: 13

Maximum number of elements in the path of a matrix

I tried to solve a problem of map (matrix 4x4) using python.

I want to find Maximum number of elements in the path of a map provided the next node must be lesser than the previous node with all possible combinations of elements in the matrix.

4 8 7 3  
2 5 9 3  
6 3 2 5  
4 4 1 6

The movement is like from an element can move to east-west-north-south

For example from m[0][1] can move to m[0][2] and m[1][1] 4-> 8 or 2

Here is the sample code but i have no idea to how to recursively check every element.

#import itertools
n = 4 
matrix = [[4, 8, 7, 3 ], [2, 5, 9, 3 ], [6, 3, 2, 5 ], [4, 4, 1, 6]]
for index,ele in enumerate(matrix):
    vals=[]
    for i2,e2 in enumerate(ele):
        for index2,ele2 in enumerate(ele):
            if index < (n-1):
                if ele2 > matrix[index+1] [index2]:
                    vals.append(matrix[index+1] [index2])
            if index > 0:
                if ele2 > matrix[index-1] [index2]:
                    vals.append(matrix[index-1] [index2])
            if index2 < n-1:
                if ele2 > matrix[index] [index2+1]:
                    vals.append(matrix[index] [index2+1])
            if index2 >0:
                if ele2 > matrix[index] [index2-1]:
                    vals.append(matrix[index] [index2-1])

how to recurse this function to loop till the end

For Example the answer will be like 8-5-3-2-1 (Longest Path with decreasing factor)

Upvotes: 1

Views: 541

Answers (1)

tobias_k
tobias_k

Reputation: 82889

Try this recursion: The longest path starting at element (x, y) is the longest longest path starting at any of its strictly smaller neighbors, plus 1.

def longest_path(matrix):
    def inner_longest_path(x, y):
        best, best_path = 0, []
        # for all possible neighbor cells...
        for dx, dy in ((+1, 0), (-1, 0), (0, +1), (0, -1)):
            # if cell is valid and strictly smaller...
            if (0 <= x + dx < len(matrix) and 0 <= y + dy < len(matrix[x]) 
                    and matrix[x+dx][y+dy] < matrix[x][y]):
                n, path = inner_longest_path(x+dx, y+dy)
                # check if the path starting at that cell is better
                if n > best:
                    best, best_path = n, path
        return best + 1, [matrix[x][y]] + best_path

    return max(inner_longest_path(x, y) for x, row in enumerate(matrix) 
                                        for y, _ in enumerate(row))

Note that this will do a lot of duplicate calculations. Adding memoization is left as an excercise to the reader.

Example:

>>> longest_path(matrix)
(5, [9, 5, 3, 2, 1])

Upvotes: 1

Related Questions