from queue import Queue
import unittest

class Node():
    def __init__(self, char):
        self.char = char
        self.children = set()
        self.finished = False

class Trie():
    def __init__(self):
        self.root = Node('')
        self.char_score = {
            'a' : 1, 'b' : 3, 'c' : 5, 'd' : 2, 'e' : 1, 'f' : 4,
            'g' : 3, 'h' : 4, 'i' : 1, 'j' : 4, 'k' : 3, 'l' : 3,
            'm' : 3, 'n' : 1, 'o' : 1, 'p' : 3, 'q' : 10, 'r' : 2,
            's' : 2, 't' : 2, 'u' : 4, 'v' : 4, 'w' : 5, 'x' : 8,
            'y' : 8, 'z' : 4
        }

    def add(self, word):
        """Adds a word to the trie"""
        node = self.root
        for char in word:
            for child in node.children:
                if child.char == char:
                    node = child
                    break
            else:
                new_node = Node(char)
                node.children.add(new_node)
                node = new_node
        node.finished = True

    def _get_possible_words(self, letters):
        """
        Generates all possible words that can be made in the trie

        letters: (list)
            A list of letters
            * stands for a joker
        """
        que = Queue()
        que.put((self.root, self.root.char, letters))
        while que.qsize() > 0:
            node, word, letters_left = que.get()
            for child in node.children:
                if letters_left and (child.char in letters_left or "*" in letters_left):
                    new_word = word + child.char
                    new_bag = letters_left[:]
                    new_bag.remove(child.char if child.char in letters_left else "*")
                    que.put((child, new_word, new_bag))
                    if child.finished:
                        yield new_word


    def get_best_words(self, letters):
        """Returns a sorted list based on the (score, length of the word)"""
        return sorted(
            (w for w in self._get_possible_words(letters)),
            key=lambda w: (
                -sum(self.char_score[c] for c in w),
                len(w)
            )
        )

# Tests
class TrieTest(unittest.TestCase):
    def setUp(self):
        self.trie = Trie()
        self.words = ('tekst', 'test', 'tekens', 'tek', 'tekst', 'teksten')
        for word in self.words:
            self.trie.add(word)

    def test_get_best(self):
        self.assertEqual(
            ['tekst', 'test', 'tek'],
            self.trie.get_best_words(['t', 'k', 'e', 's', 't', 'n'])
        )

    def test_get_best_joker(self):
        self.assertEqual(
            ['teksten', 'tekst', 'tekens', 'test', 'tek'],
            self.trie.get_best_words(['t', 'k', 'e', 's', 't', '*', 'n'])
        )

if __name__ == '__main__':
    unittest.main()