454 - Anagrams

[mf]

such a simple code!!).

Simple? Oh no, it's horrible and unreadable!

This is what I'd call a simple code - I immediately see what every piece and what the code as a whole does. It's in Python, which unfortunately UVa judge doesn't recognize yet, but you get the idea:

Code: Select all

#!/usr/bin/python
import sys

def key(s):    # returns a sorted list of letters in string s
    return sorted(filter(lambda c: c.isalpha(), s))

T = int(sys.stdin.readline())
sys.stdin.readline()

for cs in range(T):
    if cs > 0: print

    z = []
    while True:
        s = sys.stdin.readline().rstrip('\n')
        if len(s) == 0: break
        z.append(s)

    z = sorted(set(z))    # removes duplicates and sorts lexicographically

    for i in range(len(z)):
        for j in range(i+1, len(z)):
            if key(z[i]) == key(z[j]):
                print '%s = %s' % (z[i], z[j])

And you can write something similarly readable in C++, too (though it'd be quite a bit more verbose). Just use all the good features that C++ gives you - std::sort, std::uniq, vector<string>, etc. Don't resort to low level manipulation of bytes, think in objects.

As for some test cases, here:

Code: Select all

2

xy
yx
aaa
aaab
aaa
aaab
aaa
aaba
a a a

aaa
aaa
aaab
aaa
aaa b
a a a

Output:

Code: Select all

a a a = aaa
aaab = aaba
xy = yx

a a a = aaa
aaa b = aaab

[Obaida]

That was a stupid mistake in sorting!!!
Thank you for the help..

>> about simple (this is all about point of view). ya my code was horrible..

[arifcsecu]

I have tried 8 -9 hours for this problem
Then i got accepted

my algorithm is :

1) For each test case
scan the input as one string at a time and
map the input string in a distinct string array

2. sort the distinct string array as lexicographical order
like
int lexorder(string a,string b)
{
int i,j,k;
int l1,l2;
string t;

l1=a.length();
l2=b.length();
k=1;
for(i=0;i<l1;i++)
{
if(a<b)
break;
else if(a>b)
{ k=0;
break;
}
if(i>=l2)
break;
}
return k;
}
3. match the anagram

[arifcsecu]

cc

[chucky316]

hii .. can anybody plz give me his AC exe program .... and i want to know how i recognize the end of the last test case as there is no blank line after it?? THX in advance meroboy_66@hotmail.com

[sohel]

Look at ayon's post made on 12th July for handling input files when there is no new line at the end.
For testing in/out you can use gmark's site http://www.uvatoolkit.com/problemssolve.php , however problem 454 isn't available yet.

[chucky316]

please can anybody tell me why this code is giving WA !!!!
i compared outputs with AC one and still WA

Code: Select all

#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<set>
#include<fstream>
using namespace std;
bool check(string a,string b)
{
     if(a<=b)return true;
     else return false;
}

