Как создать цикл for, который проходит через все диагональные возможности списка?

Question

Контекст

Как бы вы нашли слова в этом списке по диагонали? Примечание. Чтобы показать, что слово найдено, его можно заменить любым символом, например '-'

grid =   ["HXXWXXXXXD",
          "XOXXOXXXOX",
          "XXRXXCXGXX",
          "XXXSXXXXXT",
          "XXXXEXXXEX"]

Я понял, что все возможности диагоналей в сетке:

• Спускаясь вниз и влево
• Идти вниз и вправо
• Идя вверх и влево
• Идти вверх и вправо

Слова, которые нужно найти, в этом случае будут:

words = ["HORSE","COW","DOG","ET"] # don't ask

Как я нашел слова по вертикали и по горизонтали

Поиск слов по диагонали кажется гораздо сложнее, чем по горизонтали или по вертикали. Когда я нахожу слова по горизонтали, я могу просто просмотреть все row в grid и каждый word в words. Затем я мог бы заменить word в row на символ * len(word), чтобы проиллюстрировать, что он был найден. По вертикали я повернул сетку на 90 ° по часовой стрелке, а затем проделал тот же процесс циклического перемещения по спискам по горизонтали. Затем я повернул список обратно в исходное состояние.

Какие существуют варианты поиска слов по диагонали?

Answer 1

Чтобы перебрать все возможные диагонали, вы можете использовать numpy diagonal .Также используйте numpy fliplr, flipud, flip, чтобы получить диагонали во всех направлениях:

import numpy as np

grid = [
    "HXXWXXXXXD",
    "XOXXOXXXOX",
    "XXRXXCXGXX",
    "XXXSXXXXXT",
    "XXXXEXXXEX"]
data_orig = np.array(list(map(list, grid)))

transformations = {
    'Downwards and Right': np.array,
    'Downwards and left': np.fliplr,
    'Upwards and Right': np.flipud,
    'Upwards and left': np.flip,
}

for descr, trans in transformations.items():
    data = trans(data_orig)
    print(descr)
    print(data)
    offset_row = 1 - data.shape[0]
    offset_column = data.shape[1]
    for offset in range(offset_row, offset_column):
        print(data.diagonal(offset=offset))

Ouput:

Downwards and Right
[['H' 'X' 'X' 'W' 'X' 'X' 'X' 'X' 'X' 'D']
 ['X' 'O' 'X' 'X' 'O' 'X' 'X' 'X' 'O' 'X']
 ['X' 'X' 'R' 'X' 'X' 'C' 'X' 'G' 'X' 'X']
 ['X' 'X' 'X' 'S' 'X' 'X' 'X' 'X' 'X' 'T']
 ['X' 'X' 'X' 'X' 'E' 'X' 'X' 'X' 'E' 'X']]
['X']
['X' 'X']
['X' 'X' 'X']
['X' 'X' 'X' 'X']
['H' 'O' 'R' 'S' 'E']
['X' 'X' 'X' 'X' 'X']
['X' 'X' 'X' 'X' 'X']
['W' 'O' 'C' 'X' 'X']
['X' 'X' 'X' 'X' 'E']
['X' 'X' 'G' 'X' 'X']
['X' 'X' 'X' 'T']
['X' 'O' 'X']
['X' 'X']
['D']
Downwards and left
[['D' 'X' 'X' 'X' 'X' 'X' 'W' 'X' 'X' 'H']
 ['X' 'O' 'X' 'X' 'X' 'O' 'X' 'X' 'O' 'X']
 ['X' 'X' 'G' 'X' 'C' 'X' 'X' 'R' 'X' 'X']
 ['T' 'X' 'X' 'X' 'X' 'X' 'S' 'X' 'X' 'X']
 ['X' 'E' 'X' 'X' 'X' 'E' 'X' 'X' 'X' 'X']]
['X']
['T' 'E']
['X' 'X' 'X']
['X' 'X' 'X' 'X']
['D' 'O' 'G' 'X' 'X']
['X' 'X' 'X' 'X' 'E']
['X' 'X' 'C' 'X' 'X']
['X' 'X' 'X' 'S' 'X']
['X' 'O' 'X' 'X' 'X']
['X' 'X' 'R' 'X' 'X']
['W' 'X' 'X' 'X']
['X' 'O' 'X']
['X' 'X']
['H']
Upwards and Right
[['X' 'X' 'X' 'X' 'E' 'X' 'X' 'X' 'E' 'X']
 ['X' 'X' 'X' 'S' 'X' 'X' 'X' 'X' 'X' 'T']
 ['X' 'X' 'R' 'X' 'X' 'C' 'X' 'G' 'X' 'X']
 ['X' 'O' 'X' 'X' 'O' 'X' 'X' 'X' 'O' 'X']
 ['H' 'X' 'X' 'W' 'X' 'X' 'X' 'X' 'X' 'D']]
