## 148 - Anagram checker

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

Moderator: Board moderators

saugata bose
New poster
Posts: 3
Joined: Wed Aug 21, 2002 12:49 pm
Location: bangladesh

### 148 - Anagram checker

HELP ME FOR 148
NEED IT URGENTLY
saugata

npelly
New poster
Posts: 2
Joined: Mon Sep 02, 2002 2:58 pm

### 148 wrong answer?

I am getting wrong answer for anagrams 148.

One thing I am unsure of, is a dictionary word allowed to appear twice in the anagram soln

eg
INPUT:
A
#
AA
#
OUTPUT:
AA = A A
or is there no output??

However I have submitted solutions both allowing repeated dictionary words and not allowing them and they both came back WA.

Any strange cases to check for?

I have made sure that I dont include dictionary words that appear in the phrase.

-Nick

PS
for what its worth, heres my code:
[c]
#include <stdio.h>
#include <string.h>

typedef struct {
char word[21];
int count[26];
} WORD;
WORD dict[2001];
int avail[2000];

int num;
int find[26];
int use[2000];
int used;

char line[201];

void recurse() {
int total[26];
int i, j;
int start;
int equal = 1;
for (i=0; i<26; i++) {
total = 0;
for (j=0; j<used; j++) {
total += dict[use[j]].count;
}
if (total > find) return;
if (total != find) equal = 0;
}

if (equal && used != 0) {
printf("%s = ", line);
for (i=0; i<used; i++) {
printf("%s", dict[use].word);
if (i != used-1) printf(" ");
}
printf("\n");
return;
}

/* add a word */
if (used == 0) start = 0;
else start = use[used-1]+1;
for (use[used] = start; use[used] < num; use[used]++) {
if (avail[used]) {
used++;
recurse();
used--;
}

}
}

int main() {

int i, j, k;
char inword[21];
int s;

num = 0;
while (1) {
scanf("%s", dict[num].word);
if (strchr(dict[num].word, '#') != NULL) break;
for (i=0; i<26; i++) dict[num].count = 0;
for (i=0; i<strlen(dict[num].word); i++) {
dict[num].count[dict[num].word - 'A']++;
}
num++;
}

while (1) {
for (i=0; i<26; i++) find[i] = 0;
for (i=0; i<num; i++) avail[i] = 1;

fgets(line, 200, stdin);
line[strlen(line)-1] = (char)NULL;
if (strchr(line, '#') != NULL) break;

/* mark not avail and make find */
s = 0;
while (1) {
if (sscanf(&line[s], "%s", inword) != 1) break;
s += strlen(inword) + 1;

for (i=0; i<num; i++)
if (strcmp(inword, dict[i].word) == 0) avail[i] = 0;

for (i=0; i<strlen(inword); i++) {
find[inword[i] - 'A']++;

}
}

/* look for find = count + count */
for (i=0; i<num; i++) use[i] = 0;
used = 0;
recurse();

}

}

[/c]

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
The same word might be reused, yes. But you fail the check for anagrams identical with words in the dictionary. The following input
EE
E
#
EE
E E
E
#
should yield output
EE = E E
E E = EE

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

### Anagram Checker

Is This Problem can be solved with recursive,
Why I always got Time Limit Execeded ???
Is there other method ?

Thanks.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
Yarin wrote:The same word might be reused, yes. But you fail the check for anagrams identical with words in the dictionary. The following input
EE
E
#
EE
E E
E
#
should yield output
EE = E E
E E = EE

According to a staff of the online judge, you cannot reuse a word in the dictionary....

Anyway, I have a few pieces of code, one implements no duplication of words, one implements strictly no duplication and either way, I get WA.

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

### 148 - Anagram Checker

I got WA ... please help ...

any special case ?
Anybody can give me more sample input ?

thanks in advanced ...

El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands
Hi Almost Human,

Do you still have trouble with this problem?

I just got AC, so I can assist you.

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm
Yes, please.

I have several question :
1. Does a word in the dictionary can be used more than once to form an anagram ?

e.g. :
dictionary :
A
input :
AA
output :
A A <-- is it possible ?

2. Is it possible to have 2 identic words in a dictionary ?

