Boggle solver - Updated (with Trie)

Question

Here is an update to my previous boggle solver. The new version has an almost instantaneous output, removing the need to limit the length of words being searched for.

Any comments on my general coding implementation or layout would be appreciated.

"""Boggle game solver"""


class Trie:
    """Trie class to speed up programme by stopping exploration of non-existent prefixes"""

    def __init__(self):
        """Initialise the trie"""
        self.child = {}

    def insert(self, word):
        """Insert word into trie"""
        current = self.child
        for char in word:
            if char not in current:
                current[char] = {}
            current = current[char]

    def search(self, word):
        """Search the trie"""
        current = self.child
        for char in word:
            if char not in current:
                return False
            current = current[char]
        return True


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
    # Search the Trie
    if not trie.search(running_string):
        return
    if board[row][column] != "-":
        new_string = running_string + board[row][column]
        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(board, row + dx, column + dy, new_string, list_words)
        board[row][column] = new_string[-1]
        return list_words


def get_permutations(board):
    """Get all permutations """
    set_permutations = set()
    # Build Trie
    global trie
    trie = Trie()
    with open("en-dict.txt", "r", encoding="utf8") as file:
        for line in file:
            trie.insert(line)
    #Search for words from each starting position
    for row in range(4):
        for column in range(4):
            # Search for words
            words = words_from(board, row, column, running_string="", 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("\nPerforming 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

• Rather than a global Trie object I would make a TrieNode object that inherits from dict.

  • This can inherit from dict.
  • This can overload __missing__ to simplify insert.
  • Search isn't needed in the way I used it.

• Make a function build_trie, that builds and populates the trie from "en-dict.txt".

• build_board should really be called main and the code that builds the board should be moved into it's own function.
• find_words should be moved into main.

• build_trie should be called from main and passed to where it needs to be used.

  When possible don't use global. If you think it's impossible, then you're likely wrong.

  In this case you can move the value out of the function into main and pass it where it's needed.

  In other cases using a class, a closure or other ways can solve the issue.

• dictionary_check should only display words. And the first part of the function can be removed with the new TrieNode.

• Move next_move out of words_from, just make it a global constant.
• board[row][column] != "-" relies on mutating board I would recommend not mutating input to functions.
• words_from can be simplified by passing the current node, as then you're not trie.searching.
• In words_from len(new_string) >= 3 is an artificial limitation, that should be moved out of the function.
• get_permutations can be simplified by changing words_from to return an empty list on bad input.
• I would move set_permutations out of get_permutations, as it doesn't have much purpose in that function.
• I merged words_from and set_permutations to use a while loop, I found this to make the code easier to understand and make.
• Don't print and return, use raise.

---

For the most part your code seems to be fairly good, there's some pitfalls your falling down. But on a micro - line by line - scale your code is pretty good.

The problem I saw with your code is not seeing the big picture, and not following SRP.

Improving SRP should be fairly easy for you. If you're thinking of putting a comment that says the code is performing a different task, move it into a function.

To help with the big picture, when you follow SRP think to yourself if you should split the code into 2/3 functions and should call the three functions in succession. Like I changed main to do.

---

class TrieNode(dict):
    def __init__(self, value=None):
        super().__init__()
        self.value = value

    def __missing__(self, key):
        value = TrieNode()
        self[key] = value
        return value

    def insert(self, word):
        current = self
        for char in word:
            current = current[char]
        current.value = word


def build_trie():
    trie = TrieNode()
    with open("en-dict.txt", "r", encoding="utf8") as file:
        for line in file:
            trie.insert(line.strip())
    return trie


def board_from_string(string):
    if len(string) != 16:
        raise ValueError("Must enter 4*4 grid (16 characters)")
    return [
        [*string[0:4]],
        [*string[4:8]],
        [*string[8:12]],
        [*string[12:16]]
    ]


AROUND = [
    (dx, dy)
    for dx in range(-1, 2)
    for dy in range(-1, 2)
    if not (dx == dy == 0)
]


def get_words(trie, board):
    stack = []
    for row in range(4):
        for column in range(4):
            stack.append((trie, row, column, set()))
    while stack:
        node, row, column, parents = stack.pop()
        if row in (4, -1) or column in (4, -1) or (row, column) in parents:
            continue
        char = board[row][column]
        if char not in node:
            continue
        node = node[char]
        if node.value is not None:
            yield node.value
        for dx, dy in AROUND:
            stack.append((node, row + dx, column + dy, parents | {(row, column)}))


def display(words):
    words = sorted({w for w in words if len(w) >= 3})
    print('\n'.join(words))
    print(f"======\n{len(words)} words")


def main():
    string = "playthiswordgame"
    trie = build_trie()
    board = board_from_string(string)
    words = get_words(trie, board)
    display(words)


if __name__ == "__main__":
    main()