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.
(I will appreciate if Levik will ensure that the PRE-codes are being used here.)
Here's some C++/Pseudo code that I think is easy to follow... feel free to ask questions.
I'll take for granted that we have the
trivial function and class:
FindAdjacentWords(GivenWord)
--which returns a collection containing all words that have the same number of letters and differs by only one letter. If this requires disk access (also trivial), so be it.
A
tree collection that allows
n branches at each node, and provides a
GetRootPathMembers method to return a collection of objects from the current node to the root ordered from the root to the current node.
_______________________
CalculateWordLadder(StartWord, EndWord, MaxSteps)
{
CurrentWord = ""
WordLadderTree.AddNode(NULL,StartWord) // add start as the root of the tree
Repeat FOREVER
{
For Each Element X in WordLadderTree at Maximum TreeDepth
{
BOOLEAN NewWordsFound = FALSE
WordCollection = FindAdjacentWords(Element)
For Each Element Y in WordCollection
{
If ( Y NOT IN GetRootPathMembers(X) ) Then
// we don't want to cycle nor do we want to include
// a word that we've already found in another branch
{
NewWordsFound = TRUE
WordLadderTree.AddNode(X,Y) // add the new word to the tree; child of the current element X
If ( Y == EndWord)
{
PRINT "Problem solved:"
PRINT GetRootPathMembers(Y)
END PROGRAM
}
}
}
If (NewWordsFound == FALSE ) Then
{
PRINT "Search ended, no solution found"
END PROGRAM
}
If (WordLadderTree.MaximumTreeDepth = MaxSteps) Then
{
PRINT "Search ended, maxsteps reached"
END PROGRAM
}
}
}
}
Edited on September 24, 2003, 3:15 pm
solution
