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 time a letter is changed, the resulting string of letters is a word.
For example, to turn stone into money, one possible ladder is (replace 't' by 'h', replace 'o' by 'i', etc.):
All of these words can be found in the Knuth file and in a dictionary. Your program will find the shortest word ladder between two words you enter when running the program. There may be more than one shortest ladder, your program must find one, but not all such ladders.
You are to write a program named doladder.cpp that uses a file of 5-letter words to find the shortest ladder from one word to another using a process outlined below. You must develop a class to do this, the class Ladder has been started for you, but you will need to add more member functions (both public and private).
Your program should:
The file knuth.dat has extraneous information in it. Ignore lines that begin with *, and only process the first 5 characters on other lines. Knuth asks that the file not be altered, hence these restrictions. Code to read this file is included as the member function LoadWords, already written for you to use.
The vector is diagrammed as:
A ladder is found by putting the starting word (or rather a pointer to the Wnode that the word is in) on the queue, then putting all words 1 letter away from this word on the queue, then putting all words 2 letters away on the queue, then all words 3 letters away, etc. As each word is taken off the queue, if the last (target) word is found the process can stop (there may be other words on the queue, but they'll be ignored). This process is guaranteed to find the shortest word ladder.
A Word w isn't actually stored on the queue, a pointer to a struct containing w is stored. The other field of the struct is a pointer to the word that is one letter away from w and that caused w to be put on the queue (the word's predecessor). For example, if w is bears, then pointers to structs containing dears, fears, gears, beard (and so on) are enqueued with each struct pointing to bears since this word preceeded the others and caused them to be enqueued. The first word doesn't have a predecessor. It's field cannot be NULL since this is used for another purpose (to tell if the word is already on the queue). An easy fix is to make the pointer self-referential, it points to the struct itself (and this will need to be checked when printing ladders).
This is diagrammed below
The first word (entered by the user) is looked up in the list of words, and a pointer to the struct containing the word is enqueued. (Extra: your program should be able to handle a first word even if the word is NOT in the list of words --- all other words in the ladder, except perhaps for the last, mut be in the list of words).
Put a pointer to the struct containing the first word onto the queue (it's a queue of Wnode pointers). Then repeat the dequeue/enqueue process below.
When the target word is derived, you'll need to print out the ladder from the first word to the target word. The prev pointer in the Wnode stores information that will allow the ladder to be recreated, you may need to use recursion or a vector since the ladder will be backwards (but should be printed properly). You could also search backwards, so to find a ladder from smart to brain search from brain to smart.
You'll probably find it useful to write a function IsOneApart that is used to determine if two strings are one letter apart. To do this, count the letters that are equal. If this is one less than the total number of letters in the words, the words are one apart. This function does NOT need to be a member function, it has two strings as parameters (const reference) and returns true if the strings are one letter apart. You can just define this function in ladder.cc and use it there.
You'll probably want debugging code/member functions to verify what's going on. If you build helping/debugging member functions into your class you'll save time in the long run since the member functions can be used to help debug code.
You may want to write a separate function to find a word in the vector of Wnode * read and constructed using the function Ladder::LoadWords. The function can be useful in debugging and developing the program.
You may find it useful to write a function that gives back all the words that are one letter apart from a given word. This list of words could be stored in a vector or the List class (random access isn't needed). It's not at all necessary to do this, and there is no grade improvement, but it may be helpful.