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.