156 - Ananagrams

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

psachin
New poster
Posts: 1
Joined: Sun Nov 10, 2002 9:02 pm

156 - Ananagrams

Hi,
I tried to solve prob 156 but it takes a lot of time to generate permutations for long words. can anyone help me out with this problem.
here's the permutation code that i am using to generate permutations.

[cpp]

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
void permute(string a, int b, int pos,vector<string> dict, bool & match, vector<int> & loc);
void swap(string &a,int i,int b);
void main(){

vector<string> dict;
vector<string> lDict;
vector<int> pos;
vector<string> result;
string temp;
int i;
bool temp1 = false,found;

cin >> temp;
while(temp!="#"){
dict.push_back(temp);
cin >> temp;
}
pos.resize(dict.size());
for(i=0;i<dict.size();i++){
temp = dict;
transform (temp.begin(),temp.end(), temp.begin(), tolower);
lDict.push_back(temp);
pos = 0;
}

for(i=0;i<dict.size();i++){
temp = dict;
temp1 = false;
transform (temp.begin(),temp.end(), temp.begin(), tolower);
permute(temp,0,i,lDict,temp1, pos);

}

for(i=0;i<dict.size();i++){
if(pos ==0)
result.push_back(dict);
}
sort(result.begin(),result.end());
for(i=0;i<result.size();i++)
cout << result << endl;

}

void permute(string a, int b, int pos,vector<string> dict, bool & match, vector<int> & loc){
if(loc[pos] ==1 ) return;
if(match) { return ; }
if(b == a.size()-1){
return ;

}

else {
permute(a,b+1,pos , dict,match,loc);
for(int i=b+1;i< a.size();i++){
swap(a,i,b);
// cout << a<< endl;
for(int j=0; j<dict.size();j++){
if(j==pos) continue;

if(a==dict[j]) {
loc[pos] = 1;loc[j] = 1;
match = true; return; }
}

permute(a,b+1,pos,dict,match,loc);
}
}

}

void swap(string &a,int i,int b){
char temp = a;
a=a;
a= temp;
}

[/cpp]

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
Hi
I think, that you shouldn't create any permutations here.
There is an algorithm which will allows you to test, if it is possible to create word from others words. For each element it will work O(1), but not as O(N!);
whole problem 156 can be solved in n*logn, because you have to sort all ananagrams.
If I wouldn't have to sort ananagrams, problem 156 would took O(N) time

my currect algorithm does everything in 0.002s

hts
New poster
Posts: 8
Joined: Sat Feb 22, 2003 2:56 am

Compile Error ?!?!? (Problem 156)

I got Compile Error, but I didn't received any e-mail telling me what went wrong.

Code: Select all

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

int	assinaturas[1000];
char	words[1000][20];
int	N;
FILE	*fin = stdin;

int	cmp(const char *str1, const char *str2)
{
return strcmp(str1, str2);
}

int	pot(int base, int exp)
{
int	ret = 1;

while(exp--)
ret *= base;

return ret;
}

int	assinatura(char *string)
{
int	i, ret = 0;

for(i = strlen(string)-1; i >= 0; i--)
ret += pot(2, tolower(string[i]) - 'a');

return ret;
}

int	main()
{
int	i, j, ok;

while(1)
{
fscanf(fin, "%s", &words[N][0]);

if(words[N][0] == '#')
break;

N++;
}

qsort(&words[0][0], N, 21, cmp);

for(i=0; i<N; i++)
assinaturas[i] = assinatura(&words[i][0]);

for(ok = 1, i=0; i<N; i++)
{
for(j=0; j<N; j++)
{
if(j == i)
continue;

if(assinaturas[i] == assinaturas[j])
{
ok = 0;
break;
}
}

if(ok)
printf("%s\n", &words[i][0]);
}
}
``````

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Code: Select all

``````Info :Making...
Info :test.cpp: rebuild due to dependency test.cpp
Info :  test.cpp: cache age 10:44:05 AM 2/28/2003, disk age 10:09:29 PM 3/1/2003
Info :Compiling E:\BC5\BIN\test.cpp
Error:  test.cpp(30,29):Call to undefined function 'tolower'
Error:  test.cpp(49,35):Cannot convert 'int (*)(const char *,const char *)' to 'int (*)(const void *,const void *)'
Error:  test.cpp(49,35):Type mismatch in parameter '__fcmp' in call to 'qsort(void *,unsigned int,unsigned int,int (*)(const void *,const void *))'``````
Is this what you wanted?

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
( Borland C++ 5.02 )
tolower requies "#include <ctype.h>" according to my compiler.

This is how I usually use qsort:

[cpp]int fcmp(const void *in1,const void *in2){
for(int i = 0; i < 100; i++){
if(((char *)in1) < ((char *)in2)) return -1;
if(((char *)in1) > ((char *)in2)) return 1;
if(!((char *)in1)) return 0;
}
return 0;
}
......
qsort(&index,index_num,100,&fcmp);
......[/cpp]

kareltje333
New poster
Posts: 2
Joined: Fri May 16, 2003 1:07 pm

Prbl. 156 cant get right answer

I've written this program in C to solve problem 156.

I get wrong answer with this. With the given example input i get the correct answer all the time. I have no clue whats wrong.

Anybody can help?

[c]

#include <stdio.h>
#include <ctype.h>
char sorted_words[1000][20];
char original_words[1000][20];
char ananagrams[1000][20];
char temp[1][20];
int number_of_words;
int number_of_ananagrams;
void sort(int number);
int find_equal_word(int compare_word);
void find_ananagrams();
void print_ananagram();
void swap_word(int word_1,int word_2);
void sort_equal_letter_word(int word_number_1, int word_number_2);
void sort_ananagrams(int word_number,int letternumber);

/* =============MAIN function ==============*/
main()
{
int i,j,k,a;
/* scan words in sorted_words[]*/
j=0;i=0;
scanf("%s", sorted_words);
while( strcmp(sorted_words,"#") )
{i++;
scanf("%s", sorted_words);
}
number_of_words=i;
sorted_words[0]=0;
/* put words in original_words[] */
for(k=0;k<i;k++)
for (j=0;j<20;j++)
{original_words[k][j]=sorted_words[k][j];
sorted_words[k][j]=tolower(sorted_words[k][j]);
}
/* sort sorted_words[] */
for(k=0;k<i;k++)
for (j=0;j<20;j++)
{sort(k);
}

find_ananagrams();
sort_ananagrams(0,0);
print_ananagram();
}
/* EINDE ========MAIN ========================*/

/* ===================== sort of the matrix sorted_words[][]*/
void sort(int number)
{
int m=0, temp=0;
while(sorted_words[number][m+1]!=0)
{
if(sorted_words[number][m]<=sorted_words[number][m+1])
{m++;}
else
{temp=sorted_words[number][m];
sorted_words[number][m]=sorted_words[number][m+1];
sorted_words[number][m+1]=temp;
sort(number);
}
}
}
/* END ============== sort of the matrix sorted_words[][]*/

/* =============== compare word with other words, returns zero if equal word found */
int find_equal_word(int compare_word)
{
int word_number, result;
word_number=0;

while (word_number<=number_of_words)
{
result=(strcmp(sorted_words[compare_word],sorted_words[word_number]));
if (result==0)
{
if (compare_word!=word_number)
{
return(0);
}
}
if (result!=0)
{
result=1;
}
word_number++;
}
return(result);
}
/* END ============ compare word with other words, returns zero if equal word found */

/* ============= print result ==============*/
void print_ananagram()
{
int j;
for (j=0;j<number_of_ananagrams;j++)
{
printf("%s\n",ananagrams[j]);
}
}
/* ============= print result ==============*/

/* ============= find ananagrams, move to ananagrams matrix ==============*/
void find_ananagrams()
{
int j; int word_number;int equal_or_not;
for (word_number=0;word_number<number_of_words;word_number++)
{
equal_or_not=find_equal_word(word_number);
if (equal_or_not==1)
{
for (j=0;j<20;j++)
{ananagrams[number_of_ananagrams][j]=original_words[word_number][j];
}
number_of_ananagrams++;
}
}
}
/* ============= find ananagrams, move to ananagrams matrix ==============*/

/* =========== swap words at place 1 en 2========*/
void swap_word(int word_1,int word_2)
{
strcpy(temp[1],ananagrams[word_1]);
strcpy(ananagrams[word_1],ananagrams[word_2]);
strcpy(ananagrams[word_2],temp[1]);
}
/* END ======= swap words at place 1 en 2========*/

/* =========sort words with first letter(s) euqual */
void sort_equal_letter_word(int word_number_1, int word_number_2)
{
int letter_number=0;

while(ananagrams[word_number_1][letter_number]==ananagrams[word_number_2][letter_number])
{
letter_number++;
}
if (ananagrams[word_number_1][letter_number]!='\0')
{
if (ananagrams[word_number_1][letter_number]>ananagrams[word_number_2][letter_number])
{swap_word(word_number_1,word_number_2);
}
}
}
/* END ======sort words with first letter(s) euqual */

/*=========== alphabetical sort of matrix with ananagrams ======*/
void sort_ananagrams(int word_number,int letternumber)
{
while(word_number<number_of_ananagrams-1)
{
if(ananagrams[word_number][letternumber]>ananagrams[word_number+1][letternumber])
{swap_word(word_number,word_number+1);
sort_ananagrams(0,0);
}
if(ananagrams[word_number][letternumber]<ananagrams[word_number+1][letternumber])
{
word_number++;
}
if(ananagrams[word_number][letternumber]==ananagrams[word_number+1][letternumber])
{
sort_equal_letter_word(word_number,word_number+1);
word_number++;
}
}
}
/* END ======== alphabetical sort of matrix with ananagrams ======*/

[/c]

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

156 Ananagrams What is the output

Hi. I try to solve this problem.
I sort all ananagrams and find in them the relative ones. It is easy. But I can't get what output must be?

For example if we have words ACM, aCm, AcM what must be output?
just ACM or
ACM
aCm
AcM

I read statement but I did not find anything explaining it.
I need some help.

Thanks.
_____________
NO sigNature

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
my accecpted program does not produce any output for your input:
ACM
aCm
AcM
#

but for input:
acm
ACM
ABC
#

output is:
ABC

hope it will help

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
And what about inputs:
A
a
#

A
#

A a a a a a A A A
#
_____________
NO sigNature

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
Here is input:

Code: Select all

``````A a a A a a B B B C Hello HELLO Hi REpLy
ladder came tape soon leader acme RIDE lone Dreis peat
ScAlE orb  eye  Rides dealer  NotE derail LaCeS  drIed
noel dire Disk mace Rob dries
#``````
My output is:

Code: Select all

``````C
Disk
Hi
NotE
derail
drIed
eye
soon``````
Is it correct?
_____________
NO sigNature

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
yes, correct.

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
i tried a tiny input :

a B #

incorrect output :
B
B
if u can think of it .. u can do it in software.

nibbler
New poster
Posts: 22
Joined: Fri Jun 04, 2004 10:30 pm
I got AC like this:
i had both original and sorted words ( first turned them all to lower case, then used qsort () to sort them ). Then I compared them all.
This is the code, hope it helps:

Code: Select all

``````// ACM 156
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 1000

class word {
public:
char orig[25];
char work[25];
};

word array[SIZE];

char string[25]={0};
char anagram[SIZE]={0};
int size=0;

int v_cmp(const void *a,const void *b)
{
return strcmp((*(word*)a).orig,(*(word*)b).orig);
}

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

char * lower_case(char *s)
{
int len=strlen(s);
for (int i=0;i<len;i++)
if (s[i]>='a') s[i]-='a'-'A';
return s;
}

