Lab 1570 - Word Ladder

Description

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

There are two queues in this program. The WordList and the WordPaths. The WordList is an instance of the AP CS ListQueue class. It keeps track of the word objects, each containing a word and the complete path it took to get to that word. The path stored with each word on the WordList is the WordPath, and it uses a LinkedList to store the path.

The dictionary should be an ArrayList at this point in the course. For the initial implementation, use a simple linear search to see if a word is in the dictionary. Extension 1: Write a binary search that works on the dictionary and compare speed to the linear search. Extension 2: use a HashMap as a dictionary; key is the word and value is a boolean that records if the word has been used.

Load the word list of 5 letter words from knuth.dat Ask user for start and end word (must both be 5 letter words and at least the starting word must be in the dictionary). Put that word in an object containing the word and the path to that word. Put that object on the queue. While there are word objects on the queue:

dequeue the first word object and grab the word,
find all words in the dictionary that are one off from that one that have not already been used.
enqueue each new one-off word onto the queue along with path that gets to them.
if we find our word would be enqueued, we are done.
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. As words are used, they should be removed from the dictionary so there is no possibility of looping.

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

This project was developed in response to an idea by Owen Astrachan as used in his CPS100 class, Fall 1998 as Assignment 7.

Assignment

Use appropriate OOP techniques for the project. You will create several source files:

Files to Create
TestWordLadder.java	creates a WordLadder object; invokes showPath method.
WordLadder.java	a constructor and a single method: showPath
Dictionary.java	loads and accesses a dictionary of five letter words.
WordObj.java	defines an object to hold a word and a path to the word.

You will also need these files:

Resource Files
knuth.dat	list of five letter words
EasyReader.java	for user input
Queue.java	Queue interface
ListQueue.java	Queue implementation

Return to CS Labs