17.5.1 Search for a sequence in 2D array, variant 1

#1

First variant states to implement searching for a sequence by visiting entries in 2D array at most once. Any hints on that? Sounds to me like save “some sort” of information in other 2D arrays and somehow use that in determining if sequence can be matched.

Thanks

0 Likes
#2

I have also found this post that explains the same problem but in different way I have understood:
https://stackoverflow.com/questions/39584214/search-for-a-sequence-in-a-2d-array-visit-each-entry-only-once

If its is really the solution than this question has to be fixed. My understanding was that I cannot visit each element more than once so after I read entry it i cannot read it again.
But if the goal is to solve it like in the link it is far more easier that I understood.
I suggest the question has to be rewritten in more clear manner, like:

“Solve the same problem when function isPatternSufficContainedStartingAtXY at each call do not read the same entry form A more than once.”

0 Likes
#3

If visit is to be interpreted as “not visiting the cell in a given sequence”, this is, the cell can be visited multiple times during the algorithm, then the best solution I can conjure has exponential time complexity I believe.

The gist of it to keep track of the visited cells along a given path:

Code, in Python 
from typing import Set, Tuple

def is_pattern_contained_in_grid(grid, S):
    def traverse(x, y, s_idx, visited: Set[Tuple[int,int]]):
        if (s_idx == len(S)):
            return True
        
        if ((x, y) in visited
            or not( x >= 0 and y >= 0 and x < n and y < m)
            or grid[x][y] != S[s_idx]):
            return False
        
        for adj_x, adj_y in ((x + 1, y),
                        (x - 1, y),
                        (x, y + 1),
                        (x, y - 1)):
            if (traverse(adj_x, adj_y, s_idx + 1, visited.union({(x,y)}))):
                return True
            
        return False
    
    
    if (not S):
        return True
    
    n = len(grid)
    m = len(grid[0])
    for i in range(n*m):
        x = i % n
        y = i // n
        if (traverse(x, y, 0, set())):
            return True
    
    return False

# Some examples
print(is_pattern_contained_in_grid([[0,0,0,0],[0,1,3,1],[0,3,4,0],[1,5,6,7]], [1,5,3,1,3,1]))
print(is_pattern_contained_in_grid([[0,0,0,0],[0,1,3,7],[0,3,4,0],[1,5,6,7]], [1,5,3,1,3,1]))
print(is_pattern_contained_in_grid([[0,0,0,0],[0,1,3,1],[0,3,4,0],[1,5,6,7]], [1,5,3,5,6]))
0 Likes