Word Ladder

This part is a word ladder.

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.

5 thoughts on “Word Ladder”

  1. While checking this for single word substitution, Pope -> Pipe, I am getting “Nope nothing found! no ladder”. Is it in the specs of the program or is it a bug?

  2. I just briefly glanced at the code, but it seems like you pass the entire lexicon every time you’re calling the findNextWord function. If this is the case, I think your program would run much more efficiently if this were passed by reference…

    i.e.

    findNextWord(string word, Lexicon & dictionary, Lexicon & alreadyUsed);

    instead of

    findNextWord(string word, Lexicon dictionary, Lexicon alreadyUsed);

  3. Sorry I don’t know how to use these source codes. Do I need to include some namespaces/classes such as Lexicon??

Leave a Reply

Your email address will not be published. Required fields are marked *