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:
--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.
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
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:"
If (NewWordsFound == FALSE ) Then
PRINT "Search ended, no solution found"
If (WordLadderTree.MaximumTreeDepth = MaxSteps) Then
PRINT "Search ended, maxsteps reached"
Edited on September 24, 2003, 3:15 pm