Q: Find the shortest word ladders stretching between the following pairs: hit - ace pig - sty four - five play - game green - grass wheat - bread order - chaos order - impel sixth - hubby speedy - comedy chasing - robbers effaces - cabaret griming - goblets vainest - injects vainest - infulae

A:

- Using every unabridged dictionary available, the best yet found are
- hit ait act ace pig peg seg sey sty four foud fond find fine five play blay bray bras baas bams gams game green grees greys grays grass wheat theat treat tread bread order older elder eider cider cides codes coles colls coals chals chaos order ormer armer ammer amper imper impel sixth sixty silty silly sally sably sabby nabby nubby hubby speedy speeds steeds steers sheers shyers sayers payers papers papery popery popely pomely comely comedy griming priming prising poising toising toiling coiling colling collins collies dollies doilies dailies bailies bailees bailers failers fablers gablers gabbers gibbers gibbets gobbets goblets chasing ceasing cessing messing massing masting marting martins martens martels cartels carpels carpers campers cambers combers cobbers combers robbers vainest fainest fairest sairest saidest saddest maddest middest mildest wildest wiliest winiest waniest caniest cantest contest confest confess confers conners canners fanners fawners pawners pawnees pawnces paunces jaunces jaunced jaunted saunted stunted stented stenned steined stained spained splined splines salines savines savings pavings parings earings enrings endings ondings ondines undines unlines unlives unwives unwires unwares unbares unbared unpared unpaged uncaged incaged incased incised incises incites indites indices indicts inducts indults insults insulas insulae infulae

This is not another travelling salesman - it is merely finding the diameter of connected components of that graph. The simple algorithm for this is to do one depth first search from each word, resulting in an O(n*m) worst case algorithm (where n is the number of words, and m is the number of arcs). In practice, it is actually somewhat better, since the graph breaks down into many connected components. However, the diameters (and solutions) depend on what dictionary is used. Here are the results from various dictionaries:

From /usr/dict/words (restricted to words all lower case alphabetical) (19,694 words): sixth - hubby (46 steps)

From the official scrabble players dictionary (94,276 words): effaces - cabaret (57 steps)

From the british official scrabble words (134,051 words): vainest - infulae (73 steps)

From webster's ninth new collegiate dictionary (abridged) (78, 167 words): griming - goblets (56 steps)

From all of the above, merged (180,676 words): vainest - injects (58 steps)

To see the effect the dictionary has on paths, here are the lengths of the shortest paths these pairs, and for the ones mentioned in previous posts, for each dictionary (a - means that there is no path using only words from that

- dictionary)
UDW OSPD OSW W9 ALL

hit - ace 5 3 3 5 3 pig - sty - 5 4 5 4

four - five 6 6 5 7 5 play - game 8 7 7 8 7

green - grass 13 4 4 7 4 wheat - bread 6 6 6 6 6 sixth - hubby 46 9 9 - 9

effaces - cabaret - 57 - - 33 vainest - infulae - - 73 - 52 griming - goblets - 22 19 56 15 vainest - injects - - 72 - 58