"""
A Trie/Prefix Tree is a kind of search tree used to provide quick lookup
of words/patterns in a set of words. A basic Trie however has O(n^2) space complexity
making it impractical in practice. It however provides O(max(search_string, length of
longest word)) lookup time making it an optimal approach when space is not an issue.
"""


class TrieNode:
    def __init__(self):
        self.nodes = dict()  # Mapping from char to TrieNode
        self.is_leaf = False

    def insert_many(self, words: [str]):
        """
        Inserts a list of words into the Trie
        :param words: list of string words
        :return: None
        """
        for word in words:
            self.insert(word)

    def insert(self, word: str):
        """
        Inserts a word into the Trie
        :param word: word to be inserted
        :return: None
        """
        curr = self
        for char in word:
            if char not in curr.nodes:
                curr.nodes[char] = TrieNode()
            curr = curr.nodes[char]
        curr.is_leaf = True

    def find(self, word: str) -> bool:
        """
        Tries to find word in a Trie
        :param word: word to look for
        :return: Returns True if word is found, False otherwise
        """
        curr = self
        for char in word:
            if char not in curr.nodes:
                return False
            curr = curr.nodes[char]
        return curr.is_leaf

    def delete(self, word: str):
        """
        Deletes a word in a Trie
        :param word: word to delete
        :return: None
        """

        def _delete(curr: TrieNode, word: str, index: int):
            if index == len(word):
                # If word does not exist
                if not curr.is_leaf:
                    return False
                curr.is_leaf = False
                return len(curr.nodes) == 0
            char = word[index]
            char_node = curr.nodes.get(char)
            # If char not in current trie node
            if not char_node:
                return False
            # Flag to check if node can be deleted
            delete_curr = _delete(char_node, word, index + 1)
            if delete_curr:
                del curr.nodes[char]
                return len(curr.nodes) == 0
            return delete_curr

        _delete(self, word, 0)


def print_words(node: TrieNode, word: str):
    """
    Prints all the words in a Trie
    :param node: root node of Trie
    :param word: Word variable should be empty at start
    :return: None
    """
    if node.is_leaf:
        print(word, end=" ")

    for key, value in node.nodes.items():
        print_words(value, word + key)


def test_trie():
    words = "banana bananas bandana band apple all beast".split()
    root = TrieNode()
    root.insert_many(words)
    # print_words(root, "")
    assert all(root.find(word) for word in words)
    assert root.find("banana")
    assert not root.find("bandanas")
    assert not root.find("apps")
    assert root.find("apple")
    assert root.find("all")
    root.delete("all")
    assert not root.find("all")
    root.delete("banana")
    assert not root.find("banana")
    assert root.find("bananas")
    return True


def print_results(msg: str, passes: bool) -> None:
    print(str(msg), "works!" if passes else "doesn't work :(")


def pytests():
    assert test_trie()


def main():
    """
    >>> pytests()
    """
    print_results("Testing trie functionality", test_trie())


if __name__ == "__main__":
    main()

import math
from numbers import Rational


def number_decorate(func):
    def number_wrapper(*args, **kwargs):
        return Number(func(*args, **kwargs))
    return number_wrapper


def about(number):
    return Number(float(number.value))


def point(number):
    return Number(number.value / 10 ** (int(math.log10(number.value)) + 1))


class Number(Rational):
    names_list = ['ZERO', 'ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 'SIX', 'SEVEN', 'EIGHT', 'NINE']
    names = {i: name for i, name in enumerate(names_list)}

    def __init__(self, value):
        if isinstance(value, Number):
            value = value.value
        self.value = value

    def __complex__(self):
        return compile(self.value)

    def __bool__(self):
        return bool(self.value)

    @number_decorate
    def __add__(self, other):
        return self.value + other

    @number_decorate
    def __radd__(self, other):
        return other + self.value

    @number_decorate
    def __neg__(self):
        return -self.value

    @number_decorate
    def __pos__(self):
        return +self.value

    @number_decorate
    def __mul__(self, other):
        return self.value * other

    @number_decorate
    def __rmul__(self, other):
        return other * self.value

    @number_decorate
    def __truediv__(self, other):
        return self.value / other

    @number_decorate
    def __rtruediv__(self, other):
        return other / self.value

    @number_decorate
    def __pow__(self, power):
        return self.value**power

    @number_decorate
    def __rpow__(self, base):
        return base ** self.value

    @number_decorate
    def __abs__(self):
        return abs(self.value)

    @number_decorate
    def conjugate(self):
        return self.value.conjugate()

    def __eq__(self, other):
        return self.value == other

    def __float__(self):
        return float(self.value)

    @number_decorate
    def __trunc__(self):
        return math.trunc(self.value)

    @number_decorate
    def __floor__(self):
        return math.floor(self.value)

    @number_decorate
    def __ceil__(self):
        return math.ceil(self.value)

    @number_decorate
    def __round__(self, n=None):
        return round(self.value, n)

    @number_decorate
    def __floordiv__(self, other):
        return self.value // other

    @number_decorate
    def __rfloordiv__(self, other):
        return other // self.value

    @number_decorate
    def __mod__(self, other):
        return other % self.value

    @number_decorate
    def __rmod__(self, other):
        return self.value % other

    @number_decorate
    def __lt__(self, other):
        return self.value < other

    @number_decorate
    def __le__(self, other):
        return self.value <= other

    @number_decorate
    def __gt__(self, other):
        return self.value > other

    @number_decorate
    def __ge__(self, other):
        return self.value >= other

    @number_decorate
    def numerator(self):
        return self.value.numerator

    @number_decorate
    def denominator(self):
        return self.value.denominator

    def __int__(self):
        return int(self.value)

    def __repr__(self):
        return repr(self.value)

    @number_decorate
    def __and__(self, other):
        if 0 < other < 1:
            return self.value + other
        else:
            return self.value * 10 + other


ZERO = Number(0)
ONE = Number(1)
TWO = Number(2)
THREE = Number(3)
FOUR = Number(4)
FIVE = Number(5)
SIX = Number(6)
SEVEN = Number(7)
EIGHT = Number(8)
NINE = Number(9)