164 - String Computer

[RehabReda]

btw if u know how to solve this share it

[Mans]

: D yup , because i was using my previous implementation of the Edit Distance Algorithm (copy and paste ! ):d

btw i had tested ur code ..
try to test your program with the following test case , i think it give "out of range" exception ! ..

input
wrrr awwsa

output form uvakit

Ia01Cw03Cs04Ca05EMans

thanks very much
yes i have changed it which was a trivial mistake j instead of i
i have found a bug in your code which also find it in mine
this case
wwwww wwwwwww
in ur code and me
the output :
Iw01Iw02E
the right answer:
Iw06Iw07E

hmmm
but i think our output is also right !

because i can add W , W at the front or at the end ! the result string is the same ..

quote from problem statement "Since there may be multiple solutions, only one should be produced. Any solution that satisfies these criteria will be accepted. " ..

i am sure that our mistake is at finding path ! .. may be because when adding or removing a char the index must change in the next operations !

for example !.
addx fladd

it will add f at 01 and add l at 02 , then remove x from 06 !!

[Mans]

btw if u know how to solve this share it

finally i get AC e7l :d lol

and ur code also get AC

your mistake was as i expected !... when you try to find the path ..

1-you must increment number of add or del at the end of each case , i mean after display the index .
2-in the insertion case .. the index will be J only without any addition or subtraction ! ..
3-in the deletion case ... the index will be j+NoOfAdditions-NoOfDeletions only , without add 1 ! .

so try to edit your printChanges function to :

Code: Select all

void printChanges(int i,int j)
    {

       if ( (i==0&&j==0))
		  return;
       if(Tracing[i][j]==1)//Means Copy
       {
          printChanges(i-1,j-1);
       }
       else if (Tracing[i][j]==2)//Means Replace
       {
          printChanges(i-1,j-1);
          cout<<"C"<<SecondString[i-1];
          if(j+NoOfAdditions-NoOfDeletions<10)
             cout<<"0";
          cout<<j+NoOfAdditions-NoOfDeletions;
       }
       else if (Tracing[i][j]==3)//Means Delete
       { 
          printChanges(i,j-1); 
          cout<<"D"<<FirstString[j-1];
          if(j+NoOfAdditions-NoOfDeletions<10)
             cout<<"0";
          cout<<j+NoOfAdditions-NoOfDeletions;
		 NoOfDeletions++;
       }
       else if (Tracing[i][j]==4)//Means Add
       {
       
          printChanges(i-1,j); 
          cout<<"I"<<SecondString[i-1];
          if(i<10)
             cout<<"0";
          cout<<i;
		  NoOfAdditions++;
       }
    }

and you will get it accepted isA :d

[RehabReda]

btw if u know how to solve this share it

finally i get AC e7l :d lol

and ur code also get AC

your mistake was as i expected !... when you try to find the path ..

1-you must increment number of add or del at the end of each case , i mean after display the index .
2-in the insertion case .. the index will be J only without any addition or subtraction ! ..
3-in the deletion case ... the index will be j+NoOfAdditions-NoOfDeletions only , without add 1 ! .

so try to edit your printChanges function to :

Code: Select all

void printChanges(int i,int j)
    {

       if ( (i==0&&j==0))
		  return;
       if(Tracing[i][j]==1)//Means Copy
       {
          printChanges(i-1,j-1);
       }
       else if (Tracing[i][j]==2)//Means Replace
       {
          printChanges(i-1,j-1);
          cout<<"C"<<SecondString[i-1];
          if(j+NoOfAdditions-NoOfDeletions<10)
             cout<<"0";
          cout<<j+NoOfAdditions-NoOfDeletions;
       }
       else if (Tracing[i][j]==3)//Means Delete
       { 
          printChanges(i,j-1); 
          cout<<"D"<<FirstString[j-1];
          if(j+NoOfAdditions-NoOfDeletions<10)
             cout<<"0";
          cout<<j+NoOfAdditions-NoOfDeletions;
		 NoOfDeletions++;
       }
       else if (Tracing[i][j]==4)//Means Add
       {
       
          printChanges(i-1,j); 
          cout<<"I"<<SecondString[i-1];
          if(i<10)
             cout<<"0";
          cout<<i;
		  NoOfAdditions++;
       }
    }

and you will get it accepted isA :d

thanks alot i get accepted el7dl
thanks ^ infinity ^infinity

[aia]

