在对角矩阵中查找单词的字母
Find Letter of Words in a Matrix Diagonally
我有一个5*6的矩阵，所有的值都是英文字母。我必须在从左到右、从右到左、上下、上下和对角线的矩阵中找到特定的单词。这实际上是一个字谜。
我能找到左右、右左、上下和上下这些词。当涉及到对角线查找单词时，事情变得更加混乱。我提供了从左到右和从右到左搜索的示例代码。
#the word I am looking for
word_list = ["CRAM", "ROTLQ", "TDML", "COOI"]
# create the matrix array or puzzle
letter_array = np.matrix([['C','R','A','M','B','A' ],
['R','O','T','L','Q','C' ],
['E','O','O','A','U','A'],
['I','T','E','I','A','L' ],
['I','A','L','M','D','T']])
#itenarate through word list
for word in word_list:
#flatten the array, convert it to list,
#finally join everythig to make a long string
left_right = ''.join(letter_array.flatten().tolist()[0])
# flip the string to search from right to left
right_left = left_right[::-1]
# if the word is there, it gives the index otherwise it gives -1
if left_right.find(word)>-1:
row, col = divmod(left_right.find(word), 6)
print ("The word is in left to right combination, row and column = ", row, col)
# look from right to left
elif right_left.find(word)>-1:
row, col = divmod(right_left.find(word), 6)
print ("The word is in right to left combination, row and column = ", row, col)
else:
print ("The word is in up down or diagonally located")
结果
The word is in left to right combination, row and column = 0 0
The word is in left to right combination, row and column = 1 0
The word is in right to left combination, row and column = 0 0
The word is in up down or diagonally located
但是，通过矩阵的转置，也可以完成上下查找。但是，我不确定如何对角搜索。有没有办法对角搜索？或者，对于整个问题还有其他简单的解决方案吗？
正如您已经知道如何在字符串中搜索单词（但请阅读我的评论），我在这里提供了一种如何提取对角线的方法。
def diagelem(ll, a, b):
try:
if a < 0 or b < 0:
raise IndexError
return ll[a, b]
except IndexError:
return None
我需要定义这个函数来提取矩阵的单个对角线元素。为了避免矩阵周围的循环，如果索引小于 0，我添加了一个 raise IndexError 语句。我不认为你想要那个，但是如果我错了，删除函数中的 if 语句应该授予你循环。
dd = []
for j in range(-letter_array.shape[0]+1, letter_array.shape[0]):
dd.append([diagelem(letter_array, i, i+j) for i in range(letter_array.shape[1])])
for j in range(0, 2*letter_array.shape[0]):
dd.append([diagelem(letter_array, i, -i+j) for i in range(letter_array.shape[1])])
diagonals = []
for diag in dd:
diagword = ''.join([letter for letter in diag if letter is not None])
if len(diagword) > 0:
diagonals.append(diagword)
print(diagonals)
前两个循环从对角线上构建单词。第一个循环从左上角到右下角构建单词，第二个循环从左下角到右上角。 dd这里是一个列表列表，里面有几个None。第三个循环将构建单词的内部列表连接在一起。最后 diagonals 是一个由对角线组成的单词列表。您可以使用您发布的相同逻辑搜索 word_list 中的单词是否在 diagonal 中的任何单词中。
如果你的矩阵总是那么小，我建议根本不要使用矩阵，而是通过间接列表处理字母。
# setup indirection lists for each axis
# -------------------------------------
# (only need to do this once)
#
# 00 01 02 03 04 05 <-- list positions corresponding
# 06 07 08 09 10 11 to letter coordinates
# 12 13 14 15 16 17
# 18 19 20 21 22 23
# 24 25 26 27 28 29
horizontal = [ [0,1,2,3,4,5],[6,7,8,9,10,11],[12,13,14,15,16,17],[18,19,20,21,22,23],[24,25,26,27,28,29] ]
vertical = [ [0,6,12,18,24], [1,7,13,19,25], [2,8,14,20,26], [3,9,15,21,27], [4,10,16,22,28], [5,11,17,23,29] ]
diagonal = [ [6,1], [12,7,2], [18,13,8,3], [24,19,14,9,4], [25,20,15,10,5], [26,21,16,11], [27,22,17], [28,23],
[4,11], [3,10,17], [2,9,16,23], [1,8,15,22,29], [0,7,14,21,28], [6,13,20,27], [12,29,26], [18,25] ]
horizontal = horizontal + [ list(reversed(positions)) for positions in horizontal ]
vertical = vertical + [ list(reversed(positions)) for positions in vertical ]
diagonal = diagonal + [ list(reversed(positions)) for positions in diagonal ]
# Generate the letter matrix as a simple list:
letter_array = ['C','R','A','M','B','A',
'R','O','T','L','Q','C',
'E','O','O','A','U','A',
'I','T','E','I','A','L',
'I','A','L','M','D','T' ]
word_list = ["CRAM", "ROTLQ", "TDML", "COOI"]
# transpose letter matrix into list of strings for each axis segment
horizontalStrings = [ "".join(map(lambda i:letter_array[i],positions)) for positions in horizontal]
verticalStrings = [ "".join(map(lambda i:letter_array[i],positions)) for positions in vertical]
diagonalStrings = [ "".join(map(lambda i:letter_array[i],positions)) for positions in diagonal]
# check for words ...
for word in word_list:
if any(filter(lambda string:word in string, horizontalStrings)):
print(word, " found horizontally")
elif any(filter(lambda string:word in string, verticalStrings)):
print(word, " found vertically")
elif any(filter(lambda string:word in string, diagonalStrings)):
print(word, " found diagonally")
else:
print(word, " not found")
[编辑]要推广适用于任何网格大小的方法，您可以像这样初始化间接列表：
rowCount = 5
colCount = 6
goRight = [ [ row*colCount+col for col in range(colCount) ] for row in range(rowCount) ]
goLeft = [ list(reversed(positions)) for positions in goRight ]
goDown = [ [ row*colCount+col for row in range(rowCount) ] for col in range(colCount) ]
goUp = [ list(reversed(positions)) for positions in goDown ]
goDownRight = [ [ row*colCount+row+col for row in range(min(rowCount,colCount-col))] for col in range(colCount-1) ] \
+ [ [ (row+col)*colCount+col for col in range(min(rowCount-row,colCount))] for row in range(1,rowCount-1) ]
goUpLeft = [ list(reversed(positions)) for positions in goDownRight ]
goDownLeft = [ [ row*colCount-row+col for row in range(min(rowCount,col+1))] for col in range(1,colCount) ] \
+ [ [ (row+1+col)*colCount-1-col for col in range(min(rowCount-row,colCount))] for row in range(1,rowCount-1) ]
goUpRight = [ list(reversed(positions)) for positions in goDownLeft ]
segments = [ ("horizontally going right", segment) for segment in goRight ] \
+ [ ("horizontally going left", segment) for segment in goLeft ] \
+ [ ("vertically going down", segment) for segment in goDown ] \
+ [ ("vertically going up", segment) for segment in goUp ] \
+ [ ("diagonally going down-right", segment) for segment in goDownRight ] \
+ [ ("diagonally going up-left", segment) for segment in goUpLeft ] \
+ [ ("diagonally going down-left", segment) for segment in goDownLeft ] \
+ [ ("diagonally going up-right", segment) for segment in goUpRight ]
使用分段间接列表，所有方向都以通用方式进行管理，使您的搜索逻辑能够专注于单词而不是坐标计算：
# Generate the letter matrix as a simple list:
letter_array = ['C','R','A','M','B','A',
'R','O','T','L','Q','C',
'E','O','O','A','U','A',
'I','T','E','I','A','L',
'I','A','L','M','D','T' ]
word_list = ["CRAM", "ROTLQ", "TDML", "COOI", "ROOT", "BLOT", "ALM", "ACA"]
# transpose letter matrix into list of strings for each axis segment
segmentStrings = [ (direction,positions,"".join(map(lambda i:letter_array[i],positions))) for direction,positions in segments ]
# check for words ...
for word in word_list:
for direction,positions,segmentString in segmentStrings:
startPos = segmentString.find(word) # see note below
if startPos < 0: continue
wordPositions = positions[startPos:][:len(word)]
gridPositions = [ (position // colCount, position % colCount) for position in wordPositions ]
print(word,"found\t starting at",wordPositions[0],direction,gridPositions)
break # don't break here if you want to find all matches
使用 (position//colCount, position%colCount) 可以得到二维网格坐标。这将产生以下结果：
CRAM found starting at 0 horizontally going right [(0, 0), (0, 1), (0, 2), (0, 3)]
ROTLQ found starting at 6 horizontally going right [(1, 0), (1, 1), (1, 2), (1, 3), (1, 4)]
TDML found starting at 29 horizontally going left [(4, 5), (4, 4), (4, 3), (4, 2)]
COOI found starting at 0 diagonally going down-right [(0, 0), (1, 1), (2, 2), (3, 3)]
ROOT found starting at 1 vertically going down [(0, 1), (1, 1), (2, 1), (3, 1)]
BLOT found starting at 4 diagonally going down-left [(0, 4), (1, 3), (2, 2), (3, 1)]
ALM found starting at 25 horizontally going right [(4, 1), (4, 2), (4, 3)]
ACA found starting at 5 vertically going down [(0, 5), (1, 5), (2, 5)]
注意：如果您想找到每个单词的所有匹配项（例如，解决隐藏的单词拼图），您将需要在 segmentStrings 循环中添加额外的逻辑，以在每个单词中找到一个单词的所有实例段（与此示例将产生的第一个段相反）。你可能还想有一个回文的特殊情况（例如 ACA），它会出现两次（每个相反的方向一次）
我有一个5*6的矩阵，所有的值都是英文字母。我必须在从左到右、从右到左、上下、上下和对角线的矩阵中找到特定的单词。这实际上是一个字谜。
我能找到左右、右左、上下和上下这些词。当涉及到对角线查找单词时，事情变得更加混乱。我提供了从左到右和从右到左搜索的示例代码。
#the word I am looking for
word_list = ["CRAM", "ROTLQ", "TDML", "COOI"]
# create the matrix array or puzzle
letter_array = np.matrix([['C','R','A','M','B','A' ],
['R','O','T','L','Q','C' ],
['E','O','O','A','U','A'],
['I','T','E','I','A','L' ],
['I','A','L','M','D','T']])
#itenarate through word list
for word in word_list:
#flatten the array, convert it to list,
#finally join everythig to make a long string
left_right = ''.join(letter_array.flatten().tolist()[0])
# flip the string to search from right to left
right_left = left_right[::-1]
# if the word is there, it gives the index otherwise it gives -1
if left_right.find(word)>-1:
row, col = divmod(left_right.find(word), 6)
print ("The word is in left to right combination, row and column = ", row, col)
# look from right to left
elif right_left.find(word)>-1:
row, col = divmod(right_left.find(word), 6)
print ("The word is in right to left combination, row and column = ", row, col)
else:
print ("The word is in up down or diagonally located")
结果
The word is in left to right combination, row and column = 0 0
The word is in left to right combination, row and column = 1 0
The word is in right to left combination, row and column = 0 0
The word is in up down or diagonally located
但是，通过矩阵的转置，也可以完成上下查找。但是，我不确定如何对角搜索。有没有办法对角搜索？或者，对于整个问题还有其他简单的解决方案吗？
正如您已经知道如何在字符串中搜索单词（但请阅读我的评论），我在这里提供了一种如何提取对角线的方法。
def diagelem(ll, a, b):
try:
if a < 0 or b < 0:
raise IndexError
return ll[a, b]
except IndexError:
return None
我需要定义这个函数来提取矩阵的单个对角线元素。为了避免矩阵周围的循环，如果索引小于 0，我添加了一个 raise IndexError 语句。我不认为你想要那个，但是如果我错了，删除函数中的 if 语句应该授予你循环。
dd = []
for j in range(-letter_array.shape[0]+1, letter_array.shape[0]):
dd.append([diagelem(letter_array, i, i+j) for i in range(letter_array.shape[1])])
for j in range(0, 2*letter_array.shape[0]):
dd.append([diagelem(letter_array, i, -i+j) for i in range(letter_array.shape[1])])
diagonals = []
for diag in dd:
diagword = ''.join([letter for letter in diag if letter is not None])
if len(diagword) > 0:
diagonals.append(diagword)
print(diagonals)
前两个循环从对角线上构建单词。第一个循环从左上角到右下角构建单词，第二个循环从左下角到右上角。 dd这里是一个列表列表，里面有几个None。第三个循环将构建单词的内部列表连接在一起。最后 diagonals 是一个由对角线组成的单词列表。您可以使用您发布的相同逻辑搜索 word_list 中的单词是否在 diagonal 中的任何单词中。
如果你的矩阵总是那么小，我建议根本不要使用矩阵，而是通过间接列表处理字母。
# setup indirection lists for each axis
# -------------------------------------
# (only need to do this once)
#
# 00 01 02 03 04 05 <-- list positions corresponding
# 06 07 08 09 10 11 to letter coordinates
# 12 13 14 15 16 17
# 18 19 20 21 22 23
# 24 25 26 27 28 29
horizontal = [ [0,1,2,3,4,5],[6,7,8,9,10,11],[12,13,14,15,16,17],[18,19,20,21,22,23],[24,25,26,27,28,29] ]
vertical = [ [0,6,12,18,24], [1,7,13,19,25], [2,8,14,20,26], [3,9,15,21,27], [4,10,16,22,28], [5,11,17,23,29] ]
diagonal = [ [6,1], [12,7,2], [18,13,8,3], [24,19,14,9,4], [25,20,15,10,5], [26,21,16,11], [27,22,17], [28,23],
[4,11], [3,10,17], [2,9,16,23], [1,8,15,22,29], [0,7,14,21,28], [6,13,20,27], [12,29,26], [18,25] ]
horizontal = horizontal + [ list(reversed(positions)) for positions in horizontal ]
vertical = vertical + [ list(reversed(positions)) for positions in vertical ]
diagonal = diagonal + [ list(reversed(positions)) for positions in diagonal ]
# Generate the letter matrix as a simple list:
letter_array = ['C','R','A','M','B','A',
'R','O','T','L','Q','C',
'E','O','O','A','U','A',
'I','T','E','I','A','L',
'I','A','L','M','D','T' ]
word_list = ["CRAM", "ROTLQ", "TDML", "COOI"]
# transpose letter matrix into list of strings for each axis segment
horizontalStrings = [ "".join(map(lambda i:letter_array[i],positions)) for positions in horizontal]
verticalStrings = [ "".join(map(lambda i:letter_array[i],positions)) for positions in vertical]
diagonalStrings = [ "".join(map(lambda i:letter_array[i],positions)) for positions in diagonal]
# check for words ...
for word in word_list:
if any(filter(lambda string:word in string, horizontalStrings)):
print(word, " found horizontally")
elif any(filter(lambda string:word in string, verticalStrings)):
print(word, " found vertically")
elif any(filter(lambda string:word in string, diagonalStrings)):
print(word, " found diagonally")
else:
print(word, " not found")
[编辑]要推广适用于任何网格大小的方法，您可以像这样初始化间接列表：
rowCount = 5
colCount = 6
goRight = [ [ row*colCount+col for col in range(colCount) ] for row in range(rowCount) ]
goLeft = [ list(reversed(positions)) for positions in goRight ]
goDown = [ [ row*colCount+col for row in range(rowCount) ] for col in range(colCount) ]
goUp = [ list(reversed(positions)) for positions in goDown ]
goDownRight = [ [ row*colCount+row+col for row in range(min(rowCount,colCount-col))] for col in range(colCount-1) ] \
+ [ [ (row+col)*colCount+col for col in range(min(rowCount-row,colCount))] for row in range(1,rowCount-1) ]
goUpLeft = [ list(reversed(positions)) for positions in goDownRight ]
goDownLeft = [ [ row*colCount-row+col for row in range(min(rowCount,col+1))] for col in range(1,colCount) ] \
+ [ [ (row+1+col)*colCount-1-col for col in range(min(rowCount-row,colCount))] for row in range(1,rowCount-1) ]
goUpRight = [ list(reversed(positions)) for positions in goDownLeft ]
segments = [ ("horizontally going right", segment) for segment in goRight ] \
+ [ ("horizontally going left", segment) for segment in goLeft ] \
+ [ ("vertically going down", segment) for segment in goDown ] \
+ [ ("vertically going up", segment) for segment in goUp ] \
+ [ ("diagonally going down-right", segment) for segment in goDownRight ] \
+ [ ("diagonally going up-left", segment) for segment in goUpLeft ] \
+ [ ("diagonally going down-left", segment) for segment in goDownLeft ] \
+ [ ("diagonally going up-right", segment) for segment in goUpRight ]
使用分段间接列表，所有方向都以通用方式进行管理，使您的搜索逻辑能够专注于单词而不是坐标计算：
# Generate the letter matrix as a simple list:
letter_array = ['C','R','A','M','B','A',
'R','O','T','L','Q','C',
'E','O','O','A','U','A',
'I','T','E','I','A','L',
'I','A','L','M','D','T' ]
word_list = ["CRAM", "ROTLQ", "TDML", "COOI", "ROOT", "BLOT", "ALM", "ACA"]
# transpose letter matrix into list of strings for each axis segment
segmentStrings = [ (direction,positions,"".join(map(lambda i:letter_array[i],positions))) for direction,positions in segments ]
# check for words ...
for word in word_list:
for direction,positions,segmentString in segmentStrings:
startPos = segmentString.find(word) # see note below
if startPos < 0: continue
wordPositions = positions[startPos:][:len(word)]
gridPositions = [ (position // colCount, position % colCount) for position in wordPositions ]
print(word,"found\t starting at",wordPositions[0],direction,gridPositions)
break # don't break here if you want to find all matches
使用 (position//colCount, position%colCount) 可以得到二维网格坐标。这将产生以下结果：
CRAM found starting at 0 horizontally going right [(0, 0), (0, 1), (0, 2), (0, 3)]
ROTLQ found starting at 6 horizontally going right [(1, 0), (1, 1), (1, 2), (1, 3), (1, 4)]
TDML found starting at 29 horizontally going left [(4, 5), (4, 4), (4, 3), (4, 2)]
COOI found starting at 0 diagonally going down-right [(0, 0), (1, 1), (2, 2), (3, 3)]
ROOT found starting at 1 vertically going down [(0, 1), (1, 1), (2, 1), (3, 1)]
BLOT found starting at 4 diagonally going down-left [(0, 4), (1, 3), (2, 2), (3, 1)]
ALM found starting at 25 horizontally going right [(4, 1), (4, 2), (4, 3)]
ACA found starting at 5 vertically going down [(0, 5), (1, 5), (2, 5)]
注意：如果您想找到每个单词的所有匹配项（例如，解决隐藏的单词拼图），您将需要在 segmentStrings 循环中添加额外的逻辑，以在每个单词中找到一个单词的所有实例段（与此示例将产生的第一个段相反）。你可能还想有一个回文的特殊情况（例如 ACA），它会出现两次（每个相反的方向一次）