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 fatMore 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