15-200 Fall 2006

Homework Assignment 4

Word Ladder

Program Due: Thursday Oct. 05, 2006 at 11:59pm


Overview:

The aim of this assignment is to give you experience working with Stacks and Queues, as well as to strengthen your algorithm design skills.

You'll write a program to find word-ladders: connections from one word to another formed by changing one letter at a time with the constraint that each the resulting string of letters is a meaningful word. For example, to turn stone into money, one possible ladder is:

stone
Atone
aLone
Clone
clonS
cOons
coNns
conEs
coneY
Money

Obviously, there might be more than one word ladder. You just need to find one.


Objectives:


Instructions:

Your program will accept starting and ending words from the input file. It will then check if a word ladder exists between the two words using the words from a dictionary of English five-letter words.

There are several ways to solve this problem. One simple method involves using stacks and queues. The algorithm works as it follows

Store all of the words from the dictionary in a HashSet. Get the starting word and search through the dictionary to find all words that are one letter different. Create a stack for each of these words, containing the starting word (pushed first) and the word that is one letter different. Enqueue each of these stacks into a queue. This will create a queue of stacks! Then dequeue the first item (which is a stack) from the queue, look at its top word and compare it with the ending word. If they equal, you are done. The stack contains the ladder. Otherwise, you find all the words one letter different from it. For each of these new words create a copy of the stack and push each word onto the stack. Then enqueue stacks to the queue. And so on. You terminate the process when the queue is empty.

You have to keep the track of used words! Otherwise an infinite loop occurs.


Example:

The starting word is smart.

Find all the words one letter different from smart, push them into different stacks and store stacks in the queue. This table represents a queue of stacks.

-----------------------------------------
| scart | start | swart | smalt | smarm |
| smart | smart | smart | smart | smart |
-----------------------------------------

Now dequeue the front and find all words one letter different from the top word scart. This will spawn seven stacks:

---------------------------------------------------------
| scant | scatt | scare | scarf | scarp | scars | scary |
| scart | scart | scart | scart | scart | scart | scart |
| smart | smart | smart | smart | smart | smart | smart |
---------------------------------------------------------

which we enqueue to the queue. The queue size now is 11. Again dequeue the front and find all words one letter different from the top word start. This will spawn four stacks:

---------------------------------
| sturt | stare | stark | stars |
| start | start | start | swart |
| smart | smart | smart | smart |
---------------------------------

Add them to the queue. The queue size now is 14. Repeat the procedure until either you find the ending word or such a word ladder does not exist. Make sure you do not run into infinite loop.


Input file:

Each line of the input file contains exactly two words, starting and ending. For example
smart money
Each word will be in lower-cases letters. No upper-case letters, and no apostrophes. You may not assume that the start and end words will always appear in the dictionary.

The number of lines in the input file is not specified and may vary.


Output:

Your program must output to the console one word ladder from the start word to the end word. Every word in the ladder must be a word that appears in the dictionary. Remember that there may be more than one ladder between the start word and the end word. Your program may output any one of these ladders. The first output word must be the start word and the last output word must be the end word. If there is no way to make a ladder from the start word to the end word, your program must output "There is no word ladder between ..."

Notes:

  1. MyStack and MyQueue classes must be implemented via inheritance from the Java API's LinkedList class.
  2. Your MyStack and MyQueue classes must have exceptions at the appropriate places to match the Interfaces.
  3. Feel free to add any helper methods to the WordLadder class.
  4. For testing purposes we provide you with the input file and the expected output.

What You'll Need:

Create a private directory for your work, download the file lab.zip into it, and then unzip it. You should see the following files:


Grading:

Your assignment will be graded first by compiling and testing it. After that, we will read your code to determine whether requirements were satisfied, as well as judge the overall style of your code. Programs will be graded both on correctness as well as the style. Points will be deducted for poor design decisions and un-commented, or un- readable code as determined by your TA.

Here is the point breakdown:


Handing in your Solution:

FTP your implementation to /afs/andrew.cmu.edu/course/15/200/www/handin

DO NOT HANDIN dictionary.txt