bool check2(vector<string>a,string b)
{
     for(int i=0;i<a.size();i++)
     {
             if(b==a[i]){return false;}
     }
     return true;
}
void wadab(vector<string>& a)
{
     for(int i=0;i<a.size();i++)
     {
             for(int j=0;j<a[i].size();j++)
             {
                     if(!isalpha(a[i][j])&&!isdigit(a[i][j])){a[i].erase(j,1);j--;}
             }
     }
     
     for(int i=0;i<a.size();i++)
     {
             for(int j=0;j<a[i].size();j++)
             {
                     a[i][j]=tolower(a[i][j]);
             }
     }
     for(int i=0;i<a.size();i++)
     {
             sort(a[i].begin(),a[i].end());
     }
    
     
}
int main()
{
    fstream f;
    f.open("kk.txt",ios::out);
    int count=0;
    string s,dummy;
    vector<string>h1;
    vector<string>h2;
    vector<string>res;
    set<string>r;
    int num;
    cin>>num;
    getline(cin,dummy);
    getline(cin,dummy);
    
    while (!feof(stdin)) 
    {
          getline(cin,s);
                         if(!s.empty())
                         {
                                       if(check2(h1,s)){
                                       h1.push_back(s);
                                       sort(h1.begin(),h1.end());}
                         }
                         else {
                              if(count<num ){
                              h2=h1;
                              wadab(h2);
                              
                              for(int i=0;i<h2.size();i++)
                              {
                                      for(int j=i+1;j<h2.size();j++)
                                      {
                                              if(h2[i].compare(h2[j])==0 && !h2[i].empty() && !h2[j].empty()){
                                              
                                              string x;
                                              if(h1[i]!=h1[j]){
                                              if(check(h1[i],h1[j]))
                                              {x+=h1[i]+" = "+h1[j];}
                                              else if (!check(h1[i],h1[j]))
                                              {x+=h1[j]+" = "+h1[i];}
                                              if(check2(res,x))
                                              {res.push_back(x);}
                                              }}
                                      }
                              }
                              sort(res.begin(),res.end());
                              
                              for(int i=0;i<res.size();i++)
                              {
                                      cout<<res[i]<<endl;
                              }
                              count++;
                              if(num-count!=0)
                                               {
                                               cout<<endl;
                                               while(!h1.empty()){h1.pop_back();}
                                               while(!h2.empty()){h2.pop_back();}
                                               while(!res.empty()){res.pop_back();}
                                               }
                              else break;
                                   
                              }
                         }
    }
    system("pause");
    return 0;
}

[chucky316]

THANKS i got AC finally .... i was converting to lower case letters but seems to be no need for that THX

[Bella Swan]

Can someone please check this code for me? Judges' feedback for this code is wrong answer. I modified it several times to get it working like this thread's outputs (not counting duplicate strings) and an acc code's outputs (takes only alphanumeric characters and digits). But in vain.

Code: Select all

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>

using namespace std;

char name[105][1005],line[105][1005],temp[1005];
int i,j,k,n,test,z,length[105],t,p;

void init ()

{
	for (i=0;i<105;i++)
	{
	
		
		for (j=0;j<305;j++)
		{
		
			name[i][j]='\0';
			line[i][j]='\0';
			
		}
	}

	for (i=0;i<305;i++)
		temp[i]='\0';
}



int main ()

{
     :roll: scanf ("%d",&test);
	getchar ();

	for (z=1;z<=test;z++)
	
	{
		init ();
		n=0;
		 while(1) 
		{ 
			if(!gets(temp))
              break;

			k=strlen (temp);
			if(k==0) 
			{ 
				break; 
			} 

			length[n]=k;
			strcpy(name[n],temp); 
			n++; 
		}

	 /* Sorts the input lexicographically*/	 
	for (i=0;i<n;i++)                  
		{
		
			for (j=i+1;j<n;j++)
			{
			
				if (strcmp(name[i],name[j])>0)
				{
				
					strcpy(temp,name[i]);
					strcpy (name[i],name[j]);      
					strcpy (name[j],temp);              

					t=length[i];
					length[i]=length[j];
					length[j]=t;
				}

				else if (strcmp(name[i],name[j])==0)  /* if two inputs are same one is nullified*/
				{
				
					strcpy (name[j],"\0");         
					
				}
			}

			 
		}  
		  /************************/
/*deletes the unnecessary characters and spaces and saves it to a new array*/

		for (i=0;i<n;i++)
		{
			k=0;
			for (j=0;j<length[i];j++)
			{
				if (isalpha(name[i][j]) || isdigit (name[i][j]))

				//if (!isspace(name[i][j]))
				{
					line[i][k++]=name[i][j];

				}

			}

			length[i]=k;

			strcpy (temp,line[i]);
			
			sort (temp,temp+k);

			strcpy (line[i],temp);
		}

		
		/********************************/

		/*Output portion*/
        for (i=0;i<n;i++)
		{
		
			for (j=i+1;j<n;j++)
			{
			
				
				{
				
					if (strcmp(line[i],line[j])==0)
					{
					
					
						{
							if (strcmp(name[i],name[j])!=0)
							{
								printf ("%s = %s\n",name[i],name[j]);
								
							}

							
						}

						
					}
				}
			}
		}

		/****************************/

		/*prints blank line between cases. But normally multiple input programs*/
		/*don't follow this, i know. I got it from an accepted code*/

	     if (z<test)
			printf ("\n");

	
	}

       return 0;
}

