Search code examples
pythonalgorithmmatrixpath-finding

"Matrix" of unequal width - efficient way to loop over

Trying to implement path finding algorithm which looks for adjacent True values in the matrix and concatenates them into a single path. And looks for all independent paths in the matrix. Elements are only 1s or 0s

Example:

matrix = [
    [1, 0, 1, 0],
    [1, 1, 0, 0],
    [1, 0, 1, 1]
]

1st path: [(0,0), (1,0), (1,1), (2,0)]

2nd path: [(0,2)]

3rd path: [(2,2), (2,3)]

Now, this is pretty straight forward, but I am wondering how to efficiently loop over matrices which have unequal width.

Example:

matrix = [
    [1, 0, 1, 0],
    [1, 1, 0, 0],
    [1, 0, 1, 1],
    [1, 0, 0],
    [0, 1]
    [1, 0, 1, 0, 1, 1]
]

I was thinking of two ways:

  1. Check the number of element in a row and skip it if end is reached. Using if and cols[row] where cols represent the number of elements in each column and row is the current row: cols = [len(row) for row in matrix]
  1. Populate "the missing" elements with 0s to get row * column matrix

Although these approaches may work fine with relatively small matrices, the problems will occur with large numbers, e.g.

If any of the rows has 50k elements and all others about 1k, so n rows need to be populated 49k times (second method). Using the first one, in worst case (0s and 1s appearing alternatively) the checking will occur 49k/2 times (since each 1 is a new path and the algorithm will look for adjacent ones).

I was wondering if there is more efficient way, to check as few "blank spots" as possible or not to check them at all.

Solution

  • In the general case, you can just iterate over rows and columns like this without explicitly mentioning the column width.

    for row in matrix:
    for value in row:
        ...

    For this particular problem you are trying to solve, it might still be necessary to record the length of the previous row:

    last_row = None
last_row_len = 0
for row in matrix:
    for idx, value in enumerate(row):
        if idx >= last_row_len:
            ...
        elif value and last_row[idx]:
            ...
    last_row = row
    last_row_len = len(row)

    A more efficient solution in Python can use itertools.groupby to group 0s and 1s into chunks on each row. You may try to figure out an implementation yourself.