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:
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.
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
The required SimpleList class methods are as follows.
The required MyStack class methods and data members are the following.
The MyQueue classshouldimplementaQueueADTthathasa SimpleList asitsunderlyingdatastructure. The followingmethodsarerequired. Youmayaddothermethodsifitdoesnotviolatethepropertiesorpoliciesforaqueue. Make use of whatever SimpleList member methods are available to you to implement the queues functionality.
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.
pop() on MyStack of size == 0
StackUnderflowException: pop() on MyStack of size == 0
push() on MyStack with CAPACITY == 8, size == 8
StackOverflowException: push() on MyStack with CAPACITY == 8, size == 8
pop() on MyQueue of size == 0 QueueUnderflowException: pop() on MyQueue of size == 0