156 - Ananagrams

[psachin]

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]

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]

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]

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]

( 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]

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]

[Farid Ahmadov]

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.

[Subeen]

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

[Farid Ahmadov]

And what about inputs:
A
a
#

A
#

A a a a a a A A A
#

[Farid Ahmadov]

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
REpLy
derail
drIed
eye
ladder
soon

Is it correct?

[Subeen]

yes, correct.

[jagadish]

i tried a tiny input :

a B #

incorrect output :
B
B

[nibbler]

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]

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

[Ankur Kumar Nayak]

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]