454 - Anagrams

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 454 - Anagrams

Post by mf » Tue Jul 28, 2009 6:26 pm

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
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 454 - Anagrams

Post by Obaida » Tue Jul 28, 2009 8:01 pm

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.. :oops: :oops:
try_try_try_try_&&&_try@try.com
This may be the address of success.

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 454 - Anagrams Accepted After many tryes

Post by arifcsecu » Mon Sep 28, 2009 9:42 pm



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
Last edited by arifcsecu on Wed Sep 01, 2010 6:08 pm, edited 1 time in total.
Try to catch fish rather than asking for some fishes.

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 454 - Anagrams

Post by arifcsecu » Tue Oct 20, 2009 10:01 am

cc
Try to catch fish rather than asking for some fishes.

chucky316
New poster
Posts: 5
Joined: Mon Apr 12, 2010 11:18 am

Re: 454 Anagrams

Post by chucky316 » Mon Apr 12, 2010 11:35 am

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 454 Anagrams

Post by sohel » Tue Apr 13, 2010 10:50 am

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
New poster
Posts: 5
Joined: Mon Apr 12, 2010 11:18 am

Re: 454 Anagrams

Post by chucky316 » Tue Apr 13, 2010 12:25 pm

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
New poster
Posts: 5
Joined: Mon Apr 12, 2010 11:18 am

Re: 454 Anagrams

Post by chucky316 » Tue Apr 13, 2010 12:35 pm

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

Bella Swan
New poster
Posts: 6
Joined: Mon Jun 21, 2010 9:21 pm

Re: 454 - Anagrams

Post by Bella Swan » Sun Jul 04, 2010 12:27 am

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. :roll:

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
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 454 - Anagrams

Post by Shafaet_du » Fri Dec 10, 2010 4:05 pm

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

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

454 Anagrams WA

Post by mathgirl » Thu Apr 26, 2012 8:29 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 454 Anagrams WA

Post by brianfry713 » Fri Apr 27, 2012 3:49 am

Don't print a blank line at the end.
Check input and AC output for thousands of problems on uDebug!

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

Re: 454 Anagrams WA

Post by mathgirl » Fri Apr 27, 2012 9:17 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 454 Anagrams WA

Post by brianfry713 » Fri Apr 27, 2012 9:30 pm

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
Check input and AC output for thousands of problems on uDebug!

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

Re: 454 Anagrams WA

Post by mathgirl » Sat Apr 28, 2012 8:39 am

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;
    }

Post Reply

Return to “Volume 4 (400-499)”