['H']
['X' 'X']
['X' 'O' 'X']
['X' 'X' 'X' 'W']
['X' 'X' 'R' 'X' 'X']
['X' 'X' 'X' 'O' 'X']
['X' 'S' 'X' 'X' 'X']
['X' 'X' 'C' 'X' 'X']
['E' 'X' 'X' 'X' 'X']
['X' 'X' 'G' 'O' 'D']
['X' 'X' 'X' 'X']
['X' 'X' 'X']
['E' 'T']
['X']
Upwards and left
[['X' 'E' 'X' 'X' 'X' 'E' 'X' 'X' 'X' 'X']
 ['T' 'X' 'X' 'X' 'X' 'X' 'S' 'X' 'X' 'X']
 ['X' 'X' 'G' 'X' 'C' 'X' 'X' 'R' 'X' 'X']
 ['X' 'O' 'X' 'X' 'X' 'O' 'X' 'X' 'O' 'X']
 ['D' 'X' 'X' 'X' 'X' 'X' 'W' 'X' 'X' 'H']]
['D']
['X' 'X']
['X' 'O' 'X']
['T' 'X' 'X' 'X']
['X' 'X' 'G' 'X' 'X']
['E' 'X' 'X' 'X' 'X']
['X' 'X' 'C' 'O' 'W']
['X' 'X' 'X' 'X' 'X']
['X' 'X' 'X' 'X' 'X']
['E' 'S' 'R' 'O' 'H']
['X' 'X' 'X' 'X']
['X' 'X' 'X']
['X' 'X']
['X']

Answer 2

Вы можете преобразовать список, сдвинув каждую строку в виде списка на 1 больше, чем предыдущий, - и заполните заполненное пространство заполнителем (в этом случае используйте '0'):

mearray = np.array([[e for e in g] for g in grid])
words = ["HORSE","COW","DOG","ET"] # don't ask

Iиспользовал numpy, потому что я к этому привык, и это легче показать здесь, но это, безусловно, можно сделать в обычном понимании списка.После этого ваш массив теперь является массивом с нулевыми значениями:

[['H' 'X' 'X' 'W' 'X' 'X' 'X' 'X' 'X' 'D']
 ['X' 'O' 'X' 'X' 'O' 'X' 'X' 'X' 'O' 'X']
 ['X' 'X' 'R' 'X' 'X' 'C' 'X' 'G' 'X' 'X']
 ['X' 'X' 'X' 'S' 'X' 'X' 'X' 'X' 'X' 'T']
 ['X' 'X' 'X' 'X' 'E' 'X' 'X' 'X' 'E' 'X']]

Преобразуйте это, добавив смещающие заполнители:

leng = len(mearray)
def pad_with(vector, pad_width, iaxis, kwargs):
    pad_value = kwargs.get('padder', '0')
    vector[:pad_width[0]] = pad_value
    vector[-pad_width[1]:] = pad_value
    return vector
np.array([np.pad(mearray[i], (leng-i, i+1), pad_with) for i in range(leng)])

Ваш массив теперь:

[['0' '0' '0' '0' '0' 'H' 'X' 'X' 'W' 'X' 'X' 'X' 'X' 'X' 'D' '0']
 ['0' '0' '0' '0' 'X' 'O' 'X' 'X' 'O' 'X' 'X' 'X' 'O' 'X' '0' '0']
 ['0' '0' '0' 'X' 'X' 'R' 'X' 'X' 'C' 'X' 'G' 'X' 'X' '0' '0' '0']
 ['0' '0' 'X' 'X' 'X' 'S' 'X' 'X' 'X' 'X' 'X' 'T' '0' '0' '0' '0']
 ['0' 'X' 'X' 'X' 'X' 'E' 'X' 'X' 'X' 'E' 'X' '0' '0' '0' '0' '0']]

Вы можете ясно видеть, что HORSE и COW нормализованы.Вам нужно будет сделать это снова, переключив направление заливки, чтобы у вас были GOD и ET:

