5
\$\begingroup\$

The start of a simple Scrabble solver.

What I have so far:

  • Add a word to the trie
  • Return a sorted list with the all possible combinations, based on the letters input
  • Some basic tests

Edit

Since it hasn't received any answer yet...

  • Added a joker letter, for getting the best possible words

Please critique any and all

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()
\$\endgroup\$
  • \$\begingroup\$ @BaileyParker Your comment confuses me. If you have seen the code, you would have seen the unittests, and if you had run the code, you would have noticed that they all pass. ;) Could you tell me why you think this is not working, so I can edit the question and remove the ambiguity.. \$\endgroup\$ – Ludisposed Jan 24 at 8:23
  • \$\begingroup\$ I saw both the code and unittests. Your comment reaffirms what I said before. CodeReview is for fully working code. StackOverflow is for “why this is not working” and “does my Trie seem correct”. \$\endgroup\$ – Bailey Parker Jan 24 at 11:25
  • \$\begingroup\$ @BaileyParker There has been some discussion about this recently in chat. I know it is working, I am wondering if this is the best way to do it... Why else would I ask for a review? Me stating if this is correct does not mean I don't know if it is correct or not, but rather if there is a better way to write it. \$\endgroup\$ – Ludisposed Jan 24 at 11:30
  • \$\begingroup\$ @BaileyParker chat reference: chat.stackexchange.com/transcript/message/48534932#48534932 \$\endgroup\$ – Ludisposed Jan 24 at 11:37
1
\$\begingroup\$
  1. You have a couple of style issues:

    • you don't need the empty brackets after class definitions.
    • You should have two new lines before and after class definitions.
  2. You're conflating a base class and an implementation of it. I find keeping them separate to increase readability as you should know roughly what the base dose without reading the code. And you can more easily view the additional functionality.

  3. Node and Trie should be the same class.
  4. To be a pedant, I don't think your implementation is a Trie:

    • It's not ordered, and you don't apply the key to the edges.

      self.children = set()
      
    • Nodes in the tree store the keys.

      self.char = char
      
  5. I'd change add to __setitem__, and you could change it to be a for loop constantly using dict.setdefault.

And so I'd start with the following base class:

class Trie:
    __slots__ = ('value', 'children')

    def __init__(self, value=None):
        self.value = value
        self.children = {}

    def __getitem__(self, keys):
        node = self
        for key in keys:
            node = node.children[key]
        if node.value is None:
            raise KeyError('No value for the provided key')
        return node.value

    def __setitem__(self, keys, value):
        cls = type(self)
        node = self
        for key in keys:
            node = node.children.setdefault(key, cls())
        node.value = value

The largest difference between the above Trie and yours is the addition of a value. This should be the score of the word, which the Trie shouldn't be tasked with finding.

  1. As stated above, you should find the score of the word outside the Trie and so would make a function word_score.
  2. I personally would make get_best_words a function outside of the class, so that we don't depend on the class. However if you want it for ease of use, then I'd make it call the external function.
  3. This leaves _get_possible_words.

    • It has a \$O(n^3)\$ space complexity because you keep duplicating letters.
    • Your code is hard to read as you've manually implemented recursion. This is as you didn't define the function on Node.

    You can make a public function that changes letters to a collections.Counter, and then define the recursion on a private function that adds and removes a value from letters. It also allowed me to write the code in what I think is a far simpler manner.

Giving me the code:

import collections
import functools


def score(word, scores):
    return sum(scores[l] for l in word)


