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.

(I assume it is possible for a program to consider one word of length L to be greater than or less than another word of length L, based on the normal ordering of letters from left to right:
e.g. hard < sard, sard < sord, sold < sord,
sold < solo)

This pseudocoded Al-Gore-ithm should do the job.

*
* Program initializations
*
M001: Read the input word.
M002: Scan the input word and determine its length. Set variable L to this value.
M003: Dynamically allocate and move blanks to workareas WORDLADDER (length L*(L+1)), PRIORWORD, LETTERORDER, (both of length L), and ORDERTABLE (length = L*(L!))
M004: Build the contents of ORDERTABLE (L! elements of length L each) such that ORDERTABLE contains every possible ordering of the integers 1 through L.
M005: Set J=1
M006: Move the input word to the leftmost L positions in WORDLADDER.
*
* Find all the word ladders for a
* particular ordering of integers 1-L.
* (E.g. for the word hard and the
* ordering 3124, find all the word ladders
* formed by changing the third letter, then
* the first letter, then the second letter,
* and then the fourth letter:
* (hard, hand, land, lend, lens), etc......
*
M007: Move the Jth element of ORDERTABLE to LETTERORDER.
M008: Set N to 1.
M009: Perform subroutine S001 thru S015.
M010: If position (L+1) in WORDLADDER is blank, go to M016
M011: Edit WORDLADDER into readable form, and PRINT it.
M012: Move rightmost L positions of WORDLADDER to PRIORWORD
M013: Blank out rightmost L positions of WORDLADDER
M014: Set N=L
M015: Go to M009
*
* Go to the next ordering.
*
M016: If J=L!, exit the program.
M017: Set J=J+1
M018: Go to M007.

S001: Set variable K to the Nth position of LETTERORDER.
S002: Read the first dictionary word of length L that is greater than PRIORWORD, but is exactly the same as the word in the rightmost nonblank L positions of WORDLADDER, except for the Kth letter.
S003: If end-of-dictionary, go to S009
S004: Move the dictionary word to the first leftmost blank L positions of WORDLADDER.
S005: Move spaces to PRIORWORD.
S006: Add 1 to N
S007: If N>L, go to S009.
S008: Go to S001.
S009: If the last position in WORDLADDER is nonblank, go to S015.
S010: If position (L+1) in WORDLADDER is blank, go to S015.
S011: Move the rightmost nonblank L positions of WORDLADDER to PRIORWORD.
S012: Move spaces to the rightmost nonblank L positions of WORDLADDER.
S013: Set N down by 1.
S014: Go to S001.
S015: Exit this subroutine.

I believe this program would produce the following results for input word "hard":

(hard bard bird bind bine)
(hard bard bird bind bins)
(hard bard bird bind bint)
(hard bard burd bund bung)
(hard bard burd bund bunk)
(hard bard burd bund bunn)
(hard bard burd bund buns)
(hard bard burd bund bunt)
(hard card cord cold cola)
(hard card cord cold cole)
(hard card cord cold cols)
(hard card cord cold colt)
(hard card cord cold coly)
(hard card curd cued cues)
(hard fard ford fold folk)
(hard fard ford fond fons)
(hard fard ford fond font)
(hard fard ford food fool)
(hard fard ford food foot)
(hard lard lord load loaf)
(hard lard lord load loam)
(hard lard lord load loan)
(hard lard lord loud loup)
(hard lard lord loud lour)
(hard lard lord loud lout)
(hard nard nerd need neem)
(hard nard nerd need neep)
(hard sard sord sold sola)
(hard sard sord sold sole)
(hard sard sord sold soli)
(hard sard sord sold solo)
(hard sard sord sold sols)
(hard sard surd sudd suds)
(hard sard surd sued suer)
(hard sard surd sued sues)
(hard sard surd sued suet)
(hard ward word wold wolf)
(hard ward word wood woof)
(hard ward word wood wool)
(hard ward word wood woos)
.....ETC.....
.....ETC.....
.....ETC.....
(hard hart hast hist cist)
(hard hart hast hist fist)
(hard hart hast hist gist)
(hard hart hast hist kist)
(hard hart hast hist list)
(hard hart hast hist mist)
(hard hart hast hist wist)
(hard hart hast host cost)
(hard hart hast host dost)
(hard hart hast host lost)
(hard hart hast host most)
(hard hart hast host post)
(hard hart hast host tost)
(hard hart hast host wost)













Edited on January 22, 2004, 12:55 pm

Posted by Penny on 2004-01-16 03:30:18