Scrabble helper: find the highest score with any 7 letters

Question

I'm making a python script that accepts 7 letters and returns the highest scoring word along with all other possible words. At the moment it has a few "loops in loops" and others things that will slow down the process.

import json
#open file and read the words, output as a list

def load_words():
    try:
        filename = "dictionary_2.json"
        with open(filename,"r") as english_dictionary:
            valid_words = json.load(english_dictionary)
            return valid_words

    except Exception as e:
        return str(e)

#make dictionary shorter as there will be maximum 7 letters
def quick():
    s = []
    for word in load_words():
        if len(word)<7:
            s.append(word)
    return s


# takes letters from user and creates all combinations of the letters
def scrabble_input(a):
    l=[]
    for i in range(len(a)):
        if a[i] not in l:
            l.append(a[i])
        for s in scrabble_input(a[:i] + a[i + 1:]):
            if (a[i] + s) not in l:
                l.append(a[i] + s)

    return l

#finds all words that can be made with the input by matching combo's to the dictionary and returns them
def word_check(A):
    words_in_dictionary = quick()
    for word in scrabble_input(A):
        if word in words_in_dictionary:
            yield word


#gives each word a score
def values(input):
    # scrabble values
    score = {"a": 1, "c": 3, "b": 3, "e": 1, "d": 2, "g": 2,
             "f": 4, "i": 1, "h": 4, "k": 5, "j": 8, "m": 3,
             "l": 1, "o": 1, "n": 1, "q": 10, "p": 3, "s": 1,
             "r": 1, "u": 1, "t": 1, "w": 4, "v": 4, "y": 4,
             "x": 8, "z": 10}
    word_total = 0
    for word in word_check(input):
        for i in word:
            word_total = word_total + score[i.lower()]
        yield (word_total, str(word))
        word_total = 0

#prints the tuples that have (scrabble score, word used)
def print_words(a):
    for i in values(a):
        print i

#final line to run, prints answer
def answer(a):
    print ('Your highest score is', max(values(a))[0], ', and below are all possible words:')
    print_words(a)

answer(input("Enter your 7 letters"))

I have removed some of the for loops and have tried to make the json dictionary I found shorter by limiting it to 7 letter words max. I suppose I could do that initially so that it doesn't need to do that each time i run the script. Any other tips on how to speed it up?

Answer 1

Know your data structures.

    l=[]
    for i in range(len(a)):
        if a[i] not in l:
            l.append(a[i])
        for s in scrabble_input(a[:i] + a[i + 1:]):
            if (a[i] + s) not in l:
                l.append(a[i] + s)

How long does each of those not in checks take? If the list contains n strings, a not in check has to do up to n string comparisons. list is the wrong data structure to keep a collection of non-duplicate values: that is a set.

    l=set()
    for i in range(len(a)):
        l.add(a[i])
        l.update([a[i] + s for s in scrabble_input(a[:i] + a[i + 1:])])

is easier to read and should be faster for non-trivial inputs.

An alternative, which is arguably even easier to read, uses a single accumulator:

def scrabble_input(rack, prefix='', accum=set()):
    if len(prefix) > 0:
        accum.add(prefix)
    for i in range(len(rack)):
        scrabble_input(rack[:i] + rack[i + 1:], prefix + rack[i], accum)

    return accum

Further optimisation is possible by just avoiding local duplicates, and in that case you can switch back to using a list for the accumulator:

def scrabble_input(rack, prefix='', accum=[]):
    if len(prefix) > 0:
        accum.append(prefix)
    used = set()
    for i in range(len(rack)):
        if not rack[i] in used:
            used.add(rack[i])
            scrabble_input(rack[:i] + rack[i + 1:], prefix + rack[i], accum)

    return accum

Tastes may vary as to which is the nicest implementation. You can test to see which is the fastest for your use cases.

(Of course, for "serious" use as opposed to practice, itertools is your friend).

---

        if word in words_in_dictionary:

The same applies: you should notice a significant speedup by using a set for words_in_dictionary.

If you need to optimise further then you should be looking at more complicated data structures like tries or suffix trees. In principle you will be able to do a recursion with one parameter which is the current word (prefix or suffix, depending on your data structures); one parameter which is the unused letters from the Scrabble rack; and a final parameter which is the current node of the dictionary tree. Then if the dictionary tree tells you that no words exist with that prefix/suffix, you can abort early without generating all of its extensions.

Answer 2

Your algorithm appears to be "generate all possible permutations of the tiles and check to see which are legal scrabble words". That's a very inefficient way to solve the problem.

A better way is to construct a new dictionary which is a map from letter-sorted strings to legal words. For example, suppose your dictionary is BAD, DAB, OPTS, POTS, STOP. You want to construct a map:

