Finding the maximum path of zeros in a matrix
Given a 10 x N matrix of 1s and 0s such as:
1 1 1 1 1 1 1 1
1 1 0 1 1 0 0 1
0 0 0 1 1 0 0 1
0 0 0 1 1 0 0 0
1 0 0 0 0 1 0 0
1 0 1 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
notes:
-
zeros in column are always between two runs of consecutive 1s. for example a column like
1 1 1 0 1 0 1 1 1 1
is not allowed -
in each column there must be at least a single zero space, i.e. a column such as:
1 1 1 1 1 1 1 1 1 1
not allowed
I want to find the longest sequential strip of zeros from left to right. In this case, it will be 4, which matches the path starting in the second column of the 5th row from the top,
The second longest is 3, and there are 3 examples.
I'm a bit stumped, especially for very large N (~ 10M). I'm looking for suggestions for the correct approach / data structure to use or a similar problem and the algorithm used there. Another potential way to model a problem is to represent the problem using two lists:
L1 = [2, 2, 1, 4, 4, 1, 1, 3]
L2 = [6, 3, 5, 5, 5, 5, 5, 5]
but still not quite sure how to develop an efficient solution
source to share
Solution with itertools.groupby () , sum()
and max()
function:
import itertools
m = [
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 1, 0, 0, 1],
[0, 0, 0, 1, 1, 0, 0, 1],
[0, 0, 0, 1, 1, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0],
[1, 0, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1]
]
max_zero_len = max(sum(1 for z in g if z == 0)
for l in m for k,g in itertools.groupby(l))
print(max_zero_len)
Output:
4
for l in m for k,g in itertools.groupby(l)
- will create a separate group for each sequential sequence of values 1
and 0
for each nested list. (for example [1,1], [0], [1,1], [0,0] ...
)
sum(1 for z in g if z == 0)
- only takes into account sequences 0
and calculates its length using the functionsum
max(...)
- gets the maximum length between null ( 0
) sequences
source to share