Word Ladder

Overview:

stone
Atone
aLone
Clone
clonS
cOons
coNns
conEs
coneY
Money

Word ladders were invented in 1878 by Lewis Carroll, the author of Alice in Wonderland. A word ladder is a sequence of words that starts at one word (the starting word) and ends at another word (the ending word). Each word in the ladder differs from the preceding word by exactly one letter. Each word in the ladder must be a valid English word, and all words in the ladder must have the same length. For example, to turn stone into money, one possible ladder is given on the left.

Many ladder puzzles have more than one possible solution. Another path from stone to money is:

stone  stoRe  sHore  Chore  choKe  chokY  cOoky  cooEy  coNey  Money

Your program must determine the shortest word ladder between two specified words.

Preparation

Create a PyCharm project for this assignment.
Into this project, copy the following files:

stack.py - this file contains an implementation of a Stack data structure similar to the one in the text book. You can import the Stack class into your word ladder program using the directive from stack import Stack
word_ladder.py - this file contains stubs of some functions that provide a rough outline for you to follow as you develop your code. Add other functions to this file as needed.

To the project, add a file named my_queue.py that contains an implementation of a Queue data structure similar to the one in the text book. You can import the Queue class into your word ladder program using the directive from my_queue import Queue
Copy the time_this.py file from Canvas to the project. You will be using this code to time your word ladder searches. You can import this into your word ladder program using the directive from time_this import time_this
Within the project, create a resources folder and download these two files, dictionary.txt and input.txt, to this folder. Within your word ladder program, you can refer to these files using the path name "resources/dictionary.txt" and "resources/input.txt", respectively.
Here is a small version of the dictionary file that only contains 10 words. You may want to use this small file while you are developing your program and switch to the big file after you are satisfied that your program works correctly.

Algorithm outline

Your program reads the allowed words (words that can appear in a word ladder) from dictionary.txt and stores them in a Python dictionary. The file contains exactly one word per line. Only words that appear in the dictionary can be used to construct word ladders.

For each pair of words in the file input.txt, your program reads the word pair, and attempts to build word ladders between the starting and ending words, in the manner described below.

The algorithm that you will (must) implement in the function find_word_ladder involves stacks and queues and works as described below. To receive credit, your implementation must follow the algorithm described below. All interactions with a stack or queue must occur through the methods provided by the corresponding class, i.e. push, pop, peek for Stack, and enqueue, dequeue for Queue.

Create a queue

Create a stack

Push the starting word onto the stack. The stack now has one word in it.

Enqueue this stack with one word into the queue. The queue now has a single stack in it.

Repeat the following steps as long as the queue is not empty

Dequeue the first item (which is a stack) from the queue, peek at its top word and compare it with the ending word.

If they are equal, you are done - this stack contains the ladder. Return it

Otherwise, find all the words in the dictionary one letter different from the top word.

For each of these new words,

create a deep copy of the existing stack. See the clone method defined in the Stack class. See this for an explanation of copy vs. deep copy.

push that word onto the stack.

Enqueue the newly created stack to the queue. Notice that as the algorithm continues to execute, the word ladders represented by the stacks will continue to grow, one word at a time.

Your search ends:
when you find that the top word of some stack is the ending word -- the stack represents the word ladder in this case, OR
when the queue is empty. No more word stacks exist that need to be explored. No ladder exists between the specified words in this case.

A few things to remember:
You have to keep track of words that are already used (i.e. a part of some stack), and not use them a second time! Otherwise an infinite loop occurs. For example, if a stack contains the words beat, boat, when you search for words one letter different from boat, it should not include the word beat. Otherwise, your search will go in circles: beat,boat,beat,boat,beat,boat......

Only words that appear in the dictionary are allowed in a ladder.

Example

Say the starting word is smart and the ending word is scary. You start (Step 3 above) by pushing smart onto a stack and enqueueing this stack into the queue, which now looks like this.

---------
| smart | 
---------

Your algorithm dequeues the first (leftmost in the diagram above) word-stack and examines the top word, smart. Since this is not the end word, it finds the five words (scart, start, swart, smalt, smarm) in the dictionary one letter different from smart, pushes them onto clones of the original stack, and enqueues the stacks in the queue. The queue of stacks looks as shown below and contains five stacks, each with two words--the starting word and a word that is different by one letter.

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

Your algorithm dequeues the first (leftmost in the diagram above) word-stack and examines the top word, scart. Since this is not the end word, it finds the seven words in the dictionary one letter different from the top word scart, and pushes them onto clones of the original stack. This creates seven new stacks, each of which is a clone of the dequeued stack and contains the next word, in addition to the previous two words,

---------------------------------------------------------
| 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 - the 4 remaining two-word stacks, followed by the 7 new three-word stacks, highlighted in red above.

Your algorithm then dequeues the next word-stack and examines the top word, start. Since this is not the end word, it finds all words one letter different from the top word start. This creates four new stacks each of which is a deep copy of the dequeued stack and contains the next word, in addition to the previous two words.

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

Add them to the queue. The queue size now is 14 - the 3 remaining two-word stacks, followed by the existing 7 three-word stacks, followed by the 4 new three-word stacks.

Repeat the procedure until either you find the ending word at the top of some word stack, or find that the queue is empty which indicates that such a word ladder does not exist and therefore cannot be constructed. Make sure you do not run into an infinite loop!

Output

When executed,

your program reads each word pair in the file input.txt and outputs to the console the shortest word ladder from the start word to the end word for each word pair.

There may be more than one shortest ladder between the start word and the end word. For example, [part, port, tort] and [part, tart, tort] are two different word ladders between the words part and tort, both of length 3. Your program may output any one of these ladders. Therefore, the exact words in the word ladders found by your program may be different from the words shown in the expected output, but for any word pair, the ladders must be of the same length as shown in the output.
The first word of each ladder must be the start word, and the last word must be the end word.
Every word in the ladder must be a word that appears in the dictionary. This includes the given start and end words--if the start or end words are not in the dictionary, you should print "There is no word ladder between ..."
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 ..."

Your program also prints the time taken to find each word ladder, the length of the word ladder, and the words in the ladder, maximum length of the queue during that search, as shown in this example of the expected output. Use the time_this function presented in class for timing your searches.

Submission instructions

Make sure that your Python code is well commented and follows PEP-8 Python coding style conventions.
Upload your PyCharm Project (the entire project) as a zip file. Make sure that the project contains all the code and data in the right locations and that your code works, as described above under output. If your code crashes when I execute it, I cannot grade it and you will get a zero.

Grading

Follow the coding conventions described here. The guidelines for grading can be found here.
Here is the project-specific grading scheme:

Code correctly implements the algorithm outlined above (Yes/No) - 32 points

For each of the 17 word pairs in input.txt, code correctly finds and prints the corresponding shortest word ladder and related data in the manner shown in output.txt - 4 points each (Yes/No)