Write a word ladder program.

Read this wikipedia article that describes what a word ladder is: Word Ladder

Your program must use a list to store the dictionary of words and then use stacks of strings and a queue of these stacks to solve for and output the word ladder. You are required to use the Standard Template Library (STL) list, stack, and queue.

You must implement the following class. You may not add any data members or add any public member functions to this class. You will most likely want to add private helper functions though.

class WordLadder { private: list dict; //list of possible words in ladder public: /* Passes in the name of a file that contains a dictionary of 5-letter words. Fills the list (dict) with the words within this file. If the file does not open for any reason or if any word within the file does not have exactly 5 characters, this function should output an error message and return. */ WordLadder(const string &); /* Passes in two 5-letter words and the name of an output file. Outputs to this file a word ladder that starts from the first word passed in and ends with the second word passed in. If either word passed in does not exist in the dictionary (dict), this function should output an error message and return. Otherwise, this function outputs to the file the word ladder it finds or outputs to the file, the message, "No Word Ladder Found." */ void outputLadder(const string &start, const string &end, const string &outputFile); }; 

Algorithm for finding a word ladder

• create a Stack containing just the first word in the ladder
• enqueue this Stack on to a Queue of Stacks
• while this Queue of Stacks is not empty
  • get the word on top of the front Stack of this Queue
  • for each word in the dictionary
    • if the word is off by just one letter from the top word
      • create a new Stack that is a copy of the front Stack and push on this off-by-one word found
      • if this off-by-one word is the end word of the ladder, this new Stack contains the entire word ladder. You are done!
      • otherwise, enqueue this new Stack and remove this word from the dictionary
  • dequeue this front stack
• if the Queue is empty and you didn't find the word ladder, a word ladder does not exist for these 2 words

Testing your WordLadder class

For testing you can download a dictionary of 5-letter words from my CS 14 public workspace: https://ide.c9.io/krism/cs14

You can also find in that workspace a main function that can be used to test your WordLadder class.