Write an algorithm to solve word ladders such as
Word Meld 1 or
Word Meld 2. Input consists of the
starting and ending words and the maximum number of steps allowed. Available are files containing lists of
words of any given length; call one such file, say WORDS5.TXT containing a list of words of 5 letters each, and so on.
(In reply to
Defining by Gamer)
Gamer,
I assume you are referring to my assumption of FindAdjacentWords, and the notion of having a tree template class (or equivalent, which exists in most mature programming libraries).
If so, then you are arguing about a matter of degree....
Charlie didn't explicitly say I have a PRINT command, nor an END PROGRAM command, nor collection objects, nor iterators (to move through the collection, perhaps in order), nor loop control operators (REPEAT, FOR EACH).
I must assume a modicum of basic understanding and familiarity with a computer language, and Charlie asked for an algorithm. I trust that what I proposed is sufficiently clear to actually write code in a language of your choosing.
Again, feel free to ask questions if this is in any way unclear.
--- SK
P.S.
However, all that being said....
Tree is straightforward enough... (if you've taken a basic computer algorithms class).
The FindAdjacentWords function could be implemented algorithmically as follows:
FindAdjacentWords(InitialWord)
{
FILE fWords;
ORDEREDCOLLECTION RetVal
fWords.Open("WORDS" + CurrentWord.Length + ".TXT")
while not fWords.EOF() // EOF = end of file
{
WORD Word = fWords.GetNextWord()
If ( IsAdjacent(InitialWord, Word) == TRUE) Then
{
RetVal.AddMember(Word)
}
}
return (RetVal)
}
____________________
Helper Function
IsAdjacent(Word1, Word2)
{
INT cDifference=0
For Each Letter X in Word1
{
If (X is different than corresponding letter in Word2) Then
{
cDifference = cDifference + 1
if (cDifference == 2) then
{
return (FALSE)
}
}
}
if (cDifference == 0) then
{
return(FALSE)
}
return (TRUE)
}
Edited on September 24, 2003, 4:59 pm
re: Defining