??? ?? ?????? ??? ???? ?? ??????? ??
???????? ????? ?? ?? ????? ??? ????? cases ? ??
?? ????? ????? ??? ???? ????????

Code: Select all

#include<iostream>
#include<vector>
#include<string>
//#include<fstream>
#include<math.h>
using namespace std ; 
//fstream fin ("IN.txt");
//fstream fout("Out.txt");
string str1 , str2;
int Table[100][100];
int i , j ; 
int minimum(int x ,int y,int  z)
{
	int result ; 
	result = min(x , y);
	result= min(result , z);
	return result;
}

string convert(int num)
{
	string number="" ; 
	int tempnum =num ; 
	int i=0 ;
	while(num!=0)
	{
		if(num>=1 && num<=9)
			number+=num+'0' ; 
		else
			number+=(num%10)+'0' ; 
		num/=10 ;
		i++;
	}
	string temp = number ;
	if(tempnum>=1 &&tempnum<=9)
	{
		number = "0"+temp;
	}
	else
	{
		for(int j=0 ;j<number.length() ; j++)
			number[j] = temp[temp.length()-1-j];
	}
	return number ; 
}

int EditDistance(string dist , string source)
{
	for ( i=0 ; i<=dist.length() ; i++)
		Table[i][0] = i ;// deletion
	for (j=0 ; j<=source.length() ; j++)
		Table[0][j] = j; // insertion
	for (j= 1 ;j<=source.length() ; j++)
	{
		for ( i=1 ; i<=dist.length() ; i++)
		{
			if( dist[i-1] == source[j-1])
				Table[i][j] = Table[i-1][ j-1];
			else
			{
				Table[i][j]= minimum
					(
					Table[i-1][j] + 1,  // deletion
					Table[i][j-1] + 1,  // insertion
					Table[i-1][j-1] + 1 // substitution
					);
			}
		}
	}

	return Table[dist.length()][source.length()];
}


string BackTracke(int x , int y)
{
	string temp ; 
	string number;
	if(x>0&&y==0)
	{
		number = convert(x);
		temp="D" ; 
		temp.append(1 , str1[x-1]);
		temp+=number ; 
		return BackTracke(x-1 , y)+temp;
	}
	else if(x==0 &&y>0)
	{
		number = convert(y);
		temp="I" ; 
		temp.append(1 , str2[y-1]);
		temp+=number ; 
		return BackTracke(x , y-1)+temp;
	}
	else if(x==0 &&y>0)
	{
		number = convert(y);
		temp="D" ; 
		temp.append(1 , str2[y-1]);
		temp+=number ; 
		return BackTracke(x , y-1)+temp;
	}
	else if(x==0 ||y==0)
		return"";
	else if(str1[x-1]==str2[y-1])
		return BackTracke(x-1 , y-1);
	else 
	{
		if(Table[x][y]==Table[x-1][y] + 1)//delete
		{
			number = convert(y+1);
			temp="D" ; 
			temp.append(1 , str1[x-1]);
			temp+=number ;
			return BackTracke(x-1 , y)+temp;
		}
		else if(Table[x][y]==Table[x][y-1]+1)//insertion
		{
			number = convert(y);
			temp="I" ; 
			temp.append(1 , str2[y-1]);
			temp+=number ;
			return BackTracke(x, y-1)+temp;
		}
		else if(Table[x][y]==Table[x-1][y-1]+1) //change Table[x-1][y-1] + 1
		{
			number = convert(y);
			temp="C" ; 
			temp.append(1 , str2[y-1]);
			temp+=number ;
			return BackTracke(x-1 , y-1)+temp;
		}
		
		
	}
}
int main()
{
	int s ; 
	while(cin>>str1)
	{
		if(str1=="#")
			break;
		cin>>str2;
		if(str1==""&&str2=="")
		{
			cout<<"E"<<endl;
			continue ;
		}
		s= EditDistance(str1, str2);
		string n = BackTracke(str1.length(), str2.length());
		cout<<n<<"E"<<endl;
	}
	return 0 ; 
}

???? ?????

[aia]

plz could anyone help me to know the bug in my code in this Problem
this is my code :

Code: Select all

#include<iostream>
#include<vector>
#include<string>
//#include<fstream>
#include<math.h>
using namespace std ; 
//fstream fin ("IN.txt");
//fstream fout("Out.txt");
string str1 , str2;
int Table[100][100];
int i , j ; 
int minimum(int x ,int y,int  z)
{
	int result ; 
	result = min(x , y);
	result= min(result , z);
	return result;
}

string convert(int num)
{
	string number="" ; 
	int tempnum =num ; 
	int i=0 ;
	while(num!=0)
	{
		if(num>=1 && num<=9)
			number+=num+'0' ; 
		else
			number+=(num%10)+'0' ; 
		num/=10 ;
		i++;
	}
	string temp = number ;
	if(tempnum>=1 &&tempnum<=9)
	{
		number = "0"+temp;
	}
	else
	{
		for(int j=0 ;j<number.length() ; j++)
			number[j] = temp[temp.length()-1-j];
	}
	return number ; 
}

int EditDistance(string dist , string source)
{
	for ( i=0 ; i<=dist.length() ; i++)
		Table[i][0] = i ;// deletion
	for (j=0 ; j<=source.length() ; j++)
		Table[0][j] = j; // insertion
	for (j= 1 ;j<=source.length() ; j++)
	{
		for ( i=1 ; i<=dist.length() ; i++)
		{
			if( dist[i-1] == source[j-1])
				Table[i][j] = Table[i-1][ j-1];
			else
			{
				Table[i][j]= minimum
					(
					Table[i-1][j] + 1,  // deletion
					Table[i][j-1] + 1,  // insertion
					Table[i-1][j-1] + 1 // substitution
					);
			}
		}
	}

	return Table[dist.length()][source.length()];
}


string BackTracke(int x , int y)
{
	string temp ; 
	string number;
	if(x==str1.length()+1&&y==str2.length()+1)
	{
		return BackTracke(x-1 , y-1)+"E";
	}
	if(x>0&&y==0)
	{
		number = convert(x);
		temp="D" ; 
		temp.append(1 , str1[x-1]);
		temp+=number ; 
		return BackTracke(x-1 , y)+temp;
	}
	else if(x==0 &&y>0)
	{
		number = convert(y);
		temp="I" ; 
		temp.append(1 , str2[y-1]);
		temp+=number ; 
		return BackTracke(x , y-1)+temp;
	}
	else if(x==0 &&y>0)
	{
		number = convert(y);
		temp="D" ; 
		temp.append(1 , str2[y-1]);
		temp+=number ; 
		return BackTracke(x , y-1)+temp;
	}
	else if(x==0 ||y==0)
		return"";
	else if(str1[x-1]==str2[y-1])
		return BackTracke(x-1 , y-1);
	else 
	{
		if(Table[x][y]==Table[x-1][y] + 1)//delete
		{
			number = convert(y+1);
			temp="D" ; 
			temp.append(1 , str1[x-1]);
			temp+=number ;
			return BackTracke(x-1 , y)+temp;
		}
		else if(Table[x][y]==Table[x][y-1]+1)//insertion
		{
			number = convert(y);
			temp="I" ; 
			temp.append(1 , str2[y-1]);
			temp+=number ;
			return BackTracke(x, y-1)+temp;
		}
		else if(Table[x][y]==Table[x-1][y-1]+1) //change Table[x-1][y-1] + 1
		{
			number = convert(y);
			temp="C" ; 
			temp.append(1 , str2[y-1]);
			temp+=number ;
			return BackTracke(x-1 , y-1)+temp;
		}
		
		
	}
}
int main()
{
	int s ; 
	while(cin>>str1)
	{
		if(str1=="#")
			break;
		cin>>str2;
		s= EditDistance(str1, str2);
		string n = BackTracke(str1.length()+1, str2.length()+1);
		cout<<n<<endl;
	}
	return 0 ; 
}

Thanks in advance

[sa.phoenix]

Hi all,

My solution for Problem 164 is giving WA on the judge. I have tested my solution with some test cases of my own as well as the testcases posted in the links http://acm.uva.es/board/viewtopic.php?f=1&t=42480 and http://acm.uva.es/board/viewtopic.php?f=1&t=44516 , and my solution produces the correct output for all of them.

I also tried changing the priority for the resultant output from DELETE > INSERT > MATCH to MATCH > INSERT > DELETE as mentioned in http://acm.uva.es/board/viewtopic.php?f=1&t=42480 , but i still get WA.

Can someone point me to a testcase where my code fails to produce the correct output?

My C++ code is posted below:

Code: Select all

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <sstream>
using namespace std;
#define LET(_x,_a) typeof(_a) _x(_a)
#define FOR(_i, _a, _n) for(LET(_i, _a); _i != _n; ++_i)
#define REP(_i, _n) FOR(_i, 0, _n)
#define sz size()
#define i2s(_x) ({stringstream sout; sout<<_x; sout.str();})
#define s2i(_str) ({stringstream sin(_str); int _x; sin>>_x; _x;})

int main()
{
  string line;
  while(getline(cin, line))
  {
    if(line == "#")break;
    int spaceindex = line.find(' ');
    string first = line.substr(0, spaceindex), second = line.substr(spaceindex+1);
    if(first == "#")break; //hopefully, the line == "#" check should itself suffice
    //clock_t start = clock();
    
    //Perform the Edit Distance
    int M = first.sz, N = second.sz;
    int dp[M+1][N+1]; memset(dp, 0, sizeof(dp));
    FOR(i, 1, M+1)dp[i][0] = i;
    FOR(j, 1, N+1)dp[0][j] = j;
    
    FOR(i, 1, M+1)FOR(j, 1, N+1)
    {
      if(first[i-1] == second[j-1])dp[i][j] = dp[i-1][j-1];
      else dp[i][j] = dp[i-1][j-1] + 1;
      
      if(dp[i][j] > dp[i-1][j] + 1)dp[i][j] = dp[i-1][j] + 1;
      
      if(dp[i][j] > dp[i][j-1] + 1)dp[i][j] = dp[i][j-1] + 1;
    }
    
    //REP(i, M+1){REP(j, N+1)cout<<dp[i][j]<<" "; cout<<endl;}
    
    //Form the resultant output string 
    string ret = "E";
    for(int i = M, j = N; i >= 0 && j >= 0;) //tried changing priority from DELETE > INSERT > MATCH to MATCH > INSERT > DELETE, still WA :(
      if(i > 0 && dp[i][j] == dp[i-1][j] + 1)ret = (string)"D" + first[i-1] + (i <= 9 ? "0" : "") + i2s(i) + ret , i--;
      else if(j > 0 && dp[i][j] == dp[i][j-1] + 1)ret = (string)"I" + second[j-1] + (j <= 9 ? "0" : "") + i2s(j) + ret, j--;
      else if(i > 0 && j > 0 && dp[i][j] == dp[i-1][j-1] + 1 && first[i-1] != second[j-1])ret = (string)"C" + second[j-1] + (j <= 9 ? "0" : "") + i2s(j) + ret, i--, j--;      
      else i--, j--;
    
    //Fix the index change for Delete operation due to the delete/insert operations. 
    //Insert is already taken care of because Insert deals with the position in the second string
    int numdeletes = 0;
    REP(i, ret.sz)
    if(ret[i]=='D')
    { 
      int val = 10 * (int)(ret[i+2] - '0') + (int)(ret[i+3] - '0'); 
      val -= numdeletes; 
      numdeletes++; 
      if(val > 9)ret[i+2] = (char)(val/10 + '0');
      ret[i+3] = (char)(val % 10 + '0');
    }
    else if(ret[i] == 'I')numdeletes--;
    
    cout<<ret<<endl;
    //clock_t end = clock();
    //cout<<"Time taken: "<<(double)(end-start)/(double)CLOCKS_PER_SEC<<" seconds"<<endl;
  }
  return 0;
}

[just_yousef]

I got 11 WA, Please Help !!

Code: Select all

AC

[lighted]

Did you read this thread?

http://online-judge.uva.es/board/viewtopic.php?t=1526

[just_yousef]

Thanks lighted, Finally AC

[jddantes]

AC.
Printed Da instead of D[character] so I got WA.

[brianfry713]

Try running your code on the sample input.

[jddantes]

Output: If05Cg04Da01E
From input: abcde bcgfe
Isn't this still valid?

abcde

Insert f at 05
abcdfe

Change 04 to g
abcgfe

Delete 01
bcgfe

[brianfry713]

It looks like your code isn't terminating on #
http://ideone.com/sGgOsw

[jddantes]

http://ideone.com/DEUg65
I've changed to cin instead to accomodate input like this (still WA)

Code: Select all

abcde bcgfe
 adam
asdf 
 
#

uDebug output:

Code: Select all

Da01Ig03Cf04E
Is02Da04Cf04E

My output (verified by hand):
(adam->asdam->asdm->asdf for second output)

Code: Select all

If05Cg04Da01E
Da04Cf03Is02E