trying to solve exam question and getting unreasonable length code, can it be shorter?

atikot

hi, i have C exam next week, so i started solving questions from previous years exams and run into this question, the answer i come up to is far far from having reasonable length, it's too complicated and long , but i can't come up anything shorter. the question is: write a function that receives an array of letters , and a pointer to final result string that hasn't allocated yet, the function supposed to take the array of letters and count the appearance of every letter and make the final result string look like that: received array of letters : "abbacdeefg" result string: "a 2;b 2;c 1;d 1;e 2;f 1;g 1" in the result it should be alphabetically printed here is the code that i wrote, it just doesn't makes sense that this is the actual solution:

void sortarray(char str[],char * final)
{
int i = 1,j, extra = 0;
char * letters, *lerrptr;
int * count, * cerrptr;
int size = 0, flag = 0;

// allocate memory for one array storing letter and one for storing it's appearance
letters = (char \*) malloc(sizeof(char) \* 1);
if(letters == NULL) exit(1);
count = (int \*) malloc(sizeof(int) \* 1);
if(count == NULL) exit(1);

// fill the first letter to array
letters\[0\] = str\[0\];
count\[0\] = 1;
size++;

// scan the whole string
while(str\[i\] != 0)
{
	// initiate flag for new run
	flag = 0;

	for(j = 0 ; j < size ; j++)
	{
		// if the letter already appeared before just increment the count and raise the flag that no new allocating is necessary
		if(str\[i\] == letters\[j\]) 
		{
			count\[j\]++;
			flag = 1;
		}
	}	
	// if the flag of already appeared hasn't been raised make new allocation for new letter
	if(!flag)
	{
		flag = 0 ;
		size++;
		lerrptr = letters;
		letters = (char \*) realloc(letters,sizeof(char) \* size);
		if(letters == NULL)
		{
			free(lerrptr);
			free(count);
			exit(1);
		}
		cerrptr = count;
		count = (int \*) realloc(count,sizeof(int) \* size);
		if(letters == NULL)
		{
			free(cerrptr);
			free(letters);
			exit(1);
		}
		// insert new letter and 1 for the count
		letters\[size-1\] = str\[i\] ;
		count\[size-1\] = 1 ;
			
	}

	i++;
}
	
// bubble sort the letters 
for(i = 0 ; i < size - 1; i++)
{
	for(j = 0 ; j < size - 1 - i ; j++)
	{
		if(letters\[j\] < letters\[j - 1\])
		{
			letters\[j\] ^= letters\[j+1\];
			letters\[j+1\] ^= letters\[j\];
			letters\[j\] ^= letters\[j+1\];
			count\[j\] ^= count\[j+1\];
			count\[j+1\] ^= count\[j\];
			count\[j\] ^= count\[j+1\];
		}
	}

Lost User

It's probably not the shortest possible solution, but to give you an idea maybe:

void sortarray(char str[],char *final)
{
int counter[26] = {0}; // Counter for each of 26 letters, initialised at 0.
int finallength = 0; // Length of the final array.
int i;

// Count occurences.
for(i=0;str\[i\];i++)			// Loop until the terminating zero.
	counter\[str\[i\]-'a'\]++;		// \[str\[i\]-'a'\] is a number 0-25 for the letters a-z.

// Calculate length of final array.
for(i=0;i<26;i++){			// Based on number of occurences for each letter.
	if(counter\[i\])
		finallength += 4;
	if(counter\[i\] > 9)
		finallength ++;
}

// Allocate final array.
final = (char\*)malloc(finallength+1);
final\[0\] = 0;				// Initialise to empty string for strcatting.

// Fill the final array.
char part\[6\];
for(i=0;i<26;i++)
	if(counter\[i\]){
		sprintf(part,"%c %d;",i+'a',counter\[i\]);
		strcat(final,part);
	}
final\[finallength-1\] = 0;		// Remove the last semicolon.

// Print the final array.
printf(final);

}

I copied some behaviour from your code which I would like to comment on though: 1. sortarray receives char * final, i.e. a single pointer. While you can use malloc on this, the function which calls sortarray, does not get its pointer to final updated. To solve this, you would need to pass a double pointer (so char **). 2. We're ignoring the case where a letter may occur more than 99 times in a string. It's probably a fair assumption but it's good to be aware of this. :)

atikot

thanks a lot, yes i know , the question didn't implied i have to save it, (there is a problem i forgot to free it in the end thou) and yes i hope the assumption is fair, the question doesn't actually mentions anything about it

Lost User

Good catch about the free, I forgot it as well :) Good luck with your exam!

atikot

thanks!

Philippe Mori

Since you are using 8 bits characters, one solution would be to allocate an array (of integers) for all possible letters and initialize the whole array to 0. Then for each received letter, you increment the appropiate count (the array is indexed by the ordinal value of the character). After that, you could compute the size of the string to create. As an alternative, this could also be done while receiving letters. Each time a letter is used for the first time, you must add 4 characters. And each time an incrementation cause the number of digit to increment (from 9 to 10, 99 to 100 etc...) add 1 to the required number of digits. Then you can allocate the array. A special case would be when the input is empty. You would have to uses a size of 1 instead of 0. Finally as the indexed array is already in order, you can then write the result skipping any count of 0. An ; need to be added before outputting the letter, space and count except for the first outputted item. Then final '\0' need to be appended at the end. By the way an array and a loop could be used to have the list of value when one digit need to be added. That is an array with values like 10, 100, 1000... up to the desired maximum (1e10 to support 32 bit integer range). In fact, the code would be much simpler and shorter by assuming worst case (256 * 13) assuming a 32 bit program. You then output to that buffer and at the end, you allocated the final string using the actual length (+ 1) of the outputted string. If temporary memory usage is not a problem, it could then easily be done in less than 20 lines of code.

Philippe Mori

Philippe Mori

Handling occurrence greater that 100 would requires a few extra lines.

int test = counter[i];
while (test >= 10)
{
++finalLength;
test /= 10;
}

Your code assume that the input string only contains the 26 lowercase letters. Without specification, we could assumes that we want to support all 256 possible 8 bit characters. Filling of the final array could be a little more effecicient by using strlen and a pointer to the current output position. As a final note, final length is 1 too big except for empty input. Thus is might be possible that the returned string contains one garbage character at the end.

Philippe Mori

Alain Rist

Hi,

atikot wrote:

can anyone help me come up with more reasonable solution?

This is shorter:

// CharCount.c : Defines the entry point for the console application.

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

void CharCount(char str[], char** result)
{
int i;
unsigned int count[256];
if (!strlen(str))
return;
if (*result = (char*)malloc(min(strlen(str), 256) * 8)) // Allocate a 'reasonable' output size
{
char* out = *result;
memset(count, 0, sizeof(count));
for (i = 0; str[i]; i++)
++count[str[i]];
for (i = 0; i < 256; i++)
if (count[i])
out += sprintf(out, "%c %u;", (char)i, count[i]);
*--out = '\0';
}
}

int main()
{
char* out = NULL;
CharCount("abbacdeefg", &out);
if (out)
printf("%s\n", out);
free(out);
}

cheers, AR Code edited after Stefan_Lang[^]'s excellent review.

When the wise (person) points at the moon the fool looks at the finger (Chinese proverb)

modified on Monday, July 4, 2011 10:43 AM

Stefan_Lang · modified on Monday, July 4, 2011 10:43 AM

Two things: 1. If applied to a very long string (e. g. a string containing an entire article or book) the result string becomes unreasonably large. You might want to determine the minimum between strlen(str) and 256 rather than just strlen(str). Also, since you're printing the chars as ints, you'll need at least 6 bytes to store the result of "%c %d;" from sprintf() since the first value can be up to 3 digits long. 2. You're printing the characters as integers, against the specification. (note: you can safely do so since you won't count any nonprintable characters that might meddle with your output). Printing chars as chars will also shorten the output string (see above)

Alain Rist

Hi Stefan, Not sure this quick answer deserved such in-depth excellent review ;) My updated post should address your pertinent issues, and handle empty input string. cheers, AR

When the wise (person) points at the moon the fool looks at the finger (Chinese proverb)