Basic Scrabble Word Search

Scrabble is, without a doubt, my all-time favorite board game. For me, it goes beyond mere fun and games; I’m actually, believe it or not, a competitive player! Yes, I’ve played in tournaments… and I’ve even won a few of them! Technically, that makes me a professional Scrabble player. Damn right I’m proud! It’s a great little factoid to bring up during interviews, parties and especially dates. Trust me, the ladies love a man who knows his way around a Scrabble board… (jk-lol-rofl-lmao). Jokes aside, it’s not just a dopey family board game to be pulled out on Thanksgiving and Christmas- though it’s certainly a great way to spend a few hours on a holiday. It’s a way of life!

Since I’ve been taking some of my favorite games over the past two weeks and converting them, or parts of them, into code, why not do that with one of the finest games ever devised by man (I put it just behind chess and go)??

Overview

The most fundamental skill in Scrabble is word finding. You get 7 letters on your rack, and you have to do two main things:

1. Unscramble the letters on your rack to find available words
2. Analyze the letters already played on the board and see where you can play words. This part is tricky, because the letters on the board almost function as an extension of your rack. This greatly expands the number of possible words you can play, but it also increases the difficulty of your task, as you have far more possibilities to generate and rank.

For this lil’ article, we’ll just be focusing on the 7 letters on our rack and coming up with code to find the words that lie within.

Dictionary

For a game like Scrabble, that consists of playing words, the primordial question is this: what is a word? This is a deeper, thornier question than it appears. In the end, the various governing bodies of Scrabble have combined and pared down the main dictionaries of the English-speaking world (e.g. Merriam-Webster, Oxford) to come up with one fixed word list. Any word that appears on the list is valid, and any word that don’t, ain’t. Unsurprisingly, humans being humans, this question has drummed up a fair bit of controversy of the years, and consequently, there are two main word sources to be used in tournament play- one of which holds about 140,000 words, and the other containing just north of 200,000. This difference has wrought a large schism in the Scrabble world, but most Americans use the shorter list.

For the purpose of this exercise, we’re just going to look at 2–4 letter words. I want to be able to run code in my browser, and importing all the 5–7 letter words would take up too much space. Here’s a screenshot of the “query” is used to get all 6,505 qualifying words:

Thank you, A2ZWordfinder.com! Please don’t use this during your Words With Friends games, kids.

Using the elegant copy and paste method, I’ve taken all these words and put them into a string, which I’ll then split on commas and store in an array:

const dictionary = `aa, aah, aahs, aal, aals...`.split(", ");

Now we have our dictionary! Ultimately, we want to input a given 7-letter rack (string of letters in this case) and output all the 2–4 letter subsets that make up valid words. Given that our letters can be in any order, we have a few different strategies:

1. Order all of our dictionary words alphabetically, then order our “rack” alphabetically, and see if the subsets are equal. This sounds alright, but recall that optimal sorting algorithms have O(n*log(n)), so we might not want to do all this sorting.
2. Come up with a function that counts the frequency of each letter of a word, then compares the frequencies of subsets of our rack to the frequencies of the words in our dictionary. For example, if we have the letters “aab”, we see that there are 2 A’s and 1 B. If we find a word in our dictionary with 2 A’s and 1 B, we’ve found a match! Sure enough, there are several words that fit: “aba” and “baa”. This frequency counting requires only one pass through each word, so we’d get O(n), which is better!

Another question is: do we want to generate every possible subset of our rack and then search through the entire 6K-word dictionary array? This seems like a lot of work. A 7-letter rack has the following # of subsets:

• 2 letters: 21
• 3 letters: 35
• 4 letters: 35

21+35+35=91. So that could mean up to 6505 * 91 = 591,955 checks for each rack! No thanks! However, 91 isn’t too bad a number, so if only there were a way to quickly check whether a given subset has a match in the dictionary, we’d be golden. In this case, maybe by sorting the dictionary entries once, which would admittedly be time-consuming, we could make all future checks much faster. This would be a one-time hit for many-times benefit; i.e. short-term pain for long-term gain. Sounds good! Let’s do it:

