The word-chain game

Richard Suchenwirth - Continuing Graph theory in Tcl, here comes a different application for graphs, that can be turned into a game (stimulated by a remark by Donal Fellows) and thus has a little practical application.

Let a word chain be a list of e.g. English words of equal length, where each two neighboring words differ in only one letter. Examples:

 son - sun - gun
 cat - hat - hot - hog - dog

These word chains are simple graphs, even trees as they contain no cycle. Some may be completed to a cycle, but that indicates it was not the shortest path:

 hat - hit - hot   #could have been shortened to: hat - hot  

In the proposed game, the player has to find a (or a shortest) word-chain for two random words over a given vocabulary. This amounts to finding a path in a graph whose edges need not be literally enumerated, but can be retrieved with a function (as Donal mentioned) like this:}

 proc neighbors {word wordlist} {
    set res {}
    foreach w $wordlist {lawn
        if {[wordDistance $w $word]==1} {lappend res $w}
    set res
 proc wordDistance {word1 word2} {
   set distance 0
   foreach c1 [split $word1 ""] c2 [split $word2 ""] {
        if {$c1!=$c2} {incr distance}
   set distance
 % neighbors cat {car cat man cot con hat fat fan}
 car cot hat fat

More to come...

From the Tcl chatroom on 4 Dec 2001:

suchenwi: The procedure is simple, but I got stuck with the user interface: buttons for the words so far that bring up a pop-up menu to choose where to continue?

bbh: are you generating the words on the fly ? or is there a predetermined list and you just need to use your neighbors function to find the closest ones andthen provide a picker for those?

* clock : 1007456401 : Dec 4,2001 Tuesday 9am GMT

suchenwi: My idea was a pre-set list of meaningful English three-letter words. Yes, and then pick from the legal alternatives.

bbh: UI wise, probably a combo box with all the "neighbors" of start word when next word is picked, a new combo box with its' neighbors, etc. If a change is made in any older combobox - remaining are removed and back up with a new list of neighbors

suchenwi: Right. If I already had the graph layouter I'm dreaming of, one could also visualize it like a maze.

bbh: alternately - just a single listbox for selecting - once a word is selected ti is added to a text box that contains the current chain & the listbox is filled with next list - clciking on a word in the chain can then back up to that point. (Or alternately start a new branch at that point so user can see the old path he already tried ... or a canvas instead of a text box so you can connect the words by lines or just all the words scattered about a canvas and as each word is chosen all it's neighbors have thin lines & highlights (kinda like the wonder wall games show)

suchenwi: .. if they fit the (wordDistance=1) condition...

bbh: yes, neighbors in word sense not necessarily in x,y location sense

suchenwi: The task of graph layout would be to scatter the words so "word" neighbors are also geometrically close together.

bbh: that would be neat