Given a 2D array of digits, try to find the occurrence of a given 2D pattern of digits

Question

My algorithm is quite simple. I simply iterate over the entire map arr and if I find the start of the combination I need to find, I begin exploring.

My combination data structure is simply the combination I need to find, column at a time.

If each column in arr matches, I return True. If at any point the value doesn't match the combination I need I return False.

I believe this is O(n+m) time with O(1) space. Code below...

def explore(arr, combination, i, j):
    """
    for each column in the combination we have to find
    compare it with what is present in the map (arr)
    """
    for row in combination:
        for count, item in enumerate(row):

            # compare the map with the combination value we're up to
            # if it doesn;t match, return False and stop
            if arr[i+count][j] != item:
                return False
        j+=1
    return True

def find_combination_in_arr(arr, combination, ):
    for i, row in enumerate(arr):
        for j, item in enumerate(row):

            # if we have found the start of the combination, then start exploring
            if item == combination[0][0]:
                if explore(arr, combination, i, j):
                    return "FOUND IT!"

# the map we need to search
arr = [
    [1, 1, 2, 3, 4, 1, 1],
    [1, 1, 5, 6, 7, 1, 1],
    [1, 1, 2, 7, 4, 1, 1],
    [1, 1, 7, 8, 6, 1, 1]
]

# the combination we need to find
combination = [
    [2, 5, 2, 7],
    [3, 6, 7, 8],
    [4, 7, 4, 6]
]

find_combination_in_arr(arr, combination)

Answer 1

Duplication

Your nested loops are almost equal, write a generator that contains the loops and use it twice.

Power

enumerate has more power then you think: you can specify a starting index, so you do not need manual increment.

all

You want all items to be equal, so use all.

Minimalism

Return a boolean not a string, a string is an unecessary complication.