How to find a 2x2 object in a 2D list?

Question

I have an exercise that I have to complete for school and I'm kinda stuck. I have to program a function that tells you if there's a face on the photo, by photo we can imagine a 2D list, so a list that consists of more lists to create a 2 dimensional object. The face is represented by 2x2 square with the word face in it these letters can be in a random order. As shown below in picture I. and II.:

Also there can be more faces, as long as the word face is shown at least once in the whole 2Dlist it should return True.

The problem is that the letters can't be in a row or in a column as shown in picture III.. I really can't figure out how to make a condition that would eliminate this. So far I know how to find out out if all of the letters are in that 2Dlist and I eliminated the possibility of having just a single row or a single column as shown in the picture IV. and V..

Here's what I have so far:

def is_face_on_photo(photo):
    list2D = photo
    faces = ['f','a','c','e']
    newlist = []
    for list in list2D:
        for letter in list:
            newlist.append(letter)
    if 'f' in newlist and 'a' in newlist and 'c' in newlist and 'e' in newlist and (faces not in list2D) and (len(list2D) >= 2) and (len(list2D[0]) >= 2):
        print True
    else:
        print False
 pass

I'm new to python so I would appreciate any help I can get :) thanks a lot

Answer 1

Search element by element through each row, then the next row, and so on, left to right, and down, until you find an F, A, C, or E.

When you do, since you're checking left to right and top to bottom, you can assume you've found the top left corner of a potential "FACE". So check if the letter to the right, the one below, and the one to the lower right satisfy the rest of the FACE.

If so, you're done. If not, keep going.

Edit: Here's a somewhat wordy version. I haven't tested it, but it's the idea.

def is_face_on_photo(photo):
    found = False

    for row,photo_row in enumerate(photo):
        for col,letter in enumerate(photo_row):

            if (letter in "face") and col + 1 < len(photo_row) and row + 1 < len(photo):
                found = True  # Until proven otherwise

                num_found = {"f":0, "a":0, "c":0, "e":0}

                right_letter = photo_row[col + 1]
                below_letter = photo[row + 1][col]
                below_right_letter = photo[row + 1][col + 1]

                letters = [letter, right_letter, below_letter, below_right_letter]

                # Could replace with something like defaultdict
                for let in letters:
                    if let in num_found:
                        num_found[let] += 1

                # Would need to change this slightly if the letters of "face" had 
                # any repetitions, like two "a"s or something
                for let in "face":
                    if num_found[let] == 0:
                        found = False
                        break

            if found:
                break

        if found:
            break

    return found