This project attempts to find a word ladder between two user-selected words such that any single step changes only one letter. Example path from "money" to "greed":
money coney covey cover coyer foyer fryer freer freed greed

Algorithm

Load the word list of 5 letter words from knuth.dat Create a parallel apvector type bool that tracks words used. Ask for start and end word (must both be 5 letter words). Put that word in a structure and put that on the queue. While there are word structures on the queue

1. pop one off the top,
2. find all words one off from that one that have not already been used.
3. put new words on the end of the queue along with path that goes to them.
4. if we find our word, we are done.
5. if the queue gets exhausted, then there is no path from start to end.

When running, the queue has all words that are one away, followed by all words that are two away, then three away. The dequeue process removes the words as they are processed to look for other neighbors. Each element on the queue holds the word and the path to the word. The apvector has a bool-per-word to tell if any word has already been used; if so, it will not be put on the list again.

If a path is found, program announces success and displays the path. Otherwise, it indicates no path found.

This program was written in response to an idea by Owen Astrachan as used in his CPS100 class, Fall 1998 as Assignment 7. This version was written from scratch to use only ap classes (apvector and apqueue).

Implementation Notes:

1. There are several ways to look for words, such as linear search, binary search, etc. Several are included in this project. Not included, but worthwhile if you are in the AB mode, is to put the dictionary in a binary search tree.
2. Not posted to the site, but available, are word lists with three, four, five, six and seven letter words to extend the project. (These will show up again in the Boggle project when I write it.)

Files:

Download the files in either tar format or zip format.

I welcome your feedback, suggestions for improvement, or extensions to this project.