Alternades

An alternade is one of those fun word puzzles that I enjoy solving by cheating, using wizardry rather than brain sweat. The idea is to find two English words that when combined create another, longer, word. The letters from the first word are strictly alternated with those from the second, like so:

Term + hoes = T h e o r e m s

Cheating?

My raw, grain-fed brain could not find a single alternade by itself, but was able to brute force every possible solution — using the power of Python's sets and its string slicing operations:

def find_alternades(words: set[str]) -> dict(str, tuple[str, str]):
    found = {}
    for word in words:
        first, second = word[::2], word[1::2]
        if (first in words) and (second in words):
            found[word] = (first, second)
    return found

I wrote a script around this function, then ran it against a list of legal Scrabble words and got lots of output:

$ python3 alternades.py scrabble.txt
ab + ba = abba
ab + be = abbe
al + be = able
...skip 1,484 lines...
wides + erns = weirdness
polls + epees = peopleless
tinily + renal = triennially

Found 1,490 alternades from list of 172,820 words in 0.061 seconds.

Success! 'Triennially' is indeed cited as the longest possible alternade. They're a bit obscure, though. My favourite solutions are where all three words are easily recognised. Using a shorter wordlist helped:

most + ones = moonsets
pams + slit = psalmist
riot + anus = rainouts
shoe + cold = schooled
term + hoes = theorems
blond + aloe = ballooned

Download both the script and its full output from the bottom of this article.

Better living through data structures

Careful readers will have noticed that the function calls for a Python set of words as its input, and not the usual list. This is super duper important. My PC only needed 17ms to load a (relatively) small list of of 55k words into a list, convert that list into a set, and then test every single word in that list. Not bad!

Skipping the 'convert list into a set' step causes the runtime to balloon. From 17 thousandths of one to fourteen whole seconds. 820x slower!

Larger inputs are worse. Examining 290k words took 110ms with sets, 400 seconds with a list = 3,700x slower. It's actually a nice illustration of the difference between the runtimes of O(n) and O(n²) algorithms. The input got 5x larger. The 'fast' program took 6 times longer (≈5), the 'slow' took 28 times as long (≈5²) .

Other interesting bits

I really like this function. It is doing a awful lot of work in only a few lines of code. There are some things that are worth pointing out that might not be immediately obvious.

Start with the answer, not the question

Firstly, we work backwards. In our function we start with the answer (eg. ballooned) then check to see if the two strings that make that word (blond + aloe) are actually English words. We have to do that for every word in our list:

for answer in words:
    first, second = # Split answer
    # Look-up first AND second in dictionary

The other, perhaps more obvious, approach is to check every combination of words instead:

for first in words:
    for second in words:
        answer = # Join first and second
        # Look-up answer in dictionary

This would be... non-optimal. Only having to do one look-up per loop seems nice — but that inner loop really kills us. It would have to run more than 3 billion times, and that's with our 'short' list of 55 thousand words. I'm not patient enough to have actually tried this solution.

Expressiveness

Secondly, Python shows off some really expressive syntax; here breaking our answer into its component parts using the step argument to a string slicing expression:

>>> word = 'sweaty'
>>> word[::2], word[1::2]
('set', 'way')

Here looking up two possible words in our dictionary, and in a single line of code, concisely and naturally:

if (first in words) and (second in words):
    # Solution found!

In this case that expressiveness does let us to shoot ourselves in the foot. That huge slow-down we saw earlier? It was caused by the in operators in this statement. It's a slow operation for a list, but extremely fast for a set.

Download

This article was based on a full-featured script, which I welcome you to download and around with. The script has the type-checking and documentation that I removed here for the the sake of brevity.

• The Python3 script (requires Python 3.8+)
• All the alternades it found using legal words for the game Scrabble.

You will need a word list to use as input. If you're a Linux user you'll already have one waiting for you at /usr/share/dict/words. Our better-looking Mac-using friends have a word list there too. In any case, the SCOWL project is worth checking out if you're interested in words.

Credits

I learnt about the existence of Alternades in an exercise in Allen B. Downey's excellent book Think Python (2nd edition). It is a beginners' book, but well worth a read, even by old hands. You can buy it from the usual places, or download a free electronic copy from his website.

---

Published 5 Sep 2021