Heavy-duty computing challenge — maximum-density word packing

Question

Caution: This is a challenge for computers only. Humans are advised to stand well clear of the protective safety cage. There may be CPUs on fire before it's over.

Introduction

Nothing makes a wordplay enthusiast's heart sink more than a puzzle which begins with "How many words can you find in this... ?" It's such a dull and uninspired form of wordplay.

But not from the perspective of the puzzle creator. For the puzzle creator, it is one of the most natural forms of wordplay, and maximum-density word packing is one of the most interesting computational problems.

In this challenge, we will see how many words you can pack into a string of 20 letters.

Before you get alarmed with the thought that you will be searching over a raw 26^20 search space, please know that additional constraints will be imposed. Even so, there will still be plenty of combinatorial explosion left for you to handle.

The Challenge

Ten reflectors are affixed around a bicycle wheel. You must decorate each reflector with two letters. So that's 20 letters all the way around. Like this:

Your goal is to decorate the entire wheel in such a way that it produces the maximum number of distinct words. In my example above, 16 distinct words can be found. Can you top that?

You can use whatever letters you like, repeat them as many times as you like, and place them however you like, subject to the following constraints:

1. For every adjacent pair of reflectors, there must be at least one word which contains them both. This gives a sense of continuity all the way around the wheel. In my example above, the "LY" reflector is connected to its neighbor on the left through the word ALLY (as well as other words) and connected to its neighbor on the right through the word LYRE. For another example, the "RM" reflector is connected to both its neighbor on the right and its neighbor on the left through the word FORMAL.

2. If a word includes a reflector, it must use both letters on the reflector. A word cannot break up or divide a reflector. The reflector is indivisible. In my example above, TRAIN would not count as a word because it divides the "ST" reflector. Also, MALL would not count as a word because it divides both the "RM" reflector and the "LY" reflector.

3. Words count only once no matter how many times they appear around the wheel. For example, the wheel DECIDECIDECIDECIDECI yields only one distinct word, DECIDE.

4. Two-letter words on a single reflector are trivial and do not count as a word. In my example above, the "IN" reflector does not count as a word.

Word Lists

You may use any dictionary or word list that you like, provided that you can somewhat justify any questionable words by pointing us to a semi-legitimate reference on the Internet which vaguely satisfies us that it might be sort-of a genuine English word. So go ahead, bring on those medieval musical instruments, cathedral architectural details, obscure woodworking techniques, sailing terms, and equestrian vocabulary.

In other words, I'd rather you spend your time on algorithm development than cleaning up a word list.

You're just not allowed to amend your word list with nonsense words which just happen to increase your word count astronomically. (See KWYJIBO from The Simpsons.)

I am being very lenient here because I conjecture that the choice of word list is self-regulating. If you choose a word list which is very small (say, the most common 2000 words), your search space will be small and your algorithm will run quickly, but you will be limiting your choices and thus the number of possible solutions. If you choose a word list which is very large, your search space may be too large for your algorithm to finish searching in the lifetime of this universe.

For the record, I used a word list of about 70,000 words.

Naïve Algorithm

I have in my mind that you will write some sort of exhaustive search algorithm, or maybe employ some other clever technique. In any case, your algorithm must behave as if it does not know of any existing solutions.

In other words, you may not use my solution as a starting point and take it for a random walk in your word space.

Solution Presentation

In addition to your solution, please indicate the word list you used (at least the size of it) and describe your algorithmic approach.

You don't need to explicitly present your computer program. Just describe your methodology.

Keeping the Humans Entertained

Having trouble identifying the 16 words in my solution? Here they are:

1. REFOREST
2. FORE
3. FOREST
4. REST
5. RESTRAIN
6. STRAIN
7. RAIN
8. INFO
9. INFORM
10. INFORMAL
11. INFORMALLY
12. FORM
13. FORMAL
14. FORMALLY
15. ALLY
16. LYRE

Answer 1

Here are some notes on my own approach:

1. Prep work

I did a lot of prep work ahead of time so that the combinatorial engine could run as efficiently as possible.

For example, I took each word in my word list and shifted it in a circular fashion into all possible positions around the wheel. I stored these results in a lookup array for quick referencing later.

2. Binary encoding