e.g. :
dictionary :
A
A
BBB
input :
AA
output :
???? <-- what should be the output then ?

If you are to busy, you can send me, your executable file to : an@bluejack.binus.ac.id

thank you for your attention ...

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
Almost Human wrote:Yes, please.

I have several question :
1. Does a word in the dictionary can be used more than once to form an anagram ?

e.g. :
dictionary :
A
input :
AA
output :
A A <-- is it possible ?

2. Is it possible to have 2 identic words in a dictionary ?

e.g. :
dictionary :
A
A
BBB
input :
AA
output :
???? <-- what should be the output then ?

If you are to busy, you can send me, your executable file to : an@bluejack.binus.ac.id

thank you for your attention ...

1.
A
#
AA
#

gives no output.

2.
A
A
BBB
#
AA
#

gives

AA = A A

hope that helps.

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

### 148 Anagram Checker TLE

I had a solution that I did many years ago, but it now runs too long after they changed the data a long time ago (now I finally decided to look at it again). I used backtracking before...is the "right" solution dynamic programming? I didn't go that way because I have to write all the solutions, but I guess I can use DP to prune?

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
I used backtracking with pruning and got a pretty decent time, so it shouild be fine.

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am
How do you prune?

dhyanesh
New poster
Posts: 5
Joined: Sat Feb 26, 2005 5:28 am

### 148 Anagram checker

Hi

Can someone please provide same I/O for this problem ... I have tried almost everything. I do check if the words are present in original phrase

My input:

Code: Select all

``````A
ABC
ACB
AND
DEF
DXZ
E
E
EE
K
KX
LJSRT
LT
PT
PTYYWQ
Y
YWJSRQ
ZD
ZZXY
#
AA
ZZXY ABC DEF
SXZYTWQP KLJ YRTD
ZZXY YWJSRQ PTYYWQ ZZXY
LJSRT K PTYYWQ DXZ
EE
E E
E
ABC
TL TP
#
``````
My Output:

Code: Select all

``````ZZXY ABC DEF = ACB DEF ZZXY
SXZYTWQP KLJ YRTD = DXZ K LJSRT PTYYWQ
SXZYTWQP KLJ YRTD = DXZ K LT PT Y YWJSRQ
SXZYTWQP KLJ YRTD = KX LJSRT PTYYWQ ZD
SXZYTWQP KLJ YRTD = KX LT PT Y YWJSRQ ZD
LJSRT K PTYYWQ DXZ  = DXZ K LT PT Y YWJSRQ
LJSRT K PTYYWQ DXZ  = KX LJSRT PTYYWQ ZD
LJSRT K PTYYWQ DXZ  = KX LT PT Y YWJSRQ ZD
EE = E E
E E = EE
ABC = ACB
TL TP = LT PT
``````
Is it possible to reuse a dictionary words? .. I have read conflicting posts about both.

Also does it have multiple input or just once ?

Thanks..

-Dhyanesh

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
My solution outputs similiar output with one exception:

EE = E E

This line above is not printed. I think because of 'E' which appear in input twice, but should be counted only once.

Best regards
DM
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)

dhyanesh
New poster
Posts: 5
Joined: Sat Feb 26, 2005 5:28 am

### Still WA

Code: Select all

``````ZZXY ABC DEF = ACB DEF ZZXY
SXZYTWQP KLJ YRTD = DXZ K LJSRT PTYYWQ
SXZYTWQP KLJ YRTD = DXZ K LT PT Y YWJSRQ
SXZYTWQP KLJ YRTD = KX LJSRT PTYYWQ ZD
SXZYTWQP KLJ YRTD = KX LT PT Y YWJSRQ ZD
LJSRT K PTYYWQ DXZ  = DXZ K LT PT Y YWJSRQ
LJSRT K PTYYWQ DXZ  = KX LJSRT PTYYWQ ZD
LJSRT K PTYYWQ DXZ  = KX LT PT Y YWJSRQ ZD
E E = EE
ABC = ACB
TL TP = LT PT
``````
Still WA ... do you or anyone have any tricky I/O which I might be missing?

Do you want me to post my code ?? I could do it if you want

Thanks

-Dhyanesh