anagram program

meriororen · 07-01-2009, 09:15 AM

Hi there people,

I need a little help here with a program I made, its about finding how many pairs of anagram there are in a given input (can be from keyboard, or a text data). The number of words given are not known before EOF.

for example data.txt :

Code:

atm
mat
rat
art
spit
pits
run

will give me 4 (assuming that "run" is a pair of anagram to itself)
words are all in lowercase and no space,

here is my program :

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 33


int areAnags(char *str1, char *str2){
	int i,temp;
	int count1[256] = {0}; 
	int count2[256] = {0};
	
	if(strlen(str1) != strlen(str2)) return 0;	

	for(i=0;i<strlen(str1);i++){
		temp = (int)str1[i];
		count1[temp]++;
	}
	for(i=0;i<strlen(str2);i++){
		temp = (int)str2[i];
		count2[temp]++;
	}

	for(i=97;i<=122;i++){
		if(count1[i] != count2[i]) return 0;	
	}
	
	return 1;
}


int main(void){
	char input[MAX];
	int count = 0,i;
	char **anagram = NULL;
	
	anagram = malloc(sizeof(char *));
	anagram[0] = malloc(MAX * sizeof(char));
	if(anagram == NULL){
		printf("Insufficient memory available.\n");		
		return EXIT_FAILURE;
	}

	while(scanf("%s", input) != EOF){	
		anagram[0] = strdup(input);
		for(i=0;i<sizeof(anagram);i++){
			if(areAnags(anagram[i],input) == 0){
				anagram = realloc(anagram, (count+1) * sizeof(char *));
				anagram[count] = malloc(MAX * sizeof(char));

				if(anagram == NULL || anagram[count] == NULL){
						printf("Insufficient memory available.\n");		
						return EXIT_FAILURE;		
				}
					
				anagram[count] = strdup(input);
				count++;
			}
		}
	}

	for(i=0;i<count;i++)	
		printf("%d\n", sizeof(anagram));
	

	for(i=0;i<sizeof(anagram);i++) 
		free(anagram[i]);
	free(anagram);
	return 0;
}

The program compiled successfully, but when I run it, it keeps getting me a Segmentation Faullt, I am using a bit confusing pointers here, so I am not quite sure where I did the mistake..
I tried gdb, and it gave me this :

Code:

Program received signal SIGSEGV, Segmentation fault.
0xb7de7613 in strlen () from /lib/tls/i686/cmov/libc.so.6

Thanks in advance.
meriororen.

MK27 · 07-01-2009, 09:56 AM

I'm not sure where your problem is but one thing I would note (which might help to narrow this down) is that:

Code:

if(strlen(str1) != strlen(str2)) return 0;

It looks to me like these two numbers will not change for the duration of the function, so you should really put them into two variables at the beginning:

Code:

int len1 = strlen(str1), len2 = strlen(str2);

This is because the processor has to perform all the calculations everytime you call strlen. That includes every single iteration in a for loop:

Code:

