previous page: 290 language/english/spelling/palindromes.p
page up: Puzzles FAQ
next page: 292 language/english/spelling/sets.of.words/nots.and.crosses.p

291 language/english/spelling/sets.of.words/ladder.p


This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

291 language/english/spelling/sets.of.words/ladder.p

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


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

                  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


Continue to:

previous page: 290 language/english/spelling/palindromes.p
page up: Puzzles FAQ
next page: 292 language/english/spelling/sets.of.words/nots.and.crosses.p