All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

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.

 See The Solution Submitted by Charlie Rating: 3.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution | Comment 2 of 11 |
(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.

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.

_______________________

{
CurrentWord  =  ""

Repeat  FOREVER
{
For  Each  Element  X  in  WordLadderTree  at  Maximum  TreeDepth
{
BOOLEAN  NewWordsFound  =  FALSE

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
If  (  Y  ==  EndWord)
{
PRINT  "Problem  solved:"
PRINT  GetRootPathMembers(Y)
END  PROGRAM
}
}
}

If  (NewWordsFound  ==  FALSE  )  Then
{
PRINT  "Search  ended,  no  solution  found"
END  PROGRAM
}

{
PRINT  "Search  ended,  maxsteps  reached"
END  PROGRAM
}
}
}
}
Edited on September 24, 2003, 3:15 pm
 Posted by SilverKnight on 2003-09-24 14:52:49

 Search: Search body:
Forums (0)