## 630 - Anagrams (II)

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

Moderator: Board moderators

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

### 630 - Anagrams (II)

i can't find why my prog. got W.A.
pls help me.

Code: Select all

``````/* @JUDGE_ID: 13487FC 630 C++ */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int sort_fun(const void *a,const void*b)
{
return( strcmp((char *)a,(char *)b) );
}

void main()
{
char dic[1000][20];
char temp[1000][20];
char test[20], in[10];
int letter1[26];
int letter2[26];
int n, i, j, flag, a, b;

int N, I;

gets(in);
N = atoi(in);
for(I=0; I<N; I++)
{
for(i=0; i<26; i++)
{
letter1[i] = 0;
letter2[i] = 0;
}

gets(in);
gets(in);
n = atoi(in);

for(i=0; i<n; i++)
gets(dic[i]);

for(;;)
{
gets(test);
test[strlen(test)] = 0;
if(!strcmp(test, "END")) break;
for(i=0; i<26; i++)
letter1[i] = 0;
for(i=0; i<strlen(test); i++)
{
letter1[test[i]-'a']++;
}
b = 0;
printf("Anagrams for: %sn", test);
for(i=0; i<n; i++)
{
flag = 1;
if(strlen(test)==strlen(dic[i]))
{
for(j=0; j<strlen(dic[i]); j++)
{
letter2[dic[i][j]-'a']++;
}

for(j=0; j<26; j++)
{
if(letter1[j]!=letter2[j])
{
flag = 0;
break;
}
}
if(flag)
{
strcpy(temp[b++], dic[i]);
}
for(j=0; j<26; j++)
letter2[j] = 0;
}
}
if(b)
{
qsort((void *)temp, b, sizeof(temp[0]), sort_fun);
for(a=0; a<b; a++)
printf("%3d) %sn", a+1, temp[a]);
}
else
{
printf("No anagrams for: %sn", test);
}
}
printf("n");
}
}
/* @END_OF_SOURCE_CODE */
``````

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
My accepted source produce:

Code: Select all

``````Anagrams for: atra
1) rata
2) atar
3) tara
4) rtaa
5) aart
``````
and it's multiply input problem ....

Dominik Michniewski
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
hello dominik,,
i have solved the touph part of anagram i think,
but now i am in trouble with anagram II
will you let me know what is the case very special here to be treated seperately,,
if there is none, then i will post my code or send it to U for help,
will you mind?
thanks--
--anupam
"Everything should be made simple, but not always simpler"

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
There is no special case ....
Only one thing is important - I don't know, but if you sort words (easier search) you must output it in order from input ...

Dominik

PS. If you want send me your code via PM or mail from my stats page. But I give you answer not earlier than in monday - I have a lot of job this weekend
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

jeff1999
New poster
Posts: 4
Joined: Wed Oct 01, 2003 5:35 pm

### 630 - Wrong Answer

I am getting a "Wrong Answer" for this solution. I realize that this is a multiple input problem, and I assume that I'm handling that correctly. Does anyone have some sample I/O that could possibly break this code?

[cpp]
// 630 - Anagrams (II)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <string>
#include <map>

struct Word
{
char val[21];
char sor[21];
};

int c_cmp(const void * a, const void * b)
{
return ((int)(*((char*)a))) - ((int)(*((char*)b)));
}

int w_cmp(const void * a, const void * b)
{
Word * w1 = (Word*)a, * w2 = (Word*)b;
return strcmp(w1->val, w2->val);
}

int main(int argc, char ** argv)
{
Word s[2][1000];
char msg[1000];
int i, j, k, n, nw, cn;
std::map<std::string, std::string> mymap;

scanf("%i", &cn);
while (cn > 0)
{
--cn;
scanf("%i", &n);
nw = 0;
mymap.clear();
for (i = 0; i < n; ++i)
{
scanf("%s", s[0][i].val);
if (mymap.find(s[0][i].val) != mymap.end())
{
--i;
--n;
}
else
{
mymap[s[0][i].val] = s[0][i].val;
strcpy(s[0][i].sor, s[0][i].val);
qsort(s[0][i].sor, strlen(s[0][i].sor), sizeof(char), c_cmp);
}
}
qsort(s[0], n, sizeof(Word), w_cmp);
while (scanf("%s", s[1][nw].val) == 1 && strcmp(s[1][nw].val, "END") != 0)
{
strcpy(s[1][nw].sor, s[1][nw].val);
qsort(s[1][nw].sor, strlen(s[1][nw].sor), sizeof(char), c_cmp);
++nw;
}
for (i = 0; i < nw; ++i)
{
printf("Anagrams for: %s\n", s[1][i].val);
k = 0;
for (j = 0; j < n; ++j)
{
if (strcmp(s[1][i].sor, s[0][j].sor) == 0)
{
printf("%3i) %s\n", ++k, s[0][j].val);
}
}
if (k == 0)
{
printf("No anagrams for: %s\n", s[1][i].val);
}
}
printf("\n");
}

return 0;
}
[/cpp]

nikhil
New poster
Posts: 11
Joined: Wed Oct 08, 2003 1:37 pm

### 630 WA

I am getting "WA"
for the following code
some body please help me???????????

#include<stdio.h>
#include<string.h>
#include<assert.h>

int i, a,b, len,l1,l2, intP[30], tr[30], h[30], hh, in, found ;
char voca[1000][23], test[30];

