Super Doublets: more word ladders with Julia

Nov 5, 2022 programming julia
Share on:

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:

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

evading, foliage, irksome, thalami, discrediting, embodiment, absorption, persisted, supplementing, dispatch

We do see some reductions of ladder lengths. Getting "scent" from "roses" took 11 words, but in this new version it's quicker:

roses, roes, res, rest, rent, cent, scent

And the longest word ladder has 42 words:

hammerings, hammering, hampering, pampering, papering, capering, catering, cantering, bantering, battering, bettering, fettering, festering, pestering, petering, peering, peeing, pieing, piing, ping, pine, pane, pale, paled, pealed, peeled, peered, petered, pestered, festered, fettered, bettered, battered, bantered, cantered, catered, capered, tapered, tampered, hampered, hammered, yammered

Interestingly, we might expect that most words are connected, but in fact there are 25337 connected components. One of them consists of

metabolise, metabolised, metabolises, metabolism, metabolisms, metabolite, metabolites, metabolize, metabolized, metabolizes

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:

complete, completed, completes, compose, composed, composes, compute, computed, computer, computers, computes, comfort, compete, competed, competes, composer, composers, comforted, comforts, commune, communed, communes, commute, commuted, commuter, commuters, commutes, completer, completest, complexes, compost, composted, composts, comforter, comforters, complected, comport, comported, comports, compote, compotes