The inputs and outputs all over the board are somewhat confusing.

Code: Select all

erosh
erosh   /*same as first one*/
horse
horse  /*it's already above it*/
ac bd
a cbd
q
q  /*same as one above it*/
[horse]'
[e]rosh'
iiiiiiiiiiiiij
iiiiiiiiiiiiji
orchestra
pq
qp
carthorse
erosh    /*same as first one*/
horsecart
ok i now donut
oknow uidot n
i do not know u
abdc
kencti kecut
kecut kencit

So what is the actual output?

this one

Code: Select all

[e]rosh' = [horse]'
a cbd = abdc
a cbd = ac bd
abdc = ac bd
carthorse = horsecart
carthorse = orchestra
erosh = erosh
erosh = erosh
erosh = horse
erosh = horse
erosh = erosh
erosh = horse
erosh = horse
erosh = horse
erosh = horse
horse = horse
horsecart = orchestra
i do not know u = ok i now donut
i do not know u = oknow uidot n
iiiiiiiiiiiiij = iiiiiiiiiiiiji
kecut kencit = kencti kecut
ok i now donut = oknow uidot n
pq = qp
q = q

or this one

Code: Select all

[e]rosh'  = [horse]'
a cbd  = abdc
a cbd  = ac bd
abdc  = ac bd
carthorse  = horsecart
carthorse  = orchestra
erosh  = horse
horsecart  = orchestra
i do not know u  = ok i now donut
i do not know u  = oknow uidot n
iiiiiiiiiiiiij  = iiiiiiiiiiiiji
kecut kencit = kencti kecut
ok i now donut  = oknow uidot n
pq  = qp

or this?

Code: Select all

[e]rosh'  = [horse]'
[e]rosh'  = erosh
[e]rosh'  = horse
[horse]'  = erosh
[horse]'  = horse
a cbd  = abdc
a cbd  = ac bd
abdc  = ac bd
carthorse  = horsecart
carthorse  = orchestra
erosh  = horse
horsecart  = orchestra
i do not know u  = ok i now donut
i do not know u  = oknow uidot n
iiiiiiiiiiiiij  = iiiiiiiiiiiiji
kecut kencit = kencti kecut
ok i now donut  = oknow uidot n
pq  = qp

First output contradicts mf's output strategy as far as i understood. But again this is an acc code's output in another thread. So I hope some one can give me a hand and tell me what's wrong with my code and which one is correct output.

Best regards.

[Shafaet_du]

DONT WORRY ABOUT DUPLICATE INPUTS. I DIDNT CHECK FOR DUPLICATE INPUTS BUT GOT AC.

[mathgirl]

I am repeatedly getting WA on this one. I tried input from the previous posts on this topic and it works correctly.
Can anyone please explain why I m getting WA ?

Code: Select all

#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

int main()
{
	string word;
	string empty;
	int n;
	map<string,vector<string> > input;
	vector<string> output;
	
	cin >> n;
	getline(cin,empty);
	getline(cin,empty);

	for(int i=0;i<n;i++)
	{
		getline(cin,word);
		while(!word.empty())
		{
			string copy(word);
			int j = 0;
			while(j<copy.size())
			{
				if(isspace(copy[j]))
					copy.erase(j,1);
				else
				{
					copy[j] = tolower(copy[j]);
					j++;
				}
			}
			sort(copy.begin(),copy.end());
			
			// if the word is a duplicate remove it.
			input[copy].push_back(word);
			getline(cin,word);
		}

		if(!input.empty())
		{
			map<string,vector<string> >::const_iterator iter;
			for(iter=input.begin();iter!=input.end();iter++)
			{
				vector<string> temp = iter->second;
				if(temp.size() <= 1)
					continue;

				sort(temp.begin(),temp.end());
				for(int j=0;j<temp.size()-1;j++)
					for(int k=j+1;k<temp.size();k++)
					{
						if(temp[j] != temp[k])
							output.push_back(string(temp[j]).append(" = ").append(temp[k]));
					}

			}
		}

		if(!output.empty())
		{
			string prev = " ";
			sort(output.begin(),output.end());
			for(int j=0;j<output.size();j++)
			{	
				if(output[j] == prev)
				{
					prev = output[j];
					continue;
				}
				prev = output[j];
				cout << output[j] << endl;
			}
		}

		cout << endl;

		output.clear();
		input.clear();
		
	}
	
	return 0;
}

