This problem is really a computer science problem in disguise, so this solution necessarily assumes some basic computer science knowledge. In particular, one must know what the breadth-first-search algorithm is. This algorithm is one that finds the set of all nodes reachable from some node x in a graph. It also outputs the shortest distance from x to those nodes. The implementation of it can easily be found by an Internet search.
Construct a graph where each node is a word and where an edge connects any two words that differ in exactly one letter position. Find the diameter of this graph by solving the all-pairs shortest-path problem. (This problem is to find the shortest path from s to t for all pairs (s,t) of nodes in a graph).
Solving the all-pairs shortest-path problem can be done as follows:
1. Pick a node n and perform a breadth-first search from it to find the distance of the node furthest from n.
2. Repeat for every node in the graph, and output the largest distance found.
A smart (and necessary) optimization is to first partition the set of words into equivalence classes, where word1 is equivalent to word2 if there exists a path from word1 to word2. This can be done by doing a breadth-first-search from a node to find the equivalence class containing that node, and then repeating on the remaining set of unclassified nodes until all nodes have been classified.
Then all-pairs shortest-path only need be run on each equivalence class.
When using the Scrabble dictionary (which only contains words of length 8 or less), the answer turns out to be the two words "effaces" and "cabaret":
[effaces, enfaces, enlaces, unlaces, unlades,
unladed, unfaded, unfaked, uncaked, uncakes,
uncases, uneases, ureases, creases, cresses,
crosses, crosser, crasser, crasher, brasher,
brasier, brakier, beakier, peakier, peckier,
pickier, dickier, dickies, hickies, hackies,
hackles, heckles, deckles, deciles, defiles,
defiled, deviled, develed, reveled, raveled,
ravened, havened, havered, wavered, watered,
catered, capered, tapered, tabered, tabored,
taboret, tabaret, cabaret]
|
