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)


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


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:

    FILE  fWords;

    fWords.Open("WORDS"  +  CurrentWord.Length  +  ".TXT")

    while  not  fWords.EOF()  //  EOF  =  end  of  file
        WORD  Word  =  fWords.GetNextWord()

        If  (  IsAdjacent(InitialWord,  Word)  ==  TRUE)  Then
    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  (TRUE)
Edited on September 24, 2003, 4:59 pm
  Posted by SilverKnight on 2003-09-24 16:06:39

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

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

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