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.)
Some Thoughts re: Finding adjacent words | Comment 9 of 11 |
(In reply to Finding adjacent words by Bruce)

Bruce,

This is a useful footnote, and makes much sense, provided we have a sorted list of adjacent words. (You loosely answered my earlier question regarding what one might do in preprocessing, and I take for granted that we would have sorted all this ahead of time.)
_________________

As for the "double-headed" algorithm you describe, I'm not certain that I understand what you're suggesting. Namely, it doesn't seem to reduce the BIG-O speed, and now you not only have to search for adjacent words in two trees... you must do a search (log n, I'm sure) in the other tree to see if it exists there.

So... I see the benefit of doing more in memory, reducing disk access in a practical sense, but I don't see how this speeds the algorithm up (from an algorithmic point of view).

Perhaps you can clarify for me.

Thanks,

--- SK
  Posted by SilverKnight on 2003-09-26 11:43:00

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