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.)
Question re(2): Defining - optimal solution? | Comment 5 of 11 |
(In reply to re: Defining by SilverKnight)

One who has much experience programming will (I hope) note that the algorithm I proposed is not optimal.

One possible efficiency issue is that FindAdjacentWords() searches through the whole collection of words each time it is called.

As a related question (which I won't answer since I'm posing it), how might you change the algorithm to speed up this function? (Speed measured in Big-O notation, of course. Yes, disk caching would speed things up... but it doesn't change the Big-O speed.)

How might you change the algorithm and what kind of preprocessing might you perform if you can set up any kind of collection/files before you begin your problem?

What other optimizations to my proposed algorithm might you suggest? (Preferably show enhancements that reduce the Big-O time.)

--- SK
  Posted by SilverKnight on 2003-09-25 06:24:46

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