454 - Anagrams

[brianfry713]

Don't convert copy to lowercase.

[mathgirl]

Damn ! I am really stupid. Thanks a ton Brian !

[skyhigh_]

#include<algorithm>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<deque>
#define pi 2*acos(0.0)
using namespace std;

int main()
{

int t,i,j,k,n;
bool f;
scanf("%d%*c%*c",&t); // testcases

while( t-- )
{
string s[105],str[105];
string tem;
map<string,bool>m;
m.clear();

n=0;
// input

while( getline(cin,tem) )
{
if(!tem.empty())
{
if(m.find(tem)==m.end())
{
s[n++] = tem;
m[tem] =1;
}
}
else break;
}

sort(s,s+n);

// copying string without spaces

for(i=0; i<n; i++)
{
int len = s.length();

for(j=0; j<len; j++)
{
if(isalnum(s[j]))
str.push_back(s[j]);
}
}

for(i=0; i<n; i++) sort(str.begin(),str.end()); // sorting characters

// output

if(t) cout << endl;

for(i=0; i<n; i++)
for(j=i+1; j<n; j++)
{
if(str==str[j])
cout << s <<" = " << s[j] << endl;
}

}
return 0;
}


/*
input:
1

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

output :
carthorse = horse cart
carthorse = orchestra
horse cart = orchestra
i do not know u = ok i now donut
*/

[brianfry713]

Two consecutive output for two consecutive input is separated by a single blank line.

[Mukit Chowdhury]

I've found WA many times in this problem... but why ?? my code gives same output given above(except the last one,though I think my one is also right,as problem statement says , "Each anagram pair should be printed exactly once") ... please check this code someone...

Code: Select all

Accepted............. :)

[brianfry713]

I tested 4 versions of your code and none of them match the I/O I posted above from my AC code.

[Mukit Chowdhury]

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 = cba

doesn't my code return this output ??? my compiler shows me this output... or is it wrong ??? :O

[brianfry713]

That is not the same output for the last case.

[Angry Bird]

What is the problem of my code?? Getting WA again and again...
Plzzz check it...

Code: Select all

#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;

int func(string a,string s)
{
    int l=a.size(),i;
    vector<char>c,c2;

    for(i=0; i<l; i++)
    {
        if(isalpha(a[i]))
        {
            c.push_back(a[i]);
        }
    }
    sort(c.begin(),c.end());

    int l2=s.size();

    for(i=0; i<l2; i++)
    {
        if(isalpha(s[i]))
        {
            c2.push_back(s[i]);
        }
    }
    sort(c2.begin(),c2.end());

    if(c==c2)
    {
        return 1;
    }

    else
    {
        return 0;
    }
}

int main()
{
    int t,i,j,k,g;
    string s;

    cin>>t;
    getchar();


    for(i=1; i<=t; i++)
    {
        vector<string>a,ko;
        string t1,t2,t3;

        while(getline(cin,s))
        {
            if(s=="")
            {
                break;
            }
            a.push_back(s);
        }

        for(j=0; j<a.size(); j++)
        {
            for(k=j+1; k<a.size(); k++)
            {
                g=func(a[j],a[k]);

                if(g==1)
                {
                    t1=a[j];
                    t2=a[k];

                    if(t1>t2)
                    {
                        t3=t1;
                        t1=t2;
                        t2=t3;
                    }
                    ko.push_back(t1 + " = "+t2);
                }
            }
        }

        sort(ko.begin(),ko.end());

        for(int b=0; b<ko.size(); b++)
        {
            cout<<ko[b]<<endl;
        }
        cout<<endl;
    }
    return 0;
}

[brianfry713]

Doesn't match the sample I/O.

[Angry Bird]

Really i'm confused about your ans... Pls give me more I/O.

Code: Select all

    #include <iostream>
    #include <cstring>
    #include <vector>
    #include <cstdio>
    #include <algorithm>

    using namespace std;

    int func(string a,string s)
    {
        int l=a.size(),i;
        vector<char>c,c2;

        for(i=0; i<l; i++)
        {
            if(isalpha(a[i]))
            {
                c.push_back(a[i]);
            }
        }
        sort(c.begin(),c.end());

        int l2=s.size();

        for(i=0; i<l2; i++)
        {
            if(isalpha(s[i]))
            {
                c2.push_back(s[i]);
            }
        }
        sort(c2.begin(),c2.end());

        if(c==c2)
        {
            return 1;
        }

        else
        {
            return 0;
        }
    }

    int main()
    {
        int t,i,j,k,g;
        string s;

        cin>>t;
        getchar();
        cout<<endl;

        for(i=1; i<=t; i++)
        {
            vector<string>a,ko;
            string t1,t2,t3;

            while(getline(cin,s))
            {
                if(s=="")
                {
                    break;
                }
                a.push_back(s);
            }

            for(j=0; j<a.size(); j++)
            {
                for(k=j+1; k<a.size(); k++)
                {
                    g=func(a[j],a[k]);

                    if(g==1)
                    {
                        t1=a[j];
                        t2=a[k];

                        if(t1>t2)
                        {
                            t3=t1;
                            t1=t2;
                            t2=t3;
                        }
                        ko.push_back(t1 + " = "+t2);
                    }
                }
            }

            sort(ko.begin(),ko.end());

            for(int b=0; b<ko.size(); b++)
            {
                cout<<ko[b]<<endl;
            }
            cout<<endl;
        }
        return 0;
    }

[brianfry713]

When I run your code on the sample input it's not printing anything.
http://ideone.com/ux3owo

[uDebug]

In addition to the excellent test case shared by brianfry713, I'd like to add one that helped me catch my bug.

If this isn't already clear to you, please understand that the output has to be lexicographic not only between pairs of words but also in the order of phrases printed. So, in the output, starting from the top, observe that each pair of phrases is lexicographically ordered - and that the entire list of phrases is lexicographically ordered as well.

Input:

Code: Select all

2

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

zaaaahari is here
si hari ere h aaaaz
i like tunes
tunes i like

AC Output:

Code: Select all

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

i like tunes = tunes i like
si hari ere h aaaaz = zaaaahari is here

[uDebug]

If you're stuck on this problem, please be sure to check out this thread as well.

http://acm.uva.es/board/viewtopic.php?f ... 0c6721aefc

[uDebug]

Really i'm confused about your ans... Pls give me more I/O.

I think you might be nearly there.

Couple points:

Point #1
In the future do not do this

Code: Select all

cin>>t; getchar();

and count on the "getchar()" to catch the newline. Chances are it won't.

Point #2
The problem states

Two consecutive output for two consecutive input is separated by a single blank line.

But you're printing a newline after each case - including the last one.

For Point #1, I did the following

Code: Select all

/* Read in the number of test cases */
scanf("%d\n",&t);

and for Point #2 I added this in the main for loop

Code: Select all

if(i != 1) {
    cout<<endl;
}

and your code passed all the test cases on this thread. So, it appears to be AC code.