Work the Shell

More words. This time I noticed that many of my friends and family are engrossed in a popular new iPad and iPhone game called Draw Something. It's a sort of digital version of Pictionary, but what makes it interesting to me is that you're presented with a sketch and have to guess what it is, but you're given a set of letters and spaces that clue you in to how long the word is. See Figure 1 for an example.

Figure 1. What the heck is this sketch from Draw Something?

You can see in Figure 1 that you're presented with a set of letter tiles and a blank space for the word. In this case, you can see that the word is five letters long and that the set of letters from which you can choose is A D E E K N N S V W X X. By the duplication of letters, you can conclude that if the word to guess includes more than one occurrence of a letter, each letter has to appear.

This is, of course, a simple variation on the word selection programs we've been writing during the past few months as part of our Words With Friends/Scrabble program, so let's see what's involved in making this cheat work. Let's assume that the words are in our existing dictionary.

In my previous few articles, we've developed a handy script called findwords.sh that you give a set of letters and it tells you what words could be made out of those tiles—for example:

$ findword.sh sejdowa
++ word dowse can be constructed from the letters sejdowa
++ word jawed can be constructed from the letters sejdowa

Yes, those are particularly bad letters for any Scrabble-like game when there are only two words possible that are at least five letters long (by default, the script omitted all words four-or-less-letters long because usually there are a ton of them).

It seems like we could apply the same script to Draw Something without modification, however, simply by listing all the letters possible—more than seven, needless to say. Here's what happens when I do that, with a wee bit of tweaking the output:

$ findword.sh adeeknnsvwxx
++ word ANNEX can be constructed, length = 5
++ word ASKEW can be constructed, length = 5
++ word DENSE can be constructed, length = 5
++ word EAVES can be constructed, length = 5
++ word EVADE can be constructed, length = 5
++ word KNAVE can be constructed, length = 5
++ word KNEAD can be constructed, length = 5
++ word NAKED can be constructed, length = 5
++ word NEEDS can be constructed, length = 5
++ word SEDAN can be constructed, length = 5
++ word SENNA can be constructed, length = 5
++ word SEVEN can be constructed, length = 5
++ word SKEWED can be constructed, length = 6
++ word SNAKE can be constructed, length = 5
++ word SNEAK can be constructed, length = 5
++ word SWANK can be constructed, length = 5
++ word VEXED can be constructed, length = 5
++ word WAKEN can be constructed, length = 5
++ word WAXEN can be constructed, length = 5
++ word WEAKEN can be constructed, length = 6
++ word WEAVE can be constructed, length = 5
++ word WEEDS can be constructed, length = 5

The only tweak I'd make is that we should specify the length of the word and have it show us only matches that could fit; showing a six-letter word like WEAKEN isn't very useful.

To fix that, let's add an optional second parameter to the script that specifies target word length. Being lazy, I'll make that parameter #2 and use the extraordinarily sloppy parameter test of:

if [ ! -z "$2" ] ; then
  targetlength=$2
fi

Yeah, yeah, getopt would be better, but as I've discussed before, sometimes scripting is more about getting the job done than it is about being optimal in your coding strategy.

The main loop continues to increase in complication too, now adding the targetlength parameter:

for word in $(cat $possibilities)
do
length=$(echo $word | wc --c)
  length="$(( $length - 1 ))"
  idx=1
  while [ $idx -le $length ] ; do
    letter=$(echo $word | cut -c$idx)
    occurrences $letter $word
    wordfreq=$freq  # number of times letter occurs #1
    occurrences $letter $1 # and letter occurrences #2
    uword=$(echo $word | tr '[[:lower:]]' '[[:upper:]]')
    if [ $wordfreq -gt $freq ] ; then
      break # get out of the "nearest" loop
    else
      if [ $idx -eq $length ] ; then
        if [ $targetlength -ne 0 ] ; then
          if [ $length -eq $targetlength ] ; then
            echo "word $word can be constructed"
          fi
        else
          echo "word $uword can be constructed, length = $length"
        fi
      fi
    fi
    idx=$(( $idx + 1 )) # increment loop counter
  done
done

If you're comparing this with the previous versions of this loop, you'll notice a few changes, including the uword assignment that converts words from lowercase to uppercase. Most important, if targetlength is nonzero, the script will list only words that match the target length.

Now the results are a bit trimmed down, but let's go a bit further and try to get all the results on a single line by simply having the word itself output, adding a before-and-after wrapper line, and pushing the entire output through the ever-handy fmt command:

$ findword.sh adeeknnsvwxx 5 | fmt
Possibilities: ANNEX, ASKEW, DENSE, EAVES, EVADE, KNAVE, KNEAD, NAKED,
NEEDS, SEDAN, SENNA, SEVEN, SNAKE, SNEAK, SWANK, VEXED, WAKEN, WAXEN,
WEAVE, WEEDS, out of the letter set adeeknnsvwxx.

That's a good place to stop. Oh, and did you figure out the solution to the Draw Something puzzle yet? I hope so!

The only problem is that this isn't a great cheat in this particular instance, because one of the things that makes Draw Something popular is that it uses a lot of contemporary words like Lady Gaga, NASCAR and JayZ—words that aren't going to be in our dictionary. Maybe that's another reason it's popular—unlike Words With Friends, it's hard to cheat at Draw Something. Ah well, it's still an interesting extension to our earlier word finder script!