Найти букву слов в матрице по диагонали

Question

У меня есть матрица 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

Однако, путем транспонирования матрицы поиск вверх-вниз также может быть завершен.Но я не уверен, как искать по диагонали.Есть ли способ поиска по диагонали?Или любое другое простое решение для всей проблемы?

Answer 1

Если ваша матрица всегда будет такой маленькой, я бы предложил вообще не использовать матрицу, а обрабатывать письма через списки косвенных адресов.

# 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) позволяет получить координаты 2D-сетки.Это приведет к следующему результату:

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

Примечание. Если вы хотите найти все совпадения для каждого слова (например, чтобы решить загадку со скрытым словом), вам понадобится дополнительная логика в цикле сегментной строкинайти все экземпляры слова в каждом сегменте (в отличие от 1-го, который даст этот пример).Вы можете также захотеть иметь специальный случай для палиндромов (например, ACA), который выйдет дважды (один раз в каждом противоположном направлении)

Answer 2

Поскольку вы уже знаете, как искать слово в строке (но, пожалуйста, прочитайте мой комментарий), я привожу здесь метод, как извлечь диагонали.

def diagelem(ll, a, b):
    try:
        if a < 0 or b < 0:
            raise IndexError
        return ll[a, b]
    except IndexError:
        return None

Мне нужно определить эту функцию дляизвлечь один диагональный элемент матрицы.Чтобы избежать округлости вокруг матрицы, я добавил оператор raise IndexError, если индексы меньше 0. Я не думаю, что вы этого хотите, но если я ошибаюсь, удаление оператора 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, используя ту же логику, что и вы.