Word Ladder

A word ladder is a word game. The player is given a start word and an end word and must come up with a ladder of words where each word in the ladder is no more than one letter different than the word before it and the word after it. Here are a few word ladder examples:

• style stale state slate plate prate crate craze crazy
• brave braze blaze blame ame ams ats feats fears hears heart
• stack stark stars stirs sties stied steed stead steak

For this assignment, you will write a program to nd the shortest word ladder given a start word and an end word. To keep things simple, you will only be working with 5 letter words. The program will take as command line arguments thenameofthedictionaryle,thestartword,andtheendwordandoutputtostandardoutputthewordladderiffound. Theprogramoutputshouldmatchtheexamplesabove. Ifnowordladdercanbefoundsimplyoutputthestartandend word. You can download the dictionary of 5 letter words (words5.dict) we will use to grade your program from the Piazza course website. The following command must invoke your program.

% java WordLadder words5.dict start end

There are other algorithms to solve this problem including some that are much more efcient than the one we will be using. However, this assignment has been designed to give you practice combining implementations of a stack(MyStack), queue(MyQueue), andsimplelist (SimpleList), tosolvea problem. In a WordLadder class, implement the following algorithm.

AlgorithmFindWordLadder

create a stack of strings
push the start word on this stack
create a queue of stacks
enqueue this stack


while the queue is not empty
for each word in the dictionary
if a word is 1-letter different in any pos than top string of the front stack
if this word is the end word
// Done! The front stack plus this word is your word ladder.
output this word ladder
make a copy of the front stack
push the found word onto the copy
enqueue the copy.
dequeue front stack

SimpleListClass

The required SimpleList class methods are as follows.

• SimpleList(SimpleList rhs) - Constructor. Instantiates this list as a deep copy of rhs.
• Node previous(Node curr) - Returns the previous node for the specied node curr.
• Node next(Node curr) - Returns the next node for the specied node curr.
• char getAt(int index) - Returns the element at the specied position in this list. Index of rst element in list is 0.
• void setAt(int index, T value) -Replacestheelementatthespeciedpositioninthislistwiththe specied element.
• void insertAtPos(int index, T value) - Inserts a node with specied value at specied position in the list, shifting elements starting at i to the right, if needed.
• boolean removeAt(int index) - Removes the element at the specied position index in this list. Returns true if this list contained the specied element.
• int size() - Returns the number of items in the list.
• String toString() - Overrides the toString() method. Returns the formatted contents of this as a String. Allows for printing a MyList instance llist to standard output in following way, System.out.println("llist contents = " + llist);

MyStackClass

The required MyStack class methods and data members are the following.

• final private int CAPACITY - size of the stacks internal array
• private int t - index to the position of the top item in the stack
• private T[] data - array that holds contents of the stack
• MyStack() - Constructor. Initializes and allocates an empty stack.
• public boolean isEmpty() - Returns true if stack is empty.
• public int size() - Returns the size of the stack.
• public void push(T value)-Insertsvalueontothetopofthestack. ThrowsaStackOverflowException if the stack is full. This exception should be handled within this method.
• public void pop() - Removes the stacks top item. Throws a StackUnderException if the stack is empty. This exception should be handled within this method.
• public T top() -Returnsthestackstopitem. Throwsa StackUnderException ifthestackisempty. This exception should be handled within this method.

MyQueue

The MyQueue classshouldimplementaQueueADTthathasa SimpleList asitsunderlyingdatastructure. The followingmethodsarerequired. Youmayaddothermethodsifitdoesnotviolatethepropertiesorpoliciesforaqueue. Make use of whatever SimpleList member methods are available to you to implement the queues functionality.

• public boolean isEmpty() - Returns true if queue is empty.
• public void push(T value) - Inserts value onto the rear of the queue.
• public void pop() - Removes the queues front item. Throws a QueueUnderflowException if the queue is empty. This exception should be handled within this method.
• public T front() - Returns the front item in the queue. Throws a QueueUnderflowException if the queue is empty. This exception should be handled within this method.

Exceptions

The array-based MyStack class denes an insert (push) into a full stack or an access of (top) or removal from (pop) an empty stack to be an illegal operation. Prohibited operations for the linked list-based MyQueue class are an accessof(front)orremovalfrom(pop)anemptyqueue. Topreventthisanexceptionshouldbethrownandcaught within the appropriate member method for each class. You will implement your own user-dened exception classes. Deriveeachfrom java.lang RuntimeException. Placeeachexceptionclassinajavalewiththesamename as the class e.g., StackUnderflowException.java.

An example of the required console output for an exception throw and catch is listed below. Your programs outputmustmatchthis. TherstlineofoutputisproducedusingSystem.out. Thenext3linesareobtainedbyacall toprintStackTrace()onthethrownexceptionobject. Thelelinenumbers,e.g.,MyStack.java:29,areimplementationdependent. Foryourprogramsclasses,theywillbedifferent. ReadmoreaboutprintStackTrace() here.

• class StackUnderflowException - Must call MyStacks size() method to print the current size of the stack (shown as 0 below).

pop() on MyStack of size == 0
StackUnderflowException: pop() on MyStack of size == 0
at MyStack.pop(MyStack.java:29)
at Main.main(Main.java:39)

• class StackOverflowException - Must use the MyStacks internal data member CAPACITY to print the capacity of the stack (shown as 8 below). Must call MyStacks size() method to print the current size of the stack (shown as 8 below).

push() on MyStack with CAPACITY == 8, size == 8
StackOverflowException: push() on MyStack with CAPACITY == 8, size == 8
at MyStack.push(MyStack.java:18)
at Main.main(Main.java:24)

• class QueueUnderflowException -MustcallMyQueues size() methodtoprintthecurrentsizeof the queue (shown as 0 below).

pop() on MyQueue of size == 0 QueueUnderflowException: pop() on MyQueue of size == 0
at MyQueue.pop(MyQueue.java:45)
at Main.main(Main.java:22)