CODEWITHSUNDEEP
pythontrieboggle
Faren
Faren

Reputation: 23

Implementing Trie dictionary with dictionary children for Boggle game in Python 3.x

import typing
from typing import Optional, Dict
from collections.abc import Iterator


class TrieNode:
    
    def __init__(self):
        self.children: Dict[str, TrieNode] = {}  # maps a child letter to its TrieNode class
        self.is_word = False  # whether or not this Node is a valid word ending
        self.counter = 0  # a counter indicating how many times a word is inserted


class TrieDictionary():

    def __init__(self):
        self.root: TrieNode = TrieNode()

    def load_dictionary(self, filename: str) -> None:
        # add every word to the trie, not just the words over some length.
        node = self.root
        with open(filename) as wordsfile:
            for line in wordsfile:
                word = line.strip().lower()  # Do something with word here
                for letter in word:
                    if letter not in node.children:
                        node.children[letter] = TrieNode()
                    node = node.children[letter]
                node.is_word = True
                node.counter += 1

    def contains(self, word: str) -> bool:
        node = self.root
        for letter in word:
            if letter not in node.children:
                return False
            node = node.children[letter]
        return node.is_word


# Define the file path for the dictionary file
WORDS_FILE = "words.txt"

# Read all words from the file and store them in a list
with open(WORDS_FILE) as file:
    words = [line.strip() for line in file]

# Test the contains() method for all words in the dictionary file
def test_contains_all_example():
    # Make dictionary
    game_dict = TrieDictionary()
    game_dict.load_dictionary(WORDS_FILE)

    # Check that the contains() method returns True for all the words
    for s in words:
        assert game_dict.contains(s)


# Run the test
test_contains_all_example()

I have a sample file that contains words {aa,aah,aahed,aahing,aahs,aal,aalii,aaliis,aals}. The problem is I get an assertion error when running my test. I tried to debug to figure out what was wrong. I found out the results were all False. when debugging the load_dictionary method, I see that it creates a child for each letter when reading words, while I think it shouldn't duplicate them if they exist. For example, if 'aa' is already there, it should only add 'h' to add the word 'aah'. Currently, it will 'aa' after the first 'aa'. This is what I'm guessing, I'm really not sure which method is causing the problem! I appreciate your help in figuring this out.

Upvotes: 0

Views: 190

Answers (1)

Blckknght
Blckknght

Reputation: 104712

Your load_dictionary method initializes node at the wrong place. You need to reinitialize it every time you want to add a new word, but your current code only does it once. In your Trie, every word after the first gets added on to the end of the previous word.

To fix the issue, move the node = self.root line inside the loop:

def load_dictionary(self, filename: str) -> None:
    with open(filename) as wordsfile:
        for line in wordsfile:
            word = line.strip().lower()
            node = self.root                 # move this line here!!!!
            for letter in word:
                if letter not in node.children:
                    node.children[letter] = TrieNode()
                node = node.children[letter]
            node.is_word = True
            node.counter += 1

Upvotes: 1

Related Questions