如何创建一个遍历列表所有对角线可能性的for循环

Question

上下文

你如何在这个列表中找到对角单词？注意：为了显示一个单词已经被找到，它可以被任何字符替换，如"-">

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

我认为网格中对角线的所有可能性都是：

• 向下向左
• 向下和向右
• 向上和向左
• 向上和向右

在这种情况下，要查找的单词是：

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

我是如何垂直和水平找到单词的

斜向查找单词似乎比水平或垂直查找要困难得多。当水平查找单词时，我可以循环遍历grid中的每个row和words中的每个word。然后，我可以用符号* len(word)替换row中的word，以说明它已被找到。在垂直方向上，我将网格顺时针旋转90°，然后在水平方向上循环列表。然后，我将列表旋转回其原始状态。

对角查找单词有什么不同的解决方案？

Answer 1

您可以通过将列表中的每个字符串比上一个多移位1来转换列表，并用填充符填充创建的空间(在这种情况下使用'0'(：

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

我使用numpy是因为我更习惯它，在这里更容易显示，但它肯定可以在常规列表理解中完成。在此之后，您的数组现在是一个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 2

如果你不太关心遍历所有对角线的顺序，纯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 3

要迭代所有可能的对角线，可以使用numpy对角线。还可以使用numpyfliplr、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))

输出：

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 4

您可以对每个字符进行迭代，如果该字符是单词的一部分，则可以检查每个可能性(垂直、水平、右diag、左diag(：

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']