Click here to Skip to main content
15,867,453 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
I was given this problem that must be solved using recursion.

The word ladder game was invented by Lewis Carroll in 1877. The idea is
to begin with a start word and change one letter at a time until arriving at
an end word. Each word along the way must be an English word.
For example, starting from FISH you can make a word ladder to MAST
through the following ladder:
FISH, WISH, WASH, MASH, MAST
Write a program that uses recursion to find the word ladder given a start
word and an end word, or determines if no word ladder exists.

What I have tried:

Here is my code:

C++
#include<fstream>
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
using namespace std;

bool possible_bridge(string a, string b)//determine if a bridge can be formed between two strings
{
	if (a.length()!=b.length())
	{
		return false;
	}
	bool difference=false;
	for (int i=0;i<a.length();i++)
	{
		if ((a[i]!=b[i])&&(!difference))
		{
			difference=true;
		}
		else if ((a[i]!=b[i])&&(difference))
		{
			return false;
		}
	}
	return true;
}
bool isRepeat(vector<string>& no_repeat,string word)//determine if there is already an indentical string in the vector
{
	for (int i=0;i<no_repeat.size();i++)
	{
		if (no_repeat[i]==word)
		{
			return true;
		}
	}
	return false;
}
void word_bridge(string last,vector<string>bridge[],bool& found,int size)
{
	ifstream fin;
	int count[size];
	for (int i=0;i<size;i++)
	{
		count[i]=0;
	}
	for (int i=0;i<size;i++)
	{
		string word;
		fin.open("text.dat");
		while (fin>>word)
		{
			if ((possible_bridge(word,bridge[i][bridge[i].size()-1]))&&(!isRepeat(bridge[i],word)))
			{
				count[i]++;
			}
		}
		fin.close();
	}
	int total=0;
	for (int i=0;i<size;i++)
	{
		total+=count[i];
	}
	if (total==0)
	{
		cout<<"no ladder available\n";
		return;
	}
	int n(0),i(0);
	vector<string>temp[total];
	for (int k=0;k<total;k++)
	{
		temp[k]=bridge[i];
		n++;
		if (n==count[i])
		{
			i++;
			n=0;
		}
	}
	n=0;
	i=0;
	string word;
	fin.open("text.dat");
	for (int k=0;k<total;k++)
	{
		do
		{
			fin>>word;
		} while (!((possible_bridge(word,temp[k][temp[k].size()-1]))&&(!isRepeat(temp[k],word))));
		temp[k].push_back(word);
		n++;
		if (n==count[i])
		{
			i++;
			n=0;
			fin.close();
			fin.open("text.dat");
		}
	}
	if (fin.is_open())
	{
		fin.close();
	}
	for (int i=0;i<total;i++)
	{
		if (temp[i][temp[i].size()-1]==last)
		{
			for (int k=0;k<temp[i].size();k++)
			{
				found=true;
				cout<<temp[i][k]<<" ";
			}
			return;
		}
	}
	if (!found)
	{
		word_bridge(last,temp,found,total);
	}
}

int main()
{
	vector<string>bridge[1];
	bridge[0].push_back("ade");
	bool found=false;
	word_bridge("bqe",bridge,found,1);
}



I have tested the functions and they work well except for the recursion part of the word_bridge function. When I added a simple output line cout<<"123" right before the recursive part and ran the program, the program output 123 but didn't terminate or output anything else.
Posted
Updated 11-Aug-16 10:08am
v2
Comments
jeron1 11-Aug-16 11:59am    
You've stated no question.

Development comes in four parts: Design, Code, Test, and Debug.
You've done the first three, and now it's time for the fun one: Debugging.

Why doesn't it work? I don't know, because you haven't told me how you know it doesn't - you haven't told me what you did in order to test it, or what results you got. And these are important: they tell you, the coder, what is wrong.

So start by looking at what you did: what did you enter, and what happened as a result. Any error messages are important. And output is important. How do the result relate to what you input and what you expected? When you've had a good think about about, it's time to bring out the debugger, and start working out why you get the results you do.
Put a breakpoint on the line
C++
bridge[0].push_back("ade");
And run your app in the debugger.
When it hits the breakpoint, it will stop, and let you take over. You can step over lines, step into functions, and look at (or change) the content of variables. So look at each line, and work out exactly what should happen when it runs. Then execute the line, and look at what did happen. Is it what you expected? If so, continue for the next line. If not, why not? What did it do? Why didn't it do what you expected?

This is a skill - and a very valuable one in real life as well - but the only way to develop it is to use it: the more you use it the better you get! And it's a lot easier to learn and develop the skill on a little program like this, rather than a 100,000 line behemoth mostly written by a different developer!

So give it a try, and see what you can find out - it can be frustrating, but it's the real fun part of development when you find out what the problem is!
 
Share this answer
 
I agree with OrifinalGriff, You should learn to use the debugger as soon as possible. Rather than guessing what your code is doing, It is time to see your code executing and ensuring that it does what you expect.

The debugger allow you to follow the execution line by line, inspect variables and you will see that there is a point where it stop doing what you expect.
Debugger - Wikipedia, the free encyclopedia[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]

The debugger is here to show you what your code is doing and your task is to compare with what it should do.
When the code don't do what is expected, you are close to a bug.

You have a bug here:
C++
int count[size];
for (int i=0;i<size;i++)>
{
    count[i]=0;
}

This code works perfectly if size is known at compile time.
When size change at runtime, you need a pointer and you have to manually allocate and free memory.
malloc - C++ Reference[^]
std::malloc - cppreference.com[^]
This bug is nasty because your code is trashing the stack and every time you call a function, the stack is trashing your variable.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900