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

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)


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.