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.
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.
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:
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.
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.
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.
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.
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.
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.
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: