148 - Anagram checker

[saugata bose]

HELP ME FOR 148
NEED IT URGENTLY

[npelly]

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]

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]

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

Thanks.

[junbin]

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]

I got WA ... please help ...

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

thanks in advanced ...

[El-idioto]

Hi Almost Human,

Do you still have trouble with this problem?

I just got AC, so I can assist you.

[Almost Human]

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]

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]

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]

I used backtracking with pruning and got a pretty decent time, so it shouild be fine.

[howardcheng]

How do you prune?

[dhyanesh]

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]

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

[dhyanesh]

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