Как упражнение, я пытаюсь создать игру типа нечеткого графического интерфейса в python. Пока пользователь может ввести размер платы (4x4,5x5 и т.д.). Появится "массив" букв, а затем пользователь может ввести слово, которое, по их мнению, является допустимым.
Я хотел проверить, было ли введенное слово действительным, используя рекурсивную функцию. На небольших досках мое решение работает нормально. Однако на больших досках слова с похожими пусками и несколькими путями не регистрируются. Я чувствую, что это потому, что последняя часть моей функции не может отступить достаточно далеко, если текущий путь заканчивается, не найдя правильное слово.
Вот что я до сих пор:
def isAdjacent(word, wordLetter, possibleStarts, arrayDict, currWord, start):
#'word' is the word entered. 'wordLetter' is the current letter being looked for.
#'possibleStarts' is a list of tuples of the possible starting locations and subsequent positions of each found letter.
#'arrayDict' is a dictionary associating each position ((0,1), etc) with a game letter.
#'currWord' is used to check whether or not a word has been found.
#'start' is the tuple in possibleStarts that should be used.
if currWord == word:
return 1
x = possibleStarts[start][0]
y = possibleStarts[start][1]
arrayDict[x,y] = 0
optionsList = [(x - 1, y - 1), (x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y), (x + 1, y + 1)]
newStarts = []
count = 0
count2 = 0
for option in optionsList:
count += 1
if option in arrayDict:
if arrayDict[option] == word[wordLetter]:
if count2 < 1:
currWord += word[wordLetter]
arrayDict[option] = 0
count2 += 1
newStarts.append(option)
if count == 8 and newStarts:
return isAdjacent(word, wordLetter + 1, newStarts, arrayDict, currWord, start)
try:
if currWord != word:
if wordLetter > 2:
return isAdjacent(word, wordLetter - 1, possibleStarts, arrayDict, currWord[:-1], start - 1)
else:
return isAdjacent(word, wordLetter, possibleStarts, arrayDict, currWord, start - 1)
except:
pass
Я считаю, что по крайней мере часть проблемы лежит в блоке try в конце функции. Он работает, если слово не слишком длинное или если не так много возможностей. Например, попытка найти "raws" в следующем, не будет работать, даже если она есть:
W T S V
A X A H
S R T S
A B A W
Я уверен, что это можно сделать с помощью довольно простой рекурсивной функции, но после многих часов я теряюсь. О, я бы предпочел не генерировать все возможные слова заранее. Целью этого было использование рекурсии для поиска введенного слова.
Любая помощь очень ценится!
Интересное упражнение, у меня была трещина. Я размещаю код ниже, поэтому рассмотрим это предупреждение о спойлере. Для общих советов:
Что об этом. Я немного ржав на полных правилах Boggle, и я не совсем уверен, что вы делаете все время, но это то, что я придумал:
def paths(grid, x, y, l):
"""Returns a list of positions that the required letter is at"""
positions = [(x - 1, y - 1), (x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y), (x + 1, y + 1)]
return [p for p in positions if p in grid and grid[p] == l]
def matchWord(grid, pos, word):
"""Returns true if the word was found in the grid starting from pos"""
if word == "" : return True
pos_paths = paths(grid, pos[0], pos[1], word[0])
if pos_paths == [] : return False
return any(matchWord(grid, the_pos, word[1:]) for the_pos in pos_paths)
def wordInGrid(grid, word):
"""returns true if the word is in the grid"""
return any(matchWord(grid, key, word[1:]) for (key, val) in dict.iteritems(grid) if val == word[0])
gr_dict = {(0, 1): 'T', (1, 2): 'A', (3, 2): 'A', (0, 0): 'W', (3, 3): 'W', (3, 0): 'A', (3, 1): 'B', (2, 1): 'R', (0, 2): 'S', (2, 0): 'S', (1, 3): 'H', (2, 3): 'S', (2, 2): 'T', (1, 0): 'A', (0, 3): 'V', (1, 1): 'X'}
print wordInGrid(gr_dict, "RATS")
print wordInGrid(gr_dict, "WASABATAS")
похоже, что приведенный выше код возвращает True, даже если вы используете букву несколько раз. Например: "WASAW" → true. Как мы можем изменить это, чтобы иметь только одно использование каждой буквы?
except
должно действительно называть конкретный тип исключения. Трудно отлаживать подобный код.