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.
(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
re(2): Defining - optimal solution?
