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":
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:
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.
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 |
Copyright © 2010 by Asylum Computer Services LLC | Return to CS Labs |