## 454 - Anagrams

Moderator: Board moderators

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

### Re: 454 - Anagrams

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))

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

z = []
while True:
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

### Re: 454 - Anagrams

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

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

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

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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 454 Anagrams

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

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

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

THANKS i got AC finally .... i was converting to lower case letters but seems to be no need for that THX
Bella Swan
New poster
Posts: 6
Joined: Mon Jun 21, 2010 9:21 pm

### Re: 454 - Anagrams

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,line,temp;
int i,j,k,n,test,z,length,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
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
Contact:

### Re: 454 - Anagrams

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

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

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

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

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

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