Write an algorithm to create word ladders such as any of the following:
hard bard bird bind bins
hard ward word wood wool
hard herd head dead dean
hard hand band bind bins
hard harp hasp wasp wisp

where a word is given which must be transformed into some other word (not specified in advance) with the same number of letters, but each letter position changed from its original value, in as many steps as there are letters in the word, each step also being a valid word. This is similar to the various Word Meld puzzles on this site, except there are as many steps as there are letters in the word and each letter is changed, with each letter position being changed exactly once.

Input consists of the starting word only. It is assumed that the number of steps will be the same as the number of letters in the word. 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. The program will find all the eligible word ladders given the words in the list.

The program will, of course, terminate without finding any results if in fact a word ladder cannot be constructed starting with the input word.

(In reply to I think this pseudocode will do it by Penny)

The only differences I can see between Penny's solution and the official one are that:

1. The official one does not store an array of all the possible orders of letter positions to be changed, but rather generates each new one as the processing goes along.

2. The official solution tries each of the other 25 letters at each position, then does a binary search on the word list, rather than the sequential search for a word larger than PRIORWORD. I'm not sure the "larger" part would allow a transition from, say "ford" to "food", unless there's something I missed seeing about an initialization of PRIORWORD. Oh, yes, I see it at S0005. The only disadvantage is the slowness of a sequential search.

Other than that it's basically the same--just differences between a long string vs. an array of strings and things like that.
Edited on January 23, 2004, 2:10 pm

Posted by Charlie on 2004-01-23 14:07:48