1

演習として、Pythonで非GUIボグルタイプのゲームを作成しようとしています。これまでのところ、ユーザーはボードサイズ（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

これはかなり単純な再帰関数で実行できると確信していますが、何時間も経つと迷子になります。ああ、私はむしろすべての可能な単語を事前に生成したくありません。これの目的は、再帰を使用して入力された単語を見つけることでした。

どんな助けでも大歓迎です！

4

1 に答える 1

0

面白い運動で、私はそれにひびが入った。以下のコードを投稿しているので、これをネタバレ注意報と考えてください。一般的なヒント：

  • コードをより小さなチャンクに分割します-それらすべてを支配する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")
于 2011-04-24T21:44:41.190 に答える