python - 递归搜索

Question

我使用一个 txt 文件作为“单词搜索板”，其中的单词被打乱。我还使用另一个 txt 文件中的单词列表，该文件可能位于也可能不位于单词板中。单词出现在各个方向，北、南、东、西、东北、西北、东南、西南以及这些方向的相反方向。搜索棋盘的函数必须是递归的。在我当前的 searchBoard() 中，我尝试使用单词的第一个字母进行搜索，然后检查周围环境中的下一个字母，依此类推。我的递归函数正在按我想要的方式工作，任何提示将不胜感激。

板的示例文本文件:

G J T P B A V K U V L V
M N Q H S G M N T C E E
Y H I J S G Q E N Y C W
G S K M G H C B M U T H
R A T V M N V D G V U T
E P G U E A B P W Q R T
T J C I D D R Q T E E C
U P C I S E N G B U O B
P S J C I V N F O U N N
M P R O J E C T R R A M
O H Q T P P D S H A P G
C O W U K Q E G I J M S

其他包含单词列表的 txt 文件:

COMPUTER 
SCRAM
COURSE
LECTURE
PROGRAMMING
PROJECT
SCIENCE
STUDENT

我的代码:

#Making the word file into a list
def getWords(wordList):
    fname = open(wordList,'r')
    lines = fname.read().split()

    return(lines)


#Making the puzzle file into a 2d list.
def buildBoard(puzzleBoard):

    fname = open(puzzleBoard,'r')
    boardList = []
    for line in fname:
        number_strings = line.split() 
        letters = [n for n in number_strings] 
        boardList.append(letters)

    fname.close()

    print(boardList[1][0])#row ,then col. Both start at 0s

    return(boardList)



#Recursively search board 
def searchBoard(pos,puzzleBoard,wordList):
    for word in wordList:
        firstLetter = word[:1]
        if puzzleBoard[pos[0]][pos[1]] == firstLetter:
           newPos = pos[0][0]
           searchBoard(newPos,puzzleBoard,wordList)

        #Checking above
        if puzzleBoard[pos[0]-1][pos[1]] == firstLetter:
          newPos = [pos[0]-1,pos[1]]  
          searchBoard(newPos,puzzleBoard,wordList)


def main():
    print("Welcome to the Word Search")
    print("For this, you will import two files: 1. The puzzle board, and 2. The word list.")
    puzzleBoard = input("What is the puzzle file you would like to import?: ")
    wordList = input("What is the word list file you would like to import?: ")

    puzzleBoard = buildBoard(puzzleBoard)    
    wordList = getWords(wordList)


    pos = [puzzleBoard[0][0]]
    searchBoard(pos,puzzleBoard,wordList)
main()

错误:

if puzzleBoard[pos[0]][pos[1]] == firstLetter:

TypeError: list indices must be integers or slices, not str

Answer 1

这是一个很好的做法:)
我拿了你的输入拼图板并编写了一个小函数，用于递归搜索拼图板。首先，它尝试查找单词的第一个字母 text.find(word[0], pos)，然后使用下限和模除法更改每个方向的 x,y 坐标，并查找下一个字母。如果下一个字母不匹配，它会尝试下一个方向，直到找到整个单词，或者字符不匹配，或者离开拼图板的边界。
除了 SCRAM 之外的所有单词都可以在您的拼图板上找到。

text = """
G J T P B A V K U V L V
M N Q H S G M N T C E E
Y H I J S G Q E N Y C W
G S K M G H C B M U T H
R A T V M N V D G V U T
E P G U E A B P W Q R T
T J C I D D R Q T E E C
U P C I S E N G B U O B
P S J C I V N F O U N N
M P R O J E C T R R A M
O H Q T P P D S H A P G
C O W U K Q E G I J M S"""

#cleans the input puzzleBoard
text = text.replace(' ', '').strip()
#gets the width and height of the puzzleboard
width = len(text.splitlines()[0])
text = text.replace('\n', '')
height = len(text) / width

#a dictionary storing the human readable directions
directions={0:'NW',1:'N',2:'NE',3:'W',4:'',5:'E',6:'SW',7:'S',8:'SE'}

#tries to find a word in a text
#returns x,y of the first character and the orientation of the word
def find_word(text, word):
    pos = 0
    while pos != -1:
        pos = text.find(word[0], pos)
        if pos > -1:
            for ori in [0,1,2,3,5,6,7,8]:
                found = True
                i = 0
                x = pos % width
                y = pos // height

                while found:
                    i += 1
                    if i == len(word) and found:
                        return (pos % width, pos // height, directions[ori])
                    #moves x,y in the selected direction
                    x += ori % 3 - 1
                    y += ori // 3 - 1
                    if x < width and y < height and x > -1 and y > -1:
                        found = text[width * y + x] == word[i]
                    else:
                        found = False
            pos += 1
    #nothing found
    return(-1, -1, directions[4])        

更新

解决相同的问题，但通过递归调用相同的函数。该函数返回找到的单词、最后一个字母的 x,y 位置和方向，即需要向后查找整个单词。

def find_char(text, pos, word, ori):
    x = int(pos % width)
    y = int(pos // height)
    x += ori % 3 - 1
    y += ori // 3 - 1
    if text[pos] != word[0]:
        return None
    if len(word) == 1:
        return (x,y)
    if x < width and y < height and x > -1 and y > -1:
        pos = int(width * y + x)
        if text[pos] == word[1]:
            if len(word) > 1:
                resp = find_char(text, pos, word[1:], ori)
                if resp:
                    return resp
        else:
            return None

word_list = ['COMPUTER', 'SCRAM', 'COURSE', 'LECTURE', 'PROGRAMMING', 'PROJECT', 'SCIENCE', 'STUDENT']
for i in range(len(text)):
    for ori in [0,1,2,3,5,6,7,8]:
        for word in word_list:
            resp = find_char(text, i, word, ori)
            if resp:
                print(word, resp, ori)