问题描述
我有一个 5*6 的矩阵，所有的值都是英文字母.我必须在矩阵中从左到右、从右到左、上下、上下和对角线中找到特定的单词.其实是拼字游戏.
I have a 5*6 matrix, all of the values are the English alphabets. I have to find specific words in the matrix in left to right, right to left, up down, down up and diagonally. It's a word puzzle actually.
我能找到单词 left right、right left、up down 和 down up.当涉及到对角地查找单词时，事情变得更加混乱.我提供了从左到右和从右到左搜索的示例代码.
I can find the words left right, right left, up down and down up. When it comes to finding the words diagonally things get messier. I have provided the sample code for the left to right and right to left search.
#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
但是，通过转置矩阵，也可以完成上下搜索.但是，我不确定如何对角搜索.有没有办法对角搜索?或者，整个问题的任何其他简单解决方案?
However, by transposing the matrix, the up-down and down-up search also can be completed. But, I am not sure how to search diagonally. Is there any way to search diagonally? Or, any other simple solution for the whole problem?
推荐答案
如果您的矩阵总是那么小，我建议您根本不要使用矩阵，而是通过间接列表处理字母.
If your matrix is always going to be that small, I would suggest not using a matrix at all but processing letters through indirection lists.
# 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")
要概括任何网格大小的方法，您可以像这样初始化间接列表:
To generalize the approach for any grid size, you can initialize the indirection lists like this:
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 ]
使用段间接列表，所有方向都以通用方式管理，允许您的搜索逻辑专注于单词而不是坐标计算:
Using the segments indirection list, all directions are managed in a generic fashion allowing your search logic to focus on the words rather than coordinate calculations:
# 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) 可以获得二维网格坐标.这将产生以下结果:
Using (position//colCount, position%colCount) allows you to get 2D grid coordinates. This will produce the following result:
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)，它会出现两次(每个相反方向一次)
这篇关于对角地查找矩阵中的单词字母的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！