[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

----
!!!!!!
%|[Category Graph Theory]|[Category Games]|%
!!!!!!