5
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.