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.)
re: Defining | Comment 4 of 11 |
(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
  Posted by SilverKnight on 2003-09-24 16:06:39

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (6)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
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