Super Doublets: more word ladders with Julia
Apparently there's a version of Doublets (see previous post) which allows you to add or delete a letter each turn. Thus we can go from WHEAT to BREAD as
WHEAT, HEAT, HEAD, READ, BREAD
which is shorter than the ladder given in that previous post. However, we can easily adjust the material from that post to implement this new version. There are two major differences:
- We have to use all the words in the list, since with additions and deletions, all words are potential elements in a ladder. That is, we can't restrict words by length.
- The distance between words is no long the Hamming distance. For this version we need the Levenshtein distance. This counts the number of additions, deletions, and replacements, to go from one string to another. The new version of Doublets thus requires that the Levenshtein distance between two words is 1.
Other than that it's all the same as previously. Starting with the list
medium.wds, constructing the graph (which has 59577 vertices and 78888 edges),
and determining the eccentricities of the largest connected component now take a
longer time: Constructing the graph took over 24 minutes, and the eccentricities
took a bit under 4 1/2 minutes on my machine. The largest
connected component has 23801 words; the next largest has 41 words (see below).
There are also 14688 aloof words; here's a random 10 of them:
We do see some reductions of ladder lengths. Getting "scent" from "roses" took 11 words, but in this new version it's quicker:
And the longest word ladder has 42 words:
Interestingly, we might expect that most words are connected, but in fact there are 25337 connected components. One of them consists of
Many of the connected components seem to be like this: all based around one particular word with its various grammatical forms. The two second biggest connected component contain 41 words each. Here's one: