Блог

Главная - Вопросы по программированию - Как рекурсивно проверить ответ в игре типа boggle

Как рекурсивно проверить ответ в игре типа boggle

#python #recursion #boggle

#python #рекурсия #boggle

Вопрос:

В качестве упражнения я пытался создать игру типа boggle без графического интерфейса на python. Пока что пользователь может ввести размер доски (4×4, 5×5 и т.д.). Появится «массив» букв, а затем пользователь может ввести слово, которое, по его мнению, является допустимым вариантом.

Я хотел проверить, было ли введенное слово допустимым, используя рекурсивную функцию. На небольших платах мое решение, похоже, работает нормально. Однако на больших досках слова с одинаковым началом и несколькими путями не регистрируются. У меня такое чувство, что это потому, что последняя часть моей функции не может отступить достаточно далеко, если текущий путь заканчивается, не найдя правильного слова.

Вот что у меня есть на данный момент:

 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 в конце функции. Это работает, если слово не слишком длинное или не слишком много возможных вариантов. Например, попытка найти ‘raw’ в следующем, не сработает, даже если он есть:

 W T S V
A X A H
S R T S
A B A W

Я уверен, что это можно сделать с помощью довольно простой рекурсивной функции, но после многих часов я заблудился.
О, я бы предпочел не генерировать все возможные слова заранее. Целью этого было использовать рекурсию для поиска введенного слова.

Любая помощь приветствуется!

Комментарии:

1. На самом деле неквалифицированный except должен указывать конкретный тип исключения. Сложно отлаживать подобный код.

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

3. Да, try: ... except: pass это порождение сатаны (или Бога, в зависимости от того, что для вас хуже : p)

4. Это может помочь: mh-z.com/untangle/alg_heap.html

5. Спасибо за конструктивные комментарии. Большое спасибо за ссылку — там есть хорошая информация.

Ответ №1:

Интересное упражнение, у меня получилось. Я публикую приведенный ниже код, поэтому считайте это предупреждением о спойлере. Общие советы:

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

Примерно так. Я немного устал от полных правил 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")