Are You Pondering What I'm Pondering?

I’ve been playing some scrabble lately and to improve my game, I’ve considered memorizing all the valid two letter words. [1] There are 101 words, of which about 60-70 of them fall into the category of not-obvious-to-me. So, I thought it’d be easier to just find words that are comprised of only two letter words. For example, “somehow” would be on my list because so, om, me, eh, ho, and ow are all valid two letter words. After coming up with a list of words, I could then try to form sentences that used only these words to act as a mnemonic.

I started by writing a program to generate a list of words comprised of two letter words. This ended up being pretty straight forward (hint, don’t try to chain together two letter words). Here’s a list of valid words at least 4 letters long.

There are two problems with this list. First, there are two two letter words not included: qi and ki. They’ll just have to be memorized separately. The other problem is that this list is too long. Now the problem is choosing the smallest number of (or easiest to remember) words that include the other 99 two letter words.

Unfortunately, this is the set cover problem, which is NP-complete (the reduction is left as an exercise for the reader). I ended up pruning the list a bit by hand then using a crappy greedy solution. This gave me a final list of 37 words.

Ugh, that’s actually almost as bad as just memorizing the list. Unless of course someone wants to make a few clever sentences out of this.

[1] I play using OSPD4.