void solve(void)
{
// Turn into lower case
for (int i=0;i<size;i++)
strcpy(array[i].work,lower_case(array[i].work));
// mini-sort -> work
for (int i=0;i<size;i++)
qsort(array[i].work,strlen(array[i].work),sizeof(char),m_cmp);
// big-sort -> elements of array by orig field
for (int i=0;i<size;i++)
qsort(array,size,sizeof(word),v_cmp);
// checking for anagrams
for (int i=0;i<size;i++) {
if (strlen(array[i].orig)==1) {
printf ("%s\n",array[i].orig);
continue;
}
for (int j=i+1;j<size;j++) {
if (strcmp(array[i].work,array[j].work)==0) {
anagram[i]=anagram[j]=1;
break;
}
}
if (anagram[i]==0)
printf ("%s\n",array[i].orig);
}
}

int main()
{
do {
scanf ("%s",string);
if (string[0]=='#') break;
strcpy(array[size].orig,string);
strcpy(array[size].work,string);
size++;
} while (string[0]!='#');
solve();
return 0;
}``````

Ankur Kumar Nayak
New poster
Posts: 4
Joined: Thu Feb 03, 2005 9:16 pm
Location: chennai
Contact:

prob 156 compile error

Hi,
I have written this code which seems to compile and run on my pc but gives a compile error on the online-judge...can anyone help....

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

void sort( char str[1100][30], int num);

int main()
{
char words[1100][30];
int len[1100];
char temp1[30],temp2[30];
char ananagrams[1100][30];
int i=0,k,m,n,j=0;
int f=1;
int flag = 0;
int x;

scanf("%s",words);
len = strlen(words);

while(strcmp(words,"#"))
{
scanf("%s",words[++i]);
len = strlen(words);
}

for(j=0;j<i;j++)
{
x=0;
for(k=j+1;k<=i;k++) {
if( len[k] == len[j] && len[k] != 0 ) {
strcpy(temp1,words[k]);
strcpy(temp2,words[j]);
f=1;
for(m=0;m<len[k];m++)
{
flag = 0;
for(n=0;n<len[k];n++)
{
if(temp1[m]==temp2[n] || temp1[m]==temp2[n]+32 || temp1[m]+32==temp2[n]) {
flag = 1;
temp2[n] = 200;
break;
}
}
if(flag!=1)
{
f=0;
break;
}
}

if(f==1)
{
len[k] = 0;
x = 1;
}
}
}
if(x==1)
len[j] = 0;
}

m=0;
for(j=0;j<i;j++)
{
if(len[j] != 0) {
strcpy(ananagrams[m++], words[j]);
}
}

sort(ananagrams,m);
return 0;
}

void sort( char str[1100][30], int len)
{
int i,j;
int arr[1100];
int m,n;
int min;
int num[1100];
int count;

for(i=0;i<len;i++)
num = 1;
for(i=0;i<len;i++)
{
count = 0;
while(1) {
if(count == 0) {
j=0;
while(num[j++] != 1);
min = j-1;

n=0;
arr[n++] = min;
for(;j<len;j++) {
if(num[j] != 0) {
if(str[j][count] < str[min][count]) {
min = j;
n=0;
arr[n++] = j;
}
else if(str[j][count] == str[min][count]) {
arr[n++] = j;
}
}

}
}
else
{
min = arr[0];

n = 0;
arr[n++] = min;
j=1;
while(j<m) {
if(str[arr[j]][count] < str[min][count]) {
min = j;
n=0;
arr[n++] = j;
}
else if(str[arr[j]][count] == str[min][count]) {
arr[n++] = j;
}
j++;
}
}
m=n;

if(n==1) {
printf("%s\n",str[arr[0]]);
num[arr[0]] = 0;
break;
}
//put num[j] = 0 while printing...
count++;
}
}
}
If at first you don't succeed.....you are a programmer

Ankur Kumar Nayak
New poster
Posts: 4
Joined: Thu Feb 03, 2005 9:16 pm
Location: chennai
Contact:
I think I figured out the problem....It was because of the "//" comment i had put....But the codeis giving wrong answer now....Any ideas what is wrong with my code....[/url][/b][/quote][/code]
If at first you don't succeed.....you are a programmer