Как проверить определенные значения по диагонали в 2D-списке, если высота и ширина могут варьироваться

Question

Я писал такую ​​программу, как крестики-нолики.

Explaination

Я хотел создать функцию, которая бы принимала входные данные в виде двумерного списка длиной n x m , где n может равняться или не равняться m.

Он должен проверить, есть ли в списке 2D 4 или более последовательных X или 4 последовательных O .

Он должен возвращать «X», если в списке есть четыре смежных значения «X» ( строка, столбец, диагональ ). Он должен возвращать «O», если есть четыре соседних «O» значения в любом месте списка (строка, столбец, диагональ). Он должен возвращать None, если ни 'X', ни 'O' не удовлетворяют вышеуказанному условию. Вы можете предположить, что может быть только один ответ.

Если я дам следующий , введите :

xwins = [[None, None, None, None, None, None, None],
         [None, None, None, None, None, None, None],
         [None, None, None, None, "X" , None, None],
         [None, None, None, "X" , "O" , "O", None],
         [None, "O" , "X" , "X" , "O" , "X", None],
         ["O" , "X" , "O" , "O" , "O" , "X" , "X"]]

owins = [[None, None, None, None, None, None, None],
         [None, None, None, None, None, None, None],
         ["O" , "O" , "O" , "O" , None, None, None],
         ["O" , "X" , "X" , "X" , None, None, None],
         ["X" , "X" , "X" , "O" , "X" , None, None],
         ["X" , "O" , "O" , "X" , "O" , None, None]]

nowins =[["X" , "X" , None, None, None, None, None],
         ["O" , "O" , None, None, None, None, None],
         ["O" , "X" , "O" , "O" , None, "O" , "O" ],
         ["O" , "X" , "X" , "X" , None, "X" , "X" ],
         ["X" , "X" , "X" , "O" , "X" , "X" , "O" ],
         ["X" , "O" , "O" , "X" , "O" , "X" , "O" ]]

print(myfunc(xwins))
print(myfunc(owins))
print(myfunc(nowins))

Это должно дать результат :

X
O
None

Мой Прогресс :

Я нашел способ проверить каждую строку, используя код:

def myfunc(lol):
    for i in lol:#lol is list of list :)
        string="".join(i)
        if ("XXXX" in string):
             return "X"
        elif ("OOOO" in string):
             return "O"

Я пытаюсь обойтись без NumPy.

Помощь будет оценена. Извините, если я оставил что-то неясным. Пожалуйста, спросите меня в комментариях. :)

Answer 1

Самый простой алгоритм - просто проверять каждое направление, перебирая его.

Вы спрашивали о диагонали специально.Мы должны индексировать, один в направлении x (внутренний список), один в направлении y (список out), давайте назовем их ii и jj.

Самая простая диагональ этов середине.Вы находитесь на этой диагонали, когда ii == jj.Как насчет диагоналей, параллельных этому?ii + 1 == jj и ii - 1 == jj.

Для данной диагонали ii + a == jj будет истинным для целого числа, определяющего, какую из диагоналей вы определяете.

Тогда аналогичный аргумент применяется для диагоналей, начинающихся с другой стороны ii + a = n - jj

Answer 2

Не уверен, что это самое элегантное решение, но я использовал Numpy примерно так:

Сначала включите матрицу в numpy.array

lol = np.array(lol)

Получите размеры

rows, cols = lol.shape

Проверяйте строки и столбцы, просматривая их следующим образом:

for i in range(rows):
    if "'X' 'X' 'X' 'X'" in np.array_str(lol[:, i]):
        return 'X'
    ...and so on

Вы можете перебирать диагонали с помощью функции np.diagonal:

for i in range(rows):
    if "'X' 'X' 'X' 'X'" in np.array_str(np.diagonal(lol, offset=i)):
        return 'X'
    ...and so on

Выможно получить диагонали в другом направлении, например, offset=-i.Затем вы можете сделать то же самое для транспонирования, которое вы получаете с np.fliplr(lol).Вы также можете определить предел смещения, так как вам не нужно оценивать диагонали короче 4.

Answer 3

Вы можете использовать что-то подобное для решения в столбцах:

vert = ["" for i in range(len(lol[0]))]
for i in range(len(lol)):
    for j in range(len(lol[i])):
        vert[j] += str(lol[i][j])
for column in vert:
    if ("XXXX" in column):
        print("X")
    elif ("OOOO" in column):
        print("O")

Создает с элементами из столбцов и проверяет наличие необходимого шаблона.