# Scrabble Solver

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

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

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
}

"""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 = 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:

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

• @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.. Jan 24 '19 at 8:23
• 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”. Jan 24 '19 at 11:25
• @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. Jan 24 '19 at 11:30
• @BaileyParker chat reference: chat.stackexchange.com/transcript/message/48534932#48534932 Jan 24 '19 at 11:37

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.

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)

• 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? Jan 24 '19 at 18:56
• @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. Jan 24 '19 at 19:00
• But there can be more then 1000 possible words Jan 24 '19 at 19:02
• @Ludisposed That doesn't matter, as the limits come from nested recursion. Jan 24 '19 at 19:03
• 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 :) Jan 29 '19 at 10:10

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.

• 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? Jan 26 '19 at 13:18
• 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. Jan 26 '19 at 16:42