Rather than mess with a lot of text and string functions, I encoded the entire wheel as a long binary number, five bits per letter. That way, I could use just one or two binary operations to do almost everything (e.g., check for compatibility between a word and the wheel under construction, insert a word into the wheel under construction, check if a completed wheel contains a particular word).

You can use binary AND to mask out the incomplete parts first, and then use XOR between two wheels to determine if they are compatible.

3. This one weird trick could give you 10x savings

Given any wheel, you can always rotate it in such a way that the lowest alphabetic reflector is at the top. This observation tells us that any brute force combinatorial generator will produce each wheel 10 times, just rotated into different positions. That's a lot of unnecessary work!

One way to avoid this deci-plicity is to start filling the wheel from a fixed starting point (say, the reflector at the top) and enforce the rule that every reflector which is filled after it must be alphabetically equal to or higher than the first reflector. This ensures that the first reflector is the lowest alphabetic.

You could, of course, insist that the first reflector be the highest alphabetic, or the most commonly used, or the least commonly used, or whatever. As long as your criterion is quick and easy to check, it is applied consistently, and it partitions the solution space cleanly.

4. Generate all possible candidate wheels through word tiling

It is tempting to just start filling in the reflectors one by one with all possible values. Don't do it, my friend! Don't do it.

Each reflector can take on 26^2 = 676 possible values. Okay, so not all of these values are valid. There is no word in my word list containing "XJ" or "ZQ". It's really more like 520 valid values.

Even so, powers of 520 blow up pretty quick. You're not even halfway around the wheel and you are already in the trillions.

So you might think, I know, I'll be clever about it. In natural language words, letter pairs only follow a limited set of other letter pairs. For example, the letter pair "GH" can only be followed by a few other letter pairs: "EA" (as in EGGHEADS), "ER" (HIGHER, GHERKINS), "TY" (MIGHTY), "OS" (GHOSTS), "OR" (FOGHORNS), "TS" (DELIGHTS, INSIGHTS, THOUGHTS), etc.

You could therefore create a lookup table or matrix to indicate which letter pairs follow each other. This reduces down the combinatorics significantly, but it is still unwieldy. My experiments suggest that it still balloons by a factor of about 74x with each successive reflector. Halfway around the wheel, and you are already in the billions.

The only wieldy approach I found is to fill the wheel by laying down whole words, overlapping them by at least one reflector as I go. (This also has the happy side effect of satisfying the constraint that any two adjacent reflectors must be contained in a word.)

It does have to be done carefully, however, because word lengths can vary and the amount of overlap can vary. You have to keep track of the frontiers of the growing solution.

5. Work in both directions and meet in the middle

There is a big payoff when you have wrapped around the wheel completely. At the point where the "serpent eats its tail", the last overlapping word that you fill in is unlikely to be compatible with the beginning of the serpent. This causes a sudden and drastic reduction in the number of solutions you have to store and process.

It's getting there which is the problem.

Even with word tiling, the numbers still grow quickly. By the time you have wrapped around to the point where the serpent eats its tail, you may be out of memory.

It seems a shame to have to wait so long to get that big payoff! Can't we somehow get that drastic reduction earlier?

I found that a workable solution is to construct the wheel in two separate halves, and then merge the two halves into complete wheels.

I start by filling in the top reflector with a value which will serve as the lowest alphabetic for the entire wheel.

For the clockwise set, I tile words clockwise from the top reflector until I get (at least) halfway around the wheel.

For the counterclockwise set, I tile words counterclockwise from the top reflector until I get (at least) halfway around the wheel.

Then, I merge the two sets of half wheels. This is not the massive operation it sounds like. In fact, it is quite fast. Ordering the two sets takes little time, and then a merge join takes almost no time at all.

6. Count contained words

After all the possible wheels are constructed, I have to count the number of distinct words contained in each. This is actually the most time-consuming computational process, and I haven't yet found any shortcut.

By my count, there are 81 possible words in a wheel (i.e., 81 stretches of different lengths and different positions around the wheel which could possibly be a word).

I simply chop the wheel into the 81 possible candidates and look up each candidate in my word list. I was sure to put effective indexing onto my word list beforehand for quick lookups!

And that's it... 17 hours of processing later, and I had my maximum solution. ;-)