for(i=0;i<strlen(str1);i++){

So if the loop runs ten times, you have ten strlen() calls instead of 0 calls with

Code:

for(i=0;i<len1;i++){

And, as mentioned, debugging gets a little easier when you minimize unnecessary function calls.

**Salem** · 07-01-2009, 10:02 AM

Well that looks like it crashed in a strlen function.

- check your use of strlen()
- think about whether any of them could have passed a bad pointer
- think about whether any of them could have been passed a valid pointer, but without a \0 in a reasonable place.

quzah · 07-01-2009, 12:45 PM

Code:

for(i=0;i<sizeof(anagram);i++){

What is this supposed to be doing?

Quzah.

meriororen · 07-02-2009, 12:18 AM

Quote:

Originally Posted by quzah

Code:

for(i=0;i<sizeof(anagram);i++){

What is this supposed to be doing?

Quzah.

it supposed to check whether the angram of the next given "input" is already inside the anagram[] array..

I check areAnags() in another program (i simply put two words as the input) and it worked, the strlen() function only exist inside areAnags(), not in main, I don't know why it worked on another program but not this.

also, I erased

Code:

 anagram[0] = strdup(input);

from the while loop, it was stupid mistake.

I put the strlen inside len1 and len2 variable, thanks to mk27.

Thanks for the advices,
However, I am still lost. I am working on it, but need some more advices. thanks

meriororen · 07-02-2009, 12:44 AM

ok, I found the segfault reason,

sizeof(anagram) give out 4 (as sizeof(char *) is 4).. I changed it..

but another problem came, no matter what input I gave, the result keep showing 1. ~___~

here is my current program :

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 33



int areAnags(const char *str1,const char *str2){
	int i,temp;
	int count1[256] = {0}; 
	int count2[256] = {0};
	int len1 = strlen(str1), len2 = strlen(str2);

	if(len1 != len2) return 0;	

	for(i=0;i<len1;i++){
		temp = (int)str1[i];
		count1[temp]++;
	}
	for(i=0;i<len2;i++){
		temp = (int)str2[i];
		count2[temp]++;
	}

	for(i=97;i<=122;i++){
		if(count1[i] != count2[i]) return 0;	
	}
	
	return 1;
}


int main(void){
	char input[MAX];
	int count = 0,i,anagsize;
	char **anagram = NULL;
	
	anagram = malloc(sizeof(char *));
	anagram[0] = malloc(MAX * sizeof(char));
	if(anagram == NULL){
		printf("Insufficient memory available.\n");		
		return EXIT_FAILURE;
	}

	anagram[0] = " ";

	anagsize = sizeof(anagram) / sizeof(char *);
	
	while(scanf("%s", input) != EOF){	
		for(i=0;i<anagsize;i++){
			if(areAnags(anagram[i],input) == 0){
				anagram = realloc(anagram, (count+1) * sizeof(char *));
				anagram[count] = malloc((strlen(input)+1) * sizeof(char));

				if(anagram == NULL || anagram[count] == NULL){
						printf("Insufficient memory available.\n");		
						return EXIT_FAILURE;		
				}
					
				anagram[count] = strdup(input);
				count++;
			}
		}
	}

	printf("%d\n", anagsize);
	

	for(i=0;i<anagsize;i++)
		free(anagram[i]);
	free(anagram);
	return 0;
}

linuxdude · 07-02-2009, 07:29 AM

Your loop isn't right.

Code:

while(scanf("%s", input) != EOF){	
		for(i=0;i<anagsize;i++){
			if(areAnags(anagram[i],input) == 0){

Look at how they are getting compared. For example let's say the input is

Code:

hey
you
uoy
you
there

This is what your code is comparing everytime

Code:

hey
anagram[0] =  
input = hey
you
anagram[0] = hey
input = you
uoy  
anagram[0] = hey
input = uoy
you
anagram[0] = hey
input = you
there
anagram[0] = hey
input = there
1

The first loop compares hey to nothing! Then it never compares all of the input, just anagram[0] to input. Also, malloc calls are safer if you don't use

Code:

sizeof(type)

but rather

Code:

sizeof(pointer)

So your code would look like this

Code:

	anagram[0] = malloc(MAX * sizeof(char)); // not this
anagram[0] = malloc(MAX*sizeof(*anagram[0])); // but this

This is so if you change the type of your variable your code will still run. The FAQ is interesting.

meriororen · 07-03-2009, 03:44 AM

I finally could get this program to work :

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 33



int areAnags(const char *str1,const char *str2){
	int i,temp;
	int count1[256] = {0};
	int count2[256] = {0};
	int len1 = strlen(str1), len2 = strlen(str2);

	if(len1 != len2) return 0;	

	for(i=0;i<len1;i++){
		temp = (int)str1[i];
		count1[temp]++;
	}
	for(i=0;i<len2;i++){
		temp = (int)str2[i];
		count2[temp]++;
	}

	for(i=97;i<=122;i++){
		if(count1[i] != count2[i]) return 0;	
	}
	
	return 1;
}

int isInside(char **array, char *string, int s){
	int i=0,in;

	while(i<s){
		if(areAnags(array[i], string) == 1){
			in = 1;
			break;
		}else{
			in = 0;
		}
		i++;
	}

	return in;
}

int main(void){
	char input[MAX];
	int count = 0,i,a_size=1;
	char **anagram;
	
	anagram = malloc(sizeof(*anagram));
	anagram[0] = malloc(MAX * sizeof(*anagram[0]));
	
	if(anagram == NULL || anagram[0] == NULL){
		printf("Insufficient memory available.\n");		
		return EXIT_FAILURE;
	}


	while(scanf("%s", input) != EOF){	
		if(isInside(anagram, input, a_size) == 0){
			anagram = realloc(anagram, (count+1) * sizeof(*anagram));
			anagram[count] = malloc((strlen(input)+1) * sizeof(*anagram[count]));

			if(anagram == NULL || anagram[count] == NULL){
					printf("Insufficient memory available.\n");		
					return EXIT_FAILURE;		
			}
				
			strncpy(anagram[count], input, strlen(input)+1);
			count++;
			a_size = count;
			printf("%s<--\n", anagram[count-1]);
		}
	}

	printf("%d\n", a_size);
	
	for(i=0;i<count-1;i++)
		free(anagram[i]);
	free(anagram);
	return 0;
}

but it seems like its lacking speed, I tried inputting word list txt file containing about 234000 words, it keeps looping till 20+ minutes run under my netbook (asus eeePC atom 1.6GHz, 1GB ram).

I wonder how to add speed to my program...

ZaC · 07-03-2009, 06:07 AM

I'd change the function to find anagrams... I sudgest you to sort each letter of the word, than if a sorted word like this already exists (strcmp on a list of anagrams, if you can use hash table this is a good choose) you don't store else you will store this new word. It should be faster.

nonoob · 07-03-2009, 02:43 PM

I wish I could help. Even just for my own amusement. Sounds like an intriguing problem but your statement of needing pairs of anagrams has me stumped. What is the program supposed to do exactly? Usually an anagram finder figures out if there are words existing containing the desired letters... "pairs" makes no sense to me.

meriororen · 07-04-2009, 11:53 PM

Sorry about the lack of explanation,

I am not too good to express things in English :P

The program was meant to find groups of anagrams in given words, e.g. :

Code:

file
life
run
break
brake

which would be :

{file, life}
{break, brake}
{run}

and then, the program outputs:
3 (there are 3 groups of anagrams)

Eventually, I start things over because the last program I made crazily compared everything inside the array to the next input,,

I decided to sort the inputted words into binary trees (I learnt this in one night without sleeping >.<) and succeeded reducing the execution time to 4seconds (233514 words -> 213566 groups)

thanks people!

ZaC · 07-05-2009, 08:32 AM

it is a good choose, but why don't you think about my suggestion?
You should not save each word but just one for each group...
From the example:

Quote:

file
life
run
break
brake

here you have to save only
efil
nru
abekr
Theese are the first word of each founded group but with sorted letters.
If you sort each word before to look for it over the tree, for each group you will get the same word... I think that this saves time and memory

nonoob · 07-06-2009, 12:52 PM

Thanks for the additional explanation. Looks like you shouldn't need binary trees and whatnots. Here's how I would do it.

Since the input is guaranteed to contain contiguous lists of possible pairs of anagrams...

1 - Just save the first incoming word in the count1 array as you've done. (Clever!)
2 - For subsequent possible anagram word, first check if the word is the same length...
then
3- Subtract out the corresponding letters from the count1 array - if any entries try to go below zero, the anagram test fails. [means: a letter in the new word was never in the old word]

Any words failing the anagram test is candidate for possible pair of new anagram.

07-01-2009, 09:56 AM	#2
MK27 subminimalist Join Date: Jul 2008 Location: NYC Posts: 3,943	I'm not sure where your problem is but one thing I would note (which might help to narrow this down) is that: Code: if(strlen(str1) != strlen(str2)) return 0; It looks to me like these two numbers will not change for the duration of the function, so you should really put them into two variables at the beginning: Code: int len1 = strlen(str1), len2 = strlen(str2); This is because the processor has to perform all the calculations everytime you call strlen. That includes every single iteration in a for loop: Code: for(i=0;i<strlen(str1);i++){ So if the loop runs ten times, you have ten strlen() calls instead of 0 calls with Code: for(i=0;i<len1;i++){ And, as mentioned, debugging gets a little easier when you minimize unnecessary function calls. __________________ Accuracy and integrity mean nothing if you don't make it past the censors...PYTHAGORAS
MK27 is online now

07-01-2009, 10:02 AM	#3
Salem and the hat of vanishing Join Date: Aug 2001 Location: The edge of the known universe Posts: 21,214	Well that looks like it crashed in a strlen function. - check your use of strlen() - think about whether any of them could have passed a bad pointer - think about whether any of them could have been passed a valid pointer, but without a \0 in a reasonable place. __________________ If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut. Up to 8Mb PlusNet broadband from only £5.99 a month!
Salem is offline

07-01-2009, 12:45 PM	#4
quzah +++ OK NO CARRIER Join Date: Oct 2001 Posts: 10,258	Code: for(i=0;i<sizeof(anagram);i++){ What is this supposed to be doing? Quzah. __________________ Hundreds of thousands of dipshits can't be wrong. Are you up for the suck?
quzah is offline

07-02-2009, 07:29 AM	#7
linuxdude Registered User Join Date: Mar 2003 Location: Louisiana Posts: 926	Your loop isn't right. Code: while(scanf("%s", input) != EOF){ for(i=0;i<anagsize;i++){ if(areAnags(anagram[i],input) == 0){ Look at how they are getting compared. For example let's say the input is Code: hey you uoy you there This is what your code is comparing everytime Code: hey anagram[0] = input = hey you anagram[0] = hey input = you uoy anagram[0] = hey input = uoy you anagram[0] = hey input = you there anagram[0] = hey input = there 1 The first loop compares hey to nothing! Then it never compares all of the input, just anagram[0] to input. Also, malloc calls are safer if you don't use Code: sizeof(type) but rather Code: sizeof(pointer) So your code would look like this Code: anagram[0] = malloc(MAX * sizeof(char)); // not this anagram[0] = malloc(MAXsizeof(anagram[0])); // but this This is so if you change the type of your variable your code will still run. The FAQ is interesting.
linuxdude is offline

07-03-2009, 06:07 AM	#9
ZaC Lost in the C Join Date: Jun 2008 Location: Italy Posts: 47	I'd change the function to find anagrams... I sudgest you to sort each letter of the word, than if a sorted word like this already exists (strcmp on a list of anagrams, if you can use hash table this is a good choose) you don't store else you will store this new word. It should be faster. __________________ Sorry for my bad English and also for my bad programming style... ZaC'ZaCoder (?!) Last edited by ZaC; 07-03-2009 at 10:15 AM.
ZaC is offline

07-03-2009, 02:43 PM	#10
nonoob Registered User Join Date: Sep 2008 Location: Toronto, Canada Posts: 507	I wish I could help. Even just for my own amusement. Sounds like an intriguing problem but your statement of needing pairs of anagrams has me stumped. What is the program supposed to do exactly? Usually an anagram finder figures out if there are words existing containing the desired letters... "pairs" makes no sense to me.
nonoob is offline

07-04-2009, 11:53 PM	#11
meriororen Registered User Join Date: Dec 2008 Posts: 20	Sorry about the lack of explanation, I am not too good to express things in English :P The program was meant to find groups of anagrams in given words, e.g. : Code: file life run break brake which would be : {file, life} {break, brake} {run} and then, the program outputs: 3 (there are 3 groups of anagrams) Eventually, I start things over because the last program I made crazily compared everything inside the array to the next input,, I decided to sort the inputted words into binary trees (I learnt this in one night without sleeping >.<) and succeeded reducing the execution time to 4seconds (233514 words -> 213566 groups) thanks people! __________________ Baka nanka janai. Shoshinsha tte iu mon da.
meriororen is offline

07-06-2009, 12:52 PM	#13
nonoob Registered User Join Date: Sep 2008 Location: Toronto, Canada Posts: 507	Thanks for the additional explanation. Looks like you shouldn't need binary trees and whatnots. Here's how I would do it. Since the input is guaranteed to contain contiguous lists of possible pairs of anagrams... 1 - Just save the first incoming word in the count1 array as you've done. (Clever!) 2 - For subsequent possible anagram word, first check if the word is the same length... then 3- Subtract out the corresponding letters from the count1 array - if any entries try to go below zero, the anagram test fails. [means: a letter in the new word was never in the old word] Any words failing the anagram test is candidate for possible pair of new anagram.
nonoob is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
This is a simple program.. Help me please I think it has an error..	lesrhac03	C Programming	4	02-21-2008 10:39 AM
Using variables in system()	Afro	C Programming	8	07-03-2007 12:27 PM
BOOKKEEPING PROGRAM, need help!	yabud	C Programming	3	11-16-2006 11:17 PM
airport Log program using 3D linked List : problem reading from file	gemini_shooter	C Programming	3	03-04-2005 02:46 PM
My program, anyhelp	@licomb	C Programming	14	08-14-2001 10:04 PM