const sortedDictionary = dictionary.map(word=>word.split('').sort((a,b)=>a>b?1:-1).join('');

Splitting each string into an array, then sorting the array, then joining back into a string is a little ugly, but it gets the job done. Now, we have an array full of alphabetically sorted strings!

Wait… there’s one more issue. If we sort all of our words, how will we know what the original word was? And what if a given sorted string corresponds to multiple word, as in our previous example, where “aab” could be both “aba” and “baa”? Because, yeah, anagrams are a thing!

This is where we devise a solution that both joins our anagrams together and also enables quick searches. We’re going to create an Object, with the sorted strings as the keys, and the matching word/s as values!

const dictObj = {};
// loop through each word in our original, unsorted dictionary array
for (const word of dictionary) {
    // sort the string, using same logic as before
    const sortedWord = word.split('').sort((a,b)=>a>b?1:-1).join('');
    // If the key already exists, we push the word into the array
    // Otherwise, we create a new array and push first word into it
    if (dictObj[sortedWord]) dictObj[sortedWord].push(word);
    else dictObj[sortedWord] = [word];
}

Here’s what the resultant dictObj looks like:

Hooray, just what we were looking for! Note that the ‘aab’ key has an array of length two as a value: [‘aba’, ‘baa’], as noted above.

Now, for each sorted 2–4 letter string, we can simply look it up in dictObj. If the result is undefined, no match. If not undefined, then we’ve got a match!

Next, we’ll make a function that will take our 7-letter rack string, turn it into a sorted array, then search every 2–4 letter subset in our dictObj:

function wordFinder(rack) {
    const matchObj={}; // we'll use this to avoid duplicates
    rack = rack.split('').sort((a,b)=>a>b?1:-1);
    for (let i=0;i<rack.length;i++) {
        for (let j=i+1;j<rack.length;j++) {
            // Checking each two-letter substring
            const keyStr=rack[i]+rack[j];
            const match=dictObj[keyStr];
            if (match && !matchObj[keyStr]) {
                matchObj[keyStr]=match;
            }
            for (let k=j+1;k<rack.length;k++) {
                // Checking each three-letter substring
                const keyStr=rack[i]+rack[j]+rack[k];
                const match=dictObj[keyStr];
                if (match && !matchObj[keyStr]) {
                    matchObj[keyStr]=match;
                }
                for (let l=k+1;l<rack.length;l++) {
                    // Checking each four-letter substring
                    const keyStr=rack[i]+rack[j]+rack[k]+rack[l];
                    const match=dictObj[keyStr];
                    if (match && !matchObj[keyStr]) {
                        matchObj[keyStr]=match;
                    }
                }
            }
        }
    }
    return matchObj;
}

Good Lord, that’s a lot of ugly, repetitive code! I’m sure we could refactor this heavily. That said, let’s see what this output looks like with a few sample racks:

Wow, not too shabby! It gives us objects filled with array values, full of words that are indeed composed of the letters in our racks!

However, dictionaries are a little unwieldy. Let’s see if we can get these words to display on the screen, perhaps in alphabetical order:

function wordFinderDisplay(rack) {
    const matches = wordFinder(rack); // object from above function
    // Slightly complex-looking expression that basically starts out with an empty array, then loops through the matches values and pushes them into our ongoing array
    const matchesArray = Object.values(matches).reduce((rez,array)=>rez.concat(array),[]);
    // Returns the array as a sorted string, with words separated by commas return matchesArray.sort((a,b)=>a>b?1:-1).join(', ');
}

Let’s see if this yields the previous objects in a more visually-appealing format:

Very nice! Just as we’d hoped!

Conclusion

There’s a lot more I’d like to do with this; it would be nice to be able to sort the results not only alphabetically, but by length and even word value; e.g. the word ‘aa’ is only 2 points, but ‘jack’, to pick a totally random example, is 8+1+3+5=17! Much better! That would involve writing a few more functions, but given the lateness of the hour (past midnight local time), let’s just leave it here for now.

Until next time!