ABD --> { BAD, DAB }
OPST --> { OPTS, POTS, STOP }

Now when you have a rack and you're looking to see what words it forms you sort the rack by letter order first and then you only have to consider the combinations and permutations of letters in alphabetical order to look up which ones are legal scrabble words. That is enormously less work.

How much less work? Suppose you have NVSAIET on your rack and you wish to know all the seven letter bingos. In your original approach you generate the 5040 possible re-orderings of that rack and check them all. With my approach you sort it to AEINSTV and look that up in your map to discover that the three seven letter words you can make with those letters are NAIVEST NATIVES VAINEST: that's one lookup instead of 5040.

How do you find the sixes? You look up EINSTV, AINSTV, AENSTV, AEISTV, AEINTV, AEINSV and AEINST. Now you are doing seven lookups instead of looking up each of the (again) 5040 six letter permutations from a rack of seven.

You end up doing only 120 lookups total, instead of the tens of thousands of lookups your present approach is doing.

An even better technique though is to construct a trie or a dawg (a Directed Acyclic Word Graph) from your dictionary, and recursively descend through the graph to discover what words can be made from the rack. Find yourself a good tutorial on tries, and learn how they work. Once you've mastered them, move on to dawgs.

Answer 3

To add to the previous answer, it is valuable to mention that a good practice consists in making the try block as light as possible in order to focus only on the code which is susceptible to stumble. Actually this is not the case in load_words().

First of all, the try block is not the suitable place to declare filename = "dictionary_2.json". You can wisely kick it out of that block, to the function level, for instance. You may even go further, by declaring it as a constant after picking the right name for it (you can easily understand that filename is the not the best name to give for a file's name: it is better to choose a name that reflects the content or the purpose of that file).

Also, in general, a return statement is not something to put inside the try block because the value to return is not error prone (understand error here in terms of exception). Clearly return valid_words should be kicked out from there too.

Last but not the least, this code is not very good:

except Exception as e:
   return str(e)

because we do not return exceptions but we rather raise them.

Given these facts, I would suggest you to re-write your function as follows:

import logging
# ...
# ...
logger = logging.getLogger(__name__)

def load_words():
    # pick a better name and you can put `filename` at a module level
    filename = "dictionary_2.json" 
    try:            
       with open(filename,"r") as english_dictionary:
           valid_words = json.load(english_dictionary)
    except Exception as e:
        logger.error(e)
        raise
    else:
       return valid_words

Answer 4

There are multiple times where you are calling the same function and getting the same result, which is wasteful. In answer(), you should call values() once, store it, and then print out the maximum value and the list. And if you sort the values ascending = False, then you can just print out the list; the maximum will just be the first one in the list, so you don't need to print it out separately. I don't think you need a function that does nothing but print out elements in a list.

You're also recalculating quick() every time you call word_check, and you're calling load_words() every time you call quick(). You should put that outside of word_check. Also, you don't really need an entire function for that. Just do [word for word in load_words() if len(word)<=7] (Note that if you want seven letter words, it should be <=7 or <8, not <7. And actually, since how Scrabble works is that you add the letters to an existing word, a more advanced version would look at words more than seven letters long.)

To generate words, you should use intertools.

You can save yourself a line of code if you put word_total = 0 at the beginning of the for-loop, but you can make the code even shorter by doing word_total = sum(score[i.lower()] for i in word).

Answer 5

Lots of good information in the answers here, but here's another idea to consider: Avoid creating all possible combinations and permutations of the rack.

For example, if, while you're generating the combinations and permutations, you encounter the prefix XQ then there's no point in generating the 120 possibilities that begin with XQ because none of those will match a value in your dictionary.

You'll probably have to measure to see if the benefit outweighs the cost of building a set of all the prefixes in your word list. If you're going to load the dictionary once and then let the user try out multiple racks, then it's probably worthwhile. If it's a one-shot deal, maybe not.

Answer 6

Typically, the best way to speed up a program is to first think generally about how a different approach or different algorithm might be more efficient. If you can't get your current implementation "fast enough" using the good advice already offered then I would suggest that you consider a different algorithm.

Along those lines, I recommend building a simple trie from your json dictionary, with one letter in each node. Then, in the "solve" phase, attempt to traverse the trie, using all possible permutations of your 7 letters. Either a depth-first search or a breadth-first search can be used, as long as you avoid traversing the same path more than once. There are many ways to go about it; apply the "three rules of optimization" and try what seems simplest to you first.

Answer 7

Isn't the entire premise of the algorithm wrong? As it stands, it seems to be using only 7 letters - please correct my distain for, and resultant lack of knowledge of, Python.

What about the letters already on the board: crossing an existing word gives you 8 letters, and passing through 2 words gives you 9 letters.

And what about double and triple letters? And double and triple words?

Just me?