429 - Word Transformation

[Nazmul Quader Zinnuree]

Somebody help me know...
Every word is reachable from every other words ?? How ??
or, the pairs of words will always be of same length ??
bfs can be used to solve it ??
multiple input need to output "Case no" for every set of output ?? or just to take input for no of test cases...??

[Donotalo]

getting TLE in 429. my code is written in C++. can anyone give me large input and output for this problem?

200 words in the dictionary. besides, i'm using map to use this words. so it shud not take too much time. my program passes successfully sample test case. please help me!

[kolpobilashi]

i am getting WA for this problem
http://acm.uva.es/p/v4/429.html
anyone can help...??

Code: Select all

cut..

thanx in advance..

[Jan]

Replace the 'main' function...

Code: Select all

Removed...

Minor changes, so no big deal. Hope it helps.

[kolpobilashi]

That's it !!!
thanx Jan...

[kn]

I use binary search and 2D array to implement...
Y WA...?

Code: Select all

AC-ed
I read the question wrong again.. :( 

[ayeshapakhi]

hello...

i didn't see ur code...but ur program gives output for

Code: Select all

2

aaa
bbb
aab
aba
abb
a
b
*
aab bbb

abc
abd
aaa
aab
abb
*
abb aab
abc abd
aab bbb

Code: Select all

aab abb 1

abb aab 1
abb abb 0
aab abb 1

is it correct??

[kn]

hello...

i didn't see ur code...but ur program gives output for

Code: Select all

2

aaa
bbb
aab
aba
abb
a
b
*
aab bbb

abc
abd
aaa
aab
abb
*
abb aab
abc abd
aab bbb

Code: Select all

aab abb 1

abb aab 1
abb abb 0
aab abb 1

is it correct??

Well... in your test case, words are not in a lexicographical order, which is assumed in the specification of the problem
I did take this assumption in solving the problem



Sorry for that, I was wrong

[Jan]

Well... in your test case, words are not in a lexicographical order, which is assumed in the specification of the problem
I did take this assumption in solving the problem

Read the description again...

all words will be alphabetic and in lower case, and no word will be longer than ten characters. Words can appear in the dictionary in any order.

Words can appear in any order. So, your assumption is wrong. Hope it helps.

[kn]

Well... in your test case, words are not in a lexicographical order, which is assumed in the specification of the problem
I did take this assumption in solving the problem

Read the description again...

all words will be alphabetic and in lower case, and no word will be longer than ten characters. Words can appear in the dictionary in any order.

Words can appear in any order. So, your assumption is wrong. Hope it helps.

o...really...
how comes...thx Jan, I'm now trying
AC-ed...thx

[sapnil]

Hi i am trying with BFS,but WR
Is there any tricky case?

Thanks
Keep posting
Sapnil

[deadangelx]

Sample Input

Code: Select all

4

dip
lip
mad
map
maple
may
pad
pip
pod
pop
sap
sip
slice
slick
spice
stick
stock
*
spice stock
may pod

dip
lip
mad
map
mapl
maple
may
pad
pip
pod
pop
sap
sip
slice
slick
spice
stick
stock
*
spice slick
may mad
map maple
maple map
map map

mapl
maple
mba
mbal
mbale
mbple
*
mba mapl

map
mapl
maple
mba
mbal
mbale
mbp
mbple
*
mba mapl

Sample Output

Code: Select all

spice stock 4
may pod 3

spice slick 2
may mad 1
map maple 2
maple map 2
map map 0

mba mapl 5

mba mapl 3

[gt1404]

Hey guys I'm wondering if anyone can offer some advice on this problem. I'm new to the site (solved about ~10). I submitted this specific problem multiple times under multiple white space interpretations. I'm fairly confident that my algorithm works and it passes all test cases. So I am wondering if anyone has ran into similar difficulties here that they care to share.

Also regarding the problem I count spaces as a letter meaning:
"a" can be changed to "ba" and "ab" legally

I think I might have some sort of whitespace issues?. Also I am running g++ under cygwin in windows (unix style files converted using cmd: dos2unix) if that makes any difference.

Thanks in advance

My most recent code:

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cmath>

using namespace std;

// #define DEBUG


// some global data
const int MAX_NUM_WORDS = 200;
int G[MAX_NUM_WORDS][MAX_NUM_WORDS];
int visited[200];

// Assume size of both strings is greater than 1
// and that they are the same size 
// and not the same string
bool isDistOneAway(const string& s1, const string& s2)
{
	if(s1 == s2) return false;
	
	int diff = 0;
	int size = min(s1.size(), s2.size());
	for(int i = 0; i < s1.size(); i++)
		if(s1[i] != s2[i])
		{
			diff++;
			if(diff > 1) return false;
		}
	if(s1.size() != s2.size() && diff != 0) return false;
	return true;
}

// start - current node in bfs process
// dest - destination
// level - which level are we on
// size - how many nodes should we concern ourselves with here
int breadthFirstSearch(int start, int dest, int size)
{
	if(start == dest) return 0;
	queue< pair<int, int> > Q;
	Q.push(make_pair(start, 0));
	
	while(!Q.empty())
	{	
		pair<int,int> r = Q.front();
		int id = r.first;
		Q.pop();
		if(id == dest) return r.second;
			
		for(int i = 0; i < size; i++)
			if(G[id][i] == 1)
				if(visited[i] == 0)
				{
					Q.push(make_pair(i, r.second+1));
				}
		visited[id] = 1;
	}
	
	return -1;
}


int main()
{
	int N;
	cin>>N;
	
	int words_used = 0;
	for(int i = 0; i < N; i++)
	{
		if(i != 0) cout<<endl;
		// reset graph, reset as minimal an amout of memory as possible
		for(int x =0; x < 200; x++)
		for(int y =0; y < 200; y++)
			G[x][y] = 0;
			
		words_used = 0;
		// a vector for each word length
		// some of these i.e. 0 and 1 are unused
		vector<int> vec[11];
		map<string, int> int_map;
		vector<string> id_map;
		
		string str;
		
		while(true)
		{
			getline(cin, str);
			if(str == "" || str == "\n")continue;
			if(str == "*") break;
			// we dont care about "" input since it will never
			// be used and hence does not affect results
			int id = id_map.size();
			id_map.push_back(str);
			
			// each string in dictionary guaranteed to be unique
			vec[str.size()].push_back(id);
			int_map[str] = id;
			words_used++;
			
			#ifdef DEBUG
				cout<<"\t\tread : \""<<str<<"\""<<endl;
			#endif
		}
		
		#ifdef DEBUG
			cout<<"the maps: "<<endl;
			for(int i = 0; i < id_map.size(); i++)
			{
				cout<<"vec : "<<id_map[i]<<endl;
				cout<<"map : "<<int_map[id_map[i]]<<endl<<endl;
			}	
			
			cout<<"\t\tabout to create the graph"<<endl;
		#endif
			
		// create the graph
		// same length words
		for(int j = 1; j < 10; j++)
		for(int x = 0; x < (int)(vec[j].size()-1); x++)
		{
			for(int y = x+1; y < (int)vec[j].size(); y++)
			{
				if(isDistOneAway(id_map[vec[j][x]],id_map[vec[j][y]]))
				{
					G[vec[j][x]][vec[j][y]] = 1;
					G[vec[j][y]][vec[j][x]] = 1;
					#ifdef DEBUG
						cout<<"\t\tadded : "<<id_map[vec[j][x]]<<" ---> "<<id_map[vec[j][y]]<<endl;
					#endif
				}
			}
		}
		// now different length words
		for(int j = 1; j < 10-1; j++)
		for(int x = 0; x < (int)(vec[j].size()); x++)
		{
			for(int y = 0; y < (int)vec[j+1].size(); y++)
			{
				string temp = " " + vec[j][x];
				if(isDistOneAway(id_map[vec[j][x]],id_map[vec[j+1][y]])
					|| isDistOneAway(temp, id_map[vec[j+1][y]]))
				{
					G[vec[j][x]][vec[j+1][y]] = 1;
					G[vec[j+1][y]][vec[j][x]] = 1;
					#ifdef DEBUG
						cout<<"\t\tadded : "<<id_map[vec[j][x]]<<" ---> "<<id_map[vec[j+1][y]]<<endl;
					#endif
				}
			}
		}
		#ifdef DEBUG
			cout<<"\t\twords used = "<<words_used<<endl;
		#endif
	
		// read the next line
		while(true)
		{
			if(cin.peek() == '\n') break;
			string word1, word2;
			cin>>word1;
			if(cin.eof()) break;
			cin>>word2;;
		
			#ifdef DEBUG
				cout<<"\t\ttest : "<<word1<<"  and  "<<word2<<endl;
			#endif
			
			if(word1 == word2)
				cout<<word1<<" "<<word2<<" "<<0<<endl;
			else
			{
				// RUN BREADTH FIRST SEARCH
				for(int j = 0; j < 200; j++)
					visited[j] = 0;
				
				
				if(word1.size() != 1 || word2.size() != 1)
				{
					int steps = breadthFirstSearch(int_map[word1], int_map[word2], words_used);
					cout<<word1<<" "<<word2<<" "<<steps<<endl;
				}
				else
					cout<<word1<<" "<<word2<<" "<<1<<endl;	
			}
			if(cin.peek()=='\n')
				cin.ignore(1);
		}
		if(cin.peek()=='\n')
			cin.ignore(1);
	}
	return 0;
}

[sazzadcsedu]

gt1404 wrote:

"a" can be changed to "ba" and "ab" legally.

No,it can't be.Because the problem statement clearly states that

Each successive word differs from the previous word in only a single character position while the word length remains the same.

So word must be same length to transform.

[gt1404]

ahhh I should be more careful. Thanks for the tip.

-gt