Обратное направление: np.array([np.pad(mearray[i], (i+1, leng-i), pad_with) for i in range(leng)])

[['0' 'H' 'X' 'X' 'W' 'X' 'X' 'X' 'X' 'X' 'D' '0' '0' '0' '0' '0']
 ['0' '0' 'X' 'O' 'X' 'X' 'O' 'X' 'X' 'X' 'O' 'X' '0' '0' '0' '0']
 ['0' '0' '0' 'X' 'X' 'R' 'X' 'X' 'C' 'X' 'G' 'X' 'X' '0' '0' '0']
 ['0' '0' '0' '0' 'X' 'X' 'X' 'S' 'X' 'X' 'X' 'X' 'X' 'T' '0' '0']
 ['0' '0' '0' '0' '0' 'X' 'X' 'X' 'X' 'E' 'X' 'X' 'X' 'E' 'X' '0']]

Теперь вы можетесм. GOD и ET (вверх ногами) в вашей матрице.Вы должны быть в состоянии использовать ваши оригинальные функции для их получения.

Answer 3

Если вас не слишком заботит порядок, в котором пересекаются все диагонали, эта функция генератора в чистом Python сделает то же самое, используя тот факт, что вверх-вправо-вниз-назад-назад:

def rotate(row, n):
    return row[n:] + row[:n]

def diags(grid, rev=False):
    n = len(grid)
    _grid = [list(row) + [None]*(n-1) for row in grid]  # pad for rotation
    for diag in zip(*(rotate(_grid[i], (i, -i)[rev]) for i in range(n))):
        d = ''.join(filter(None, diag))
        yield from (d, d[::-1])
    if not rev:
        yield from diags(grid, rev=True) 

>>> list(diags(grid))
['H',
 'H',
 'XX',
 'XX',
 'XOX',
 'XOX',
 'WXXX',
 'XXXW',
 'XXRXX',
 'XXRXX',
 'XOXXX',
 'XXXOX',
 'XXXSX',
 'XSXXX',
 'XXCXX',
 'XXCXX',
 'XXXXE',
 'EXXXX',
 'DOGXX',
 'XXGOD',
 'XXXX',
 'XXXX',
 'XXX',
 'XXX',
 'TE',
 'ET',
 'X',
 'X',
 'HORSE',
 'ESROH',
 'XXXXX',
 'XXXXX',
 'XXXXX',
 'XXXXX',
 'WOCXX',
 'XXCOW',
 'XXXXE',
 'EXXXX',
 'XXGXX',
 'XXGXX',
 'XXXT',
 'TXXX',
 'XOX',
 'XOX',
 'XX',
 'XX',
 'D',
 'D',
 'X',
 'X',
 'XX',
 'XX',
 'XXX',
 'XXX',
 'XXXX',
 'XXXX']

Answer 4

Вы можете выполнять итерацию по каждому символу, и, если символ является частью слова, тогда можно проверить каждую возможность (вертикальная, горизонтальная, правая и левая):

from collections import namedtuple
d = ['HXXWXXXXXD', 'XOXXOXXXOX', 'XXRXXCXGXX', 'XXXSXXXXXT', 'XXXXEXXXEX']
node = namedtuple('node', ['val', 'ischar'])
_d = [[node(i, i != 'X') for i in b] for b in d]
def traverse(_func, _start, _board):
  while True:
    try:
       _a, _b = _func(*_start)
       if not _board[_a][_b].ischar:
         break
       _start = [_a, _b]
       yield _board[_a][_b].val
    except:
       break

def get_words(board, *args):
  funcs = [[lambda x, y:(x-1, y), lambda x, y:(x+1, y)], [lambda x, y:(x, y+1), lambda x, y:(x, y-1)], [lambda x:(x-1, y-1), lambda x, y:(x+1, y+1)], [lambda x, y:(x-1, y+1), lambda x, y:(x+1, y-1)]]
  for _s1, _s2 in funcs:
     yield ''.join(traverse(_s1, args, board))+board[args[0]][args[1]].val+''.join(traverse(_s2, args, board))


def words(board, to_find):
  for i in range(len(board)):
    for b in range(len(board[0])):
      if board[i][b].ischar:
        for word in get_words(board, i, b):
          if word in to_find:
            yield word
          if word[::-1] in to_find:
            yield word[::-1] 

print(list(set(words(_d, ["HORSE","COW","DOG","ET"]))))

Вывод:

['DOG', 'ET', 'HORSE', 'COW']