word_score = functools.partial(
    score,
    scores={
        '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 best_words(s_trie, letters):
    return sorted(
        s_trie.get_possible_words(letters)
        key=lambda (k, v): (-v, len(k))
    )


class Trie:
    __slots__ = ('value', 'children')

    def __init__(self, value=None):
        self.value = value
        self.children = {}

    def __getitem__(self, keys):
        node = self
        for key in keys:
            node = node.children[key]
        if node.value is None:
            raise KeyError('No value for the provided key')
        return node.value

    def __setitem__(self, keys, value):
        cls = type(self)
        node = self
        for key in keys:
            node = node.children.setdefault(key, cls())
        node.value = value


class ScrabbleTrie(Trie):
    def _get_possible_words(self, letters, prefix):
        if self.value is not None:
            yield prefix, node.value

        for key, node in self.children.items():
            if not letters.get(key, 0):
                continue
            letters[key] -= 1
            yield from node._get_possible_words(letters, prefix + key)
            letters[key] += 1

        if letters.get('#', 0):
            letters['#'] -= 1
            for key, node in self.children.items():
                yield from node._get_possible_words(letters, prefix + key)
            letters['#'] += 1

    def get_possible_words(self, letters):
        return self._get_possible_words(collections.Counter(letters), '')

    def get_best_words(self, letters):
        return best_words(self, letters)
\$\endgroup\$
  • \$\begingroup\$ I like your additions, the Counter is a smart counter to the problem I had with the copying of lists. I did go iterative (queue), because i thought Python and recursion don't really work well together. The generator does not have these issues I take? \$\endgroup\$ – Ludisposed Jan 24 at 18:56
  • \$\begingroup\$ @Ludisposed recursion is good, unless you're going to nestively recurse around 1000 times or more (IIRC). I highly doubt you'll have a word that long as the board is like 15 squares big. \$\endgroup\$ – Peilonrayz Jan 24 at 19:00
  • \$\begingroup\$ But there can be more then 1000 possible words \$\endgroup\$ – Ludisposed Jan 24 at 19:02
  • 1
    \$\begingroup\$ @Ludisposed That doesn't matter, as the limits come from nested recursion. \$\endgroup\$ – Peilonrayz Jan 24 at 19:03
  • \$\begingroup\$ I have decided to expand on this code, but there were a few issues I needed to fix before being able to use it. 1. That lambda expression is Python2.x iirc can't unpack in lambda anymore. 2. A typo with node.value -> self.value 3. Having to set the possible words to avoid duplicates when adding a joker. But overall it works fine, and the value addition does come in handy in the future. Thnx :) \$\endgroup\$ – Ludisposed Jan 29 at 10:10
1
\$\begingroup\$

You are too enamored of the Trie class. Ask yourself, "what am I doing?" I believe the answer looks something like this:

In order to "solve" word-generation board games, I am trying to write code that can:

  1. Given a 'context' string and two numeric 'limits' indicating the maximum number of before/after cells, plus a list of 'tile' characters possibly including match-any-letter wildcard values, generate the sequence of all possible words that can be built starting with, ending with, or surrounding the context string.

  2. Compute a score for each generated word, using a provided "base" scoring mechanism and possibly a position-based mechanism for additional "word" or "letter" scores. (E.g., "Double Letter Score" or "Triple Word Score")

Notice that the word "trie" never appears in those requirements. This is because the trie is an implementation detail, rather than a part of the solution. In simple OO terms, your WordList object might "has-a" trie, but it doesn't "is-a" trie.

What you have, I think, is a Lexicon (which is a way of saying "WordList" without using the word 'list'). And you're going to ask that Lexicon one question to start with: what words can you make with this fixed part and these variable parts?

# Board like _ _ _ _ _ _ _ A N D _ _ with tiles [a,e,f,m,q,r,t]
lex.generate_words(fixed='and', max_before=7, max_after=2, tiles='aefmqrt')

(Obviously you would also call with fixed='a', fixed='n', fixed='d' going crossways.)

Once you have a sequence of words coming from the Lexicon, you will want to score the words. You will need to somehow map the words to positions on the board, and then to scoring. For example, if your fixed='an' you might generate "banana" two ways (b[an]ana vs. ban[an]a), and the Lexicon should report that, and your scoring algorithm should account for it so you can try to match the "Double Word Score" in whatever position.

So I think you will need a scoring mechanism that is sensitive to the board location, and also to the rules of the game. (Official Scrabble(tm) has different scoring rules than Words-with-Friends, for example.)

When you get particularly advanced, you might also want to ask the Lexicon for matches involving multiple fixed parts: _ _ _ A N D _ _ R A M _ _. I'll leave that as an exercise for the coder.

\$\endgroup\$
  • \$\begingroup\$ I haven't implemented all that yet, but would you say a Trie is the correct dataclass for generating words from a lexicon or should I drop it entirely? \$\endgroup\$ – Ludisposed Jan 26 at 13:18
  • \$\begingroup\$ It seems like you have the trie working, so keep it by all means. But remember what you're building. If the trie starts to give you problems, switch to something else. \$\endgroup\$ – Austin Hastings Jan 26 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.