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)

• Josiah: A trie is a great option for this. I don't have time for a proper review, but one thing that sticks out as worth mentioning: the same trie structure can both indicate prefixes and indicate whole words in the dictionary. If you added that distinction, you could avoid adding any invalid words to list_words in words_from in the first place, and therefore avoid needing the additional dictionary_check to take them out again afterwards.

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()

• MrJoe: Using the binary operator is pretty smart. Also very clever to inherit the dict class. Didn't think about that. Thank you