A word ladder is when you move from one word to another with only changing 1 letter, so for example if you wanted to move from dog to bog, then you are just altering one letter (the “d” to a “b”), but if you are going from code -> data, then you would have to go through a couple of changes to get to the end word.
code -> cade -> cate -> date -> data
as you can tell we have only altered one letter at a time to move from one point of the linking words to another.
But if there is no linking words that we need to stop the program, because there is no link between the two words in that case and also if we have already used a word for a test sequence then do not use that word another for another sequence. (breath-first-searching).
So what we need to do is to have a way of finding another word with just changing one of the letters within the linking words, so, if we alter each letter within a word and make sure it is actually a word within a dictionary (and of course we have not already used that word before) then return that word as a new search pattern. This is what the below function (findNextWord) does, the parameters are word (the base word), dictionary (the dictionary to make sure that the new word is a word) and the alreadyUsed is the list of already used words.
string findNextWord(string word, Lexicon dictionary, Lexicon alreadyUsed) { string newWord; for (int i =0; i < word.length(); i++) { newWord = word; for (char ch = 'a'; ch <= 'z'; ch++) { // create a new word newWord = newWord.replace(i,1,1, ch); // make sure it is a valid word and also not already used if (dictionary.containsWord(newWord)) if (!alreadyUsed.containsWord(newWord)) return newWord; } } return ""; } |
Next since there could be allot of different words created from a 4 letter word, which in-turn would allow for different paths to take then what we need to do is to add the next word gained from the above function to the already path that we have taken and insert that into a queue (first in and first out), this queue will have all of the paths that we are testing in ordered of length to see if we are able to get to the end word. For example lets say with the code – data test, the queue may look like this after the first round, where the words are in a array
queue top
code -> cade
…
code -> node
code -> tode
…
queue bottom
so this means that we will always check to see if any of the 2 length linking paths can get to the end, and then process them in order and place the 3 length linking paths afterwards for example (we have take the code->cade from the top to process)
queue top
code -> node
code -> tode
… (other 2 length paths)
code -> cade -> cate
code -> cade -> kade
k. kade is a name, but could be in the dictionary, but you get the point, 2 length paths will be checked first and then 3 length paths until we reach the end word.
So this is how I done the it, added the start word to the queue, then looped, take off the next element, search for another word, if the next word is the end word stop, else add to the queue of searchable paths and also add to the list of already used words, below is the source code
void processMainGame(Lexicon dictionary, string startWord, string endWord) { Queue<Vector<string> > theFIFO; Lexicon alreadyUsed; string nextStr; theFIFO.clear(); Vector<string> addToQueue; addToQueue.add(startWord); // start the queue theFIFO.enqueue(addToQueue); while (true) { // build up a new list of items to search, or stop if empty if (theFIFO.size() ==0) { cout << "Nope nothing found! no ladder"<< endl; break; } Vector<string> newString = theFIFO.dequeue(); while (true) { // find the next word to use nextStr = findNextWord(newString[newString.size()-1], dictionary, alreadyUsed); // the end of the search if (nextStr == endWord) { cout << "FOUND ladder !!" << endl; foreach (string list in newString) { cout << list << " - "; } cout << endWord << endl << endl; return; } else if (nextStr != "") { // if there is another word to search with add to the end of the list Vector<string> addMore = newString; addMore.add(nextStr); theFIFO.enqueue(addMore); } // else if nothing left to search for stop!! else if (nextStr =="") break; alreadyUsed.add(nextStr); } } } |
I have attached the source code and also the PDF file of the assignment.