一种递归Boggle求解器

Question

“`Boggle是一种单词游戏，其中字母被随机放置在4x4网格中，例如：

A D Q P
N L E M
O S R T
V K J H

单词可以从任何字母开始，并通过查找一系列连接字母形成。字母可以对角、垂直或水平连接。

上述字句为“儿子”、“法援署”及“土地”，字母不得重复使用。

下面是拨动板的递归解决方案。我的解决办法的问题是它很慢。我不得不把字长限制为8，否则要花太长时间。

请你评论一般风格的改进，如果你能想到另一种方法来解决这个游戏，提示我应该做什么，我的下一次尝试。

这本字典来自这里

"""Boggle game solver"""
import copy


def words_from(board, row, column, running_string="", list_words=[]):
    """Calculate all possible words from a given starting position [row, column]"""
    if row in (4, -1) or column in (4, -1):
        return
    if len(running_string) > 4:
        return
    if board[row][column] != "-":
        new_string = running_string + board[row][column]
        new_board = copy.deepcopy(board)
        new_board[row][column] = "-"
        # Add new word
        if len(new_string) >= 3:
            list_words.append(new_string.lower())

        # Find next word
        next_move = [
            (1, 1),
            (-1, -1),
            (1, -1),
            (-1, 1),
            (1, 0),
            (0, 1),
            (-1, 0),
            (0, -1),
        ]
        for dx, dy in next_move:
            words_from(new_board, row + dx, column + dy, new_string, list_words)
        return list_words


def get_permutations(board):
    """Get all permutations """
    set_permutations = set()
    counter = 0
    print("Working..", end = "")
    for row in range(4):
        for column in range(4):
            print(".", end="")
            counter += 1
            words = words_from(board, row, column, list_words=[])
            if words:
                for word in words:
                    set_permutations.add(word)
            words = None
    return sorted(list(set_permutations))

def dictionary_check(set_permuations):
    """Check set_permutations for valid English words"""
    dictionary = {}
    with open("en-dict.txt", "r", encoding="utf8") as file:
        for line in file:
            dictionary[line.strip()] = 0

    counter = 0
    for word in set_permuations:
        if word.lower() in dictionary:
            counter += 1
            print(word)
    print(f"======\n{counter} words")


def find_words(board):
    """Find words on the boggle board"""
    set_permutations = get_permutations(board)
    print("Performing dictionary check....")
    dictionary_check(set_permutations)


def build_board(string):
    """Build board from string"""
    if len(string) != 16:
        print("Error. Must enter 4*4 grid (16 characters)")
        return
    board = [[*string[0:4]], [*string[4:8]], [*string[8:12]], [*string[12:16]]]
    find_words(board)


if __name__ == "__main__":
    string_board = "playthiswordgame"
    build_board(string_board)

Answer 1

你用这个程序观察到的问题是速度，所以让我们来看看这个。

运行程序时，我立即注意到get_permutations部分速度慢，而dictionary_check部分速度要快很多倍。这立即告诉我，在dictionary_check变得更快之前，寻找更快的方法是不值得的。毕竟，即使我们可以让dictionary_check完全不用花时间，程序运行的时间也差不多一样长！

当然，我在那里有点淘气。我带着我的内部时钟，当我应该做的是使用一个工具。这是运行cprofile的结果。

python -m cProfile -s cumtime boggle.py

             116983186 function calls (93930898 primitive calls) in 32.455 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   32.455   32.455 {built-in method builtins.exec}
        1    0.052    0.052   32.455   32.455 boggle.py:1()
        1    0.009    0.009   32.403   32.403 boggle.py:62(find_words)
        1    0.085    0.085   31.945   31.945 boggle.py:34(get_permutations)
5763088/16    4.231    0.000   31.726    1.983 boggle.py:15(words_from)
15128064/720384   12.915    0.000   27.119    0.000 copy.py:132(deepcopy)
3601920/720384    5.565    0.000   25.605    0.000 copy.py:210(_deepcopy_list)
 30256128    3.207    0.000    3.207    0.000 {method 'get' of 'dict' objects}
  3601920    1.764    0.000    2.288    0.000 copy.py:252(_keep_alive)
 23052288    1.619    0.000    1.619    0.000 {built-in method builtins.id}
 18009500    1.261    0.000    1.261    0.000 {method 'append' of 'list' objects}
 11526144    0.840    0.000    0.840    0.000 copy.py:190(_deepcopy_atomic)
        1    0.289    0.289    0.448    0.448 boggle.py:50(dictionary_check)
  4431757    0.324    0.000    0.324    0.000 {built-in method builtins.len}
   720284    0.131    0.000    0.131    0.000 {method 'add' of 'set' objects}
      173    0.076    0.000    0.076    0.000 {built-in method builtins.print}
   712738    0.067    0.000    0.067    0.000 {method 'lower' of 'str' objects}
   178691    0.017    0.000    0.017    0.000 {method 'strip' of 'str' objects}
      240    0.000    0.000    0.003    0.000 cp1252.py:22(decode)
      240    0.003    0.000    0.003    0.000 {built-in method _codecs.charmap_decode}
        1    0.000    0.000    0.000    0.000 {built-in method io.open}
        1    0.000    0.000    0.000    0.000 _bootlocale.py:11(getpreferredencoding)
        1    0.000    0.000    0.000    0.000 {built-in method _locale._getdefaultlocale}
        1    0.000    0.000    0.000    0.000 boggle.py:5(check_board)
        1    0.000    0.000    0.000    0.000 codecs.py:259(__init__)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

前几行只是调用序列:例如，在find_words中花费了大量的时间(累积时间)，但几乎所有的时间都在调用的函数中，而直接调用的函数很少(全部时间)。那不是你要削减的地方。

相反，在deepcopy内花费了大量的时间: 32秒钟中的27秒。这是真正的时间支出，也是开始击球的好地方。我想到了两个选择:要么寻找更简单、更便宜、更容易复制的董事会表示，要么尽量避免复制。

对于选项1，最简单的事情是一个带有16个元素的平面列表或元组，然后将其索引到as中。数据将是相同的，但您将避免复制所有额外列表的开销。

对于选项2，您可能希望使用一个板并跟踪您正在更改的内容(并且，根据您的实现，可能正是您从未更改的板的一个副本)。当你使用一个字母时，你会把它留出来；当你回到树上时，你会用原来的字母替换存根符号。

我自己还没有做过这件事，对性能的猜测总是很危险的，但是我会乐观地认为第二次改变的速度会快四到五倍。

上面的方法试图通过对底层算法进行最小的更改来提高效率。但是，如果您想获得更快的速度，则需要更改解决问题的方法。快速完成工作的第一条规则是“最快的工作是你不做的工作”。

虽然我在前面已经说过了，您不需要开始优化dictionary_check，但是在您探索网格时，了解您的单词列表可能会带来一些好处。例如，没有以"plt“开头的单词。如果您的running_string是"plt“，那么您发现的所有未来字符串都将在最后被过滤掉。一种选择是在开始时读取单词列表，并准备一本字典，其中包含所有出现的前缀。在递归调用words_from时，如果running_string不在前缀字典中，则立即返回。这可能会提供足够的收益，你可以取消你的限制长度8字。

我注意到，自从我开始回答这个问题和代码以来，这个问题和代码已经被编辑了好几次。我只想按原样发布，希望除了最微妙的细节之外，它仍然是有帮助的。