int main(void)
{
/* freopen("c:\\a\\630.txt","rb",stdin); */

int dummy;

dummy=scanf("%d", &a);
assert(dummy==1);
b = a;
while(a--)
scanf("%s", &voca[in++]);

while( scanf("%s", test) && strcmp(test,"END") ){

for(i=0; test; i++)
intP[ (test-'a') ]++;

printf("Anagrams for: %s\n", test );

found=0;
l2 = strlen(test);

a=-1;
int f=1;

while( ++a<b ){
l1 = strlen(voca[a]);

if( l2 != l1 )continue;

for(hh=i=0; voca[a]; i++)
tr[ h[hh]=(voca[a]-'a') ]++, hh++;

i = hh;

while(hh--)
if(tr[ h[hh] ]!=intP[ h[hh] ])break;

if(hh==-1)
printf("%3d) %s\n", f++, voca[a]) ,found++;

for(hh=0; hh<i; hh++) h[hh]=tr[ h[hh] ] = 0;
}
for(i=0; i<30; i++) intP = 0;

if( !found )
printf("No anagrams for: %s\n", test );
}
return 0;
}

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### 630 -> Anagrams (II)

Greetings!
I think I've got enough WAs with this one already
What's the critical input for this problem?
How long is the vocabulary going to be?
Is the statement
All words are lowercase (word END means end of data - it is NOT a test word). You can assume all words are not longer than 20 characters.
true?
Is this the correct format?:

Code: Select all

``````Anagrams for: tola
1) atol
2) lato
3) tola
...
102) tlao``````
Is this a goo I/O?
Input:

Code: Select all

``````8
lato
atol
microphotographics
rata
rola
tara
tola
pies
tola
kola
aatr
photomicrographics
END
2
xxx
kola
tola
kola
aatr
photomicrographics
xxx
END
``````
Output:

Code: Select all

``````Anagrams for: tola
1) atol
2) lato
3) tola
Anagrams for: kola
No anagrams for: kola
Anagrams for: aatr
1) rata
2) tara
Anagrams for: photomicrographics
1) microphotographics
Anagrams for: tola
1) atol
2) lato
3) tola
Anagrams for: kola
1) kola
Anagrams for: aatr
1) rata
2) tara
Anagrams for: photomicrographics
1) microphotographics
Anagrams for: xxx
1) xxx
``````
ANY help or tips for this problem will be really appreciated
Thanks in advance!
_.

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
a) Don't sort the words
b) clear the dictionary after each case
c) Do you know it's a multiple input problem?
I'm always willing to help, if you do the same.

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### Thanks!

Greetings Ryan Pai!
Thanks for the prompt answer!
I'll consider all that now
Wasn't sure if it was Multiple Input or not

Thanks!, and keep posting!

Edited: ACed now Thanks for the help!
Freaking lack of description in the problems...

Keep posting!
_.

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland
Hi !

So, the I/O should be sth like that ?

Input:

Code: Select all

``````8
lato
atol
microphotographics
rata
rola
tara
tola
pies
tola
kola
aatr
photomicrographics
END
2
xxx
kola
tola
kola
aatr
photomicrographics
xxx
END
``````
Output:

Code: Select all

``````Anagrams for: tola
1) lato
2) atol
3) tola
Anagrams for: kola
No anagrams for: kola
Anagrams for: aatr
1) rata
2) tara
Anagrams for: photomicrographics
1) microphotographics
Anagrams for: tola
No anagrams for: tola
Anagrams for: kola
1) kola
Anagrams for: aatr
No anagrams for: aatr
Anagrams for: photomicrographics
No anagrams for: photomicrographics
Anagrams for: xxx
1) xxx
``````
Help me please !

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### More like this...

Greetings!
More like this:

/* See I/O in post below */

Hope it helps
Thanks to Daveon too!

Keep posting!
Last edited by _.B._ on Sat Sep 04, 2004 11:56 pm, edited 1 time in total.
_.

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland
Hi _.B._ !

Are you sure that the "3" in the begining of your sampe input is correct ?
It is not mentioned in the problem specification about counting test cases ?

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### Indeed :)

Hello Wolf!
Indeed it is, and I bet that's why there are SO many WAs for this problem.
It just says in one of the Problemsets that it's a MI problem, but in the description it doesn't mention neither that it has a number of cases in the beginning of the problem, nor that you have to output a blank line between output for each case, nor it is indeed a MI problem
The description of this problem is pretty poor regarding the input it has.
You may try to read the number of cases, then use the FOR, or read the number of cases, ignore it, and then work untill EOF.
I made it both ways
Hope it helps.

Keep posting!
_.

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland
Hi !
Thanx for helping _.B._ but I still have WA (I don't know why). Can you look up my code for some stupid mistakes. My output for input behind is identicaly like yours (I hope ), or maybe you have another test cases ?

Here's the code:

[cpp]
/*remove cause of AC*/
[/cpp]
Last edited by wolf on Sat Sep 04, 2004 9:41 pm, edited 1 time in total.

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### Well, so far...

Greetings!
Well, so far, you could change this:

[cpp] if (strcmp(word.txt,word2.txt)==0)
{
czy++;
cout.width(3);
cout << czy;
cout << ") " << word.original << endl;
}
[/cpp]

To avoid the printing of " ".
But still can't find a critical input for your program.
Will post later.
_.