Work the Shell

Words—We Can Make Lots of Words

Dave Taylor

Issue #259, November 2015

In this article, Dave Taylor shows complicated script code to complete the findwords script. Now you'll be ready to crush everyone in Scrabble and Words with Friends.

It was a dark and stormy night when I started this series here in Linux Journal—at least two months ago, and in Internet terms, that's quite a while. And just wait until our robot overlords are running the show, because then two months will be 10–20 generations of robot evolution and quite frankly, the T-2000 probably could have solved this problem already anyway.

Puny humans!

But, we haven't yet reached the singularity—at least, I don't think so. I asked Siri, and she said we hadn't, so that's good enough, right? Let's dive back in to this programming project because the end is nigh! Well, for this topic at least.

The challenge started out as trying to make words from a combination of letter blocks. You know, the wooden blocks that babies play with (or, alternatively, hurl at you if you're within 20 feet of them). Those give you six letters per space, but I simplified the problem down to the Scrabble tiles example: you have a set of letters on your rack; what words can you make with them?

I've talked about algorithms for the last few months, so this time, let's really dig in to the code for findwords, the resultant script. After discarding various solutions, the one I've implemented has two phases:

  • Identify a list of all words that are composed only of the letters started with (so “axe” wouldn't match the starting letters abcdefg).

  • For each word that matches, check that the number of letters needed to spell the word match up with the occurrences of letters in the starting pattern (so “frogger” can't be made from forger—but almost).

Let's have a look at the code blocks, because it turns out that this is non-trivial to implement, but we have learned to bend The Force to do our bidding (in other words, we used regular expressions).

First we step through the dictionary to identify n-letter words that don't contain letters excluded from the set, with the additional limitation that the word is between (length–3) and (length) letters long:


unique="$(echo $1 | sed 's/./&\
/g' | tr '[[:upper:]]' '[[:lower:]]' | sort | uniq | \
fmt | tr -C -d '[[:alpha:]]')"

while [ $minlength -lt $length ]
do
  regex="^[$unique]{$minlength}$"
  if [ $verbose ] ; then
    echo "Raw word list of length $minlength for \
    letterset $unique:"
    grep -E $regex "$dictionary" | tee -a $testwords
  else
    grep -E $regex "$dictionary" >> $testwords
  fi
  minlength="$(( $minlength + 1 ))"
done

I explained how this block works in my column in the last issue (October 2015), if you want to flip back and read it, but really, the hard work involves the very first line, creating the variable $unique, which is a sorted, de-duped list of letters from the original pattern. Given “messages”, for example, $unique would be “aegms”.

Indeed, given “messages”, here are the words that are identified as possibilities by findwords:

Raw word list of length 6 for letterset aegms:
assess
mammas
masses
messes
sesame
Raw word list of length 7 for letterset aegms:
amasses
massage
message
Raw word list of length 8 for letterset aegms:
assesses
massages
messages

Clearly there's more work to do, because it's not possible to make the word “massages” from the starting pattern “messages”, since there aren't enough occurrences of the letter “a”. That's the job of the second part of the code, so I'm just going to show you the whole thing, and then I'll explain specific sections:

pattern="$(echo $1 | sed 's/./&\
/g' | tr '[[:upper:]]' '[[:lower:]]' | sort | fmt 
 ↪| sed 's/ //g')"
for word in $( cat $testwords )
do
  simplified="$(echo $word | sed 's/./&\
/g' | tr '[[:upper:]]' '[[:lower:]]' | sort | fmt 
 ↪| sed 's/ //g')"

  ## PART THREE: do all letters of the word appear 
  # in the pattern once and exactly once? Easy way: 
  # loop through and remove each letter as used, 
  # then compare end states

  indx=1; failed=0
  before=$pattern
  while [ $indx -lt ${#simplified} ]
  do
    ltr=${simplified:$indx:1}
    after=$(echo $before | sed "s/$ltr/-/")
    if [ $before = $after ] ; then
      failed=1
    else
      before=$after
    fi
    indx=$(( $indx + 1 ))
  done
  if [ $failed -eq 0 ] ; then
    echo "SUCCESS: You can make the word $word"
  fi
done

The first rather gnarly expression to create $pattern from the specified starting argument ($1) normalizes the pattern to all lowercase, sorts the letters alphabetically, then reassembles it. In this case, “messages” would become “aeegmsss”. Why? Because we can do that to each of the possible words too, and then the comparison test becomes easy.

The list of possible words was created in part one and is stored in the temporary file $testwords, so the “for” loop steps us through. For each word, $simplified becomes a similarly normalized pattern to check. For each letter in the proposed word, we replace that letter with a dash in the pattern, using two variables, $before and $after, to stage the change so we can ensure that something really did change for each letter. That's what's done here:

after=$(echo $before | sed "s/$ltr/-/")

If $before = $after, then the needed letter from the proposed word wasn't found in the pattern, and the word can't be assembled from the pattern. On the other hand, if there are extra letters in the pattern after we're done analyzing the word, that's fine. That's the situation where we can make, for example, “games” from “messages”, and that's perfectly valid, even with the leftover letters.

I've added some debugging statements so you can get a sense of what's going on in this example invocation:

$ sh findwords.sh messages
Raw word list of length 5 for letterset aegms:
amass
asses
eases
games
gamma
gases
geese
mamma
sages
seams
seems
Raw word list of length 6 for letterset aegms:
assess
mammas
masses
messes
sesame
Raw word list of length 7 for letterset aegms:
amasses
massage
message
Raw word list of length 8 for letterset aegms:
assesses
massages
messages

created pattern aeegmsss
SUCCESS: You can make the word asses
SUCCESS: You can make the word eases
SUCCESS: You can make the word games
SUCCESS: You can make the word gases
SUCCESS: You can make the word sages
SUCCESS: You can make the word seams
SUCCESS: You can make the word seems
SUCCESS: You can make the word masses
SUCCESS: You can make the word messes
SUCCESS: You can make the word sesame
SUCCESS: You can make the word message
SUCCESS: You can make the word messages

So, we can make a dozen different words out of the word “messages”, including the word messages itself. What about the original pattern we were using in previous columns: “chicken”? For this one, let's skip the potential words and just look at the solution:

SUCCESS: You can make the word chic
SUCCESS: You can make the word chin
SUCCESS: You can make the word heck
SUCCESS: You can make the word hick
SUCCESS: You can make the word hike
SUCCESS: You can make the word inch
SUCCESS: You can make the word neck
SUCCESS: You can make the word nice
SUCCESS: You can make the word nick
SUCCESS: You can make the word check
SUCCESS: You can make the word chick
SUCCESS: You can make the word chink
SUCCESS: You can make the word niche
SUCCESS: You can make the word chicken

Impressive!

To make this work a bit better, I've added some error checking, included an -f flag so we can have the script also output failures, not just successes, and left in some additional debugging output if $verbose is set to true.

See Listing 1 for the complete code. It's also available at www.linuxjournal.com/extra/findwords.

That's it. Now we have a nice tool that can help us figure out what to play the next time we're stuck on Scrabble, Words with Friends, or even looking at a big stack of letter blocks.

Next month, I'll turn my attention to a different scripting challenge. Do you have an idea? Send it to info@linuxjournal.com.

Dave Taylor has been hacking shell scripts since the dawn of the computer era. Well, not really, but still, 30 years is a long time! He's the author of the popular Wicked Cool Shell Scripts (10th anniversary update coming very soon from O'Reilly and NoStarch Press) and can be found on Twitter as @DaveTaylor and more generally at his tech site www.AskDaveTaylor.com.