[brianfry713]

Don't print a blank line at the end.

[mathgirl]

I tried that, and got WA again. I m getting frustrated with this. To be clear,

1) lexicographic order means A > a > B > b.... Z > z right ?
2) And my output format is

(output 1 starts)
<word1><space><=><space><word2>
<blank line> (output 2 starts)
<word1><space><=><space><word2>
<word1><space><=><space><word2>
<end> (no blank line)

3) I am removing duplicates from inputs, my program does not print anagrams of the form " aaa = aaa "
4) If there are no anagrams, program prints a single blank line.

Am i doing something wrong ? I have tried submitting this almost 10 times changing each of these, still WA

[brianfry713]

Next time post your updated code.

My AC code sorts a copy of the letters in each word (except for spaces) by their ASCII value. I sort the entire input using strcmp(). I don't remove duplicate words.

For this input:

Code: Select all

4

carthorse
horse
horse cart
i do not know u
ok i now donut
orchestra

carthorse
horse
horse cart
i do not know u
ok i now donut
orchestra

abc
def

cba
abc
abc

My AC output is:

Code: Select all

carthorse = horse cart
carthorse = orchestra
horse cart = orchestra
i do not know u = ok i now donut

carthorse = horse cart
carthorse = orchestra
horse cart = orchestra
i do not know u = ok i now donut


abc = abc
abc = cba
abc = cba

[mathgirl]

Ok. I am getting the same output for the input u gave. But still got WA.

Code: Select all

    
    #include <vector>
    #include <string>
    #include <map>
    #include <algorithm>
    #include <iostream>
    #include <cstring>

    using namespace std;
	
    int main()
    {
       string word;
       string empty;
       int n;
       map<string,vector<string> > input;
       vector<string> output;
       
	   bool flag = true;
	   
       cin >> n;
       getline(cin,empty);
       getline(cin,empty);

       for(int i=0;i<n;i++)
       {
		  
		  if(flag)
			flag = false;
		  else
			cout << endl;
		  
		  getline(cin,word);
          while(!word.empty())
          {
             string copy(word);
             int j = 0;
             while(j<copy.size())
             {
                if(isspace(copy[j]))
                   copy.erase(j,1);
                else
                {
                   copy[j] = tolower(copy[j]);
                   j++;
                }
             }
             sort(copy.begin(),copy.end());
             
             // if the word is a duplicate remove it.
             input[copy].push_back(word);
             getline(cin,word);
          }

          if(!input.empty())
          {
             map<string,vector<string> >::const_iterator iter;
             for(iter=input.begin();iter!=input.end();iter++)
             {
                vector<string> temp = iter->second;
                if(temp.size() <= 1)
                   continue;

                sort(temp.begin(),temp.end());
                for(int j=0;j<temp.size()-1;j++)
                   for(int k=j+1;k<temp.size();k++)
                   {
                      output.push_back(string(temp[j]).append(" = ").append(temp[k]));
                   }

             }
          }

          if(!output.empty())
          {
			 sort(output.begin(),output.end());
             for(int j=0;j<output.size();j++)
             {   
                cout << output[j] << endl;
             }
          }

          output.clear();
          input.clear();
          
       }
       
       return 0;
    }