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

Home > Algorithms
Word Ladders (Posted on 2003-09-24) Difficulty: 4 of 5
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 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:

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
  Posted by SilverKnight on 2003-09-24 14:52:49
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2020 by Animus Pactum Consulting. All rights reserved. Privacy Information