Thread: problem with to long solution to exam question

  1. #1
    Registered User
    Join Date
    Aug 2001
    Posts
    155

    problem with to long solution to exam question

    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:

    Code:
    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];
                }
            }
        }
        
        // check for more 9 appearances to reserve more letters for one more digit
        for(i = 0 ; i < size ; i++) if(count[i] > 9) extra++;
    
        // allocate the memory for the final array that is going to be printed
        final = (char *) malloc(sizeof(char) * (size * 4) + extra + 1);
        
        j = 0;
        for(i = 0 ; i < size ; i++)
        {
            // insert the letter
            final[i*4 + j] = letters[i];
            // insert space
            final[i*4 + 1 + j] = ' ';
    
            // if more then one digit used for the count of appearances
            if(count[i] > 9)
            {
                // first digit
                final[i*4 + 2 + j] = count[i]/10 + 48;
                j++;
                // second
                final[i*4 + 2 + j] = count[i]%10 + 48 ;
            }
            else final[i*4 + 2 + j] = count[i]  + 48;
            
            // print ; 
            final[i*4 + 3 + j] = ';';
        }
    
        // add terminating character
        final[i*4 + j] = 0;
        // print the result
        printf(" %s ", final);
    }
    can anyone help me come up with more reasonable solution?

  2. #2
    Registered User
    Join Date
    Aug 2001
    Posts
    155
    thanks , although we didn't learned the functions isalpha and upcase (or any other from ctype.h) i'll try to write it without using them. and see the result
    thanks!

    Quote Originally Posted by CommonTater View Post
    Frequency of letters, easy way...

    Code:
    #include <stdio.h>
    #include <string.h>
    
    int main (void)
      { char buff[255] = {0};
         int   count[26] = {0};
         int x,len; 
        
        printf("Enter a sentence:\n" );
        fgets(buff,254,stdin);
    
         len = strlen(buff);
        for (x = 0; x < len; x++)
          if (isalpha(buff[x]))
            count[upcase(buf[x]) - 'A']++;
    
        // now you have the counts you can figure out the rest.
    
    
      return 0; }

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    You need to write test code that calls the function; you are not thinking correctly about having a usable function.

    Does 'A' and 'a' increment the same or different counts?
    How many different letters are possible?
    How is the "final result" returned to the calling program.
    Why do you think the results needs to be sorted?

    Tim S.

  4. #4
    Registered User
    Join Date
    Jun 2011
    Posts
    4,513
    ^ Good advice.

    Also, have you tried to approach this by writing out a flow chart on paper? This will let you see how all the logic would work together, and would help you trim down the logic before writing the code.

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    and no limit of how many different letters are possible and the memory for them has to be dynamically allocated.
    I think the above statement is false; say there is only 26 possible results.
    Why not use an array of 26 items?

    Tim S.

  6. #6
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Frequency of letters, easy way...

    Code:
    #include <stdio.h>
    #include <string.h>
    
    int main (void)
      { char buff[255] = {0};
         int   count[26] = {0};
         int x,len; 
        
        printf("Enter a sentence:\n" );
        fgets(buff,254,stdin);
    
         len = strlen(buff);
        for (x = 0; x < len; x++)
          if (isalpha(buff[x]))
            count[upcase(buf[x]) - 'A']++;
    
        // now you have the counts you can figure out the rest.
    
    
      return 0; }

  7. #7
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Memory leak Warning!

    You never free the variable "final" or pass its address to the calling program. This results in a memory leak.

    Tim S.

  8. #8
    Registered User
    Join Date
    Aug 2001
    Posts
    155
    yes i did not took to account the difference of big and small letters, let's say i would it's not complicated, also final result isn't returned and from the question it isn't implied that it should be returned or saved (no need for pointer to pointer) but this is just small details, the problem is the length of the codethe results has to be alphabetically sorted because the question asks for it, and no limit of how many different letters are possible and the memory for them has to be dynamically allocated.thanks

  9. #9
    Registered User
    Join Date
    Aug 2001
    Posts
    155
    thanks for the warning of the memory leak, didn't notice... that's the reason why such code would never be possible to write in an exam, to long and complicated to write.

  10. #10
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    well i got to something like that
    any thoughts ? can it be improved?
    Yep... use the functions you never learned. The remainder of the solution I presented above should take you no more than 5 or maybe 10 lines.

    I've yet to see any course where the teacher says "Do not read ahead"... Any teacher who would not reward initiative should not be teaching.

    For your actual code, you should look at simplifying your conditionals...
    Code:
        if ((letters[x] >= 'a' && letters[x] <= 'z') || (letters[x] >= 'A' && letters[x] <= 'Z' ))
            if(letters[x] >= 'A' && letters[x] <= 'Z') count[letters[x] - 'A']++;
            else count[letters[x] - 'a']++;
    Way too complicated....

    Code:
    if ((letters[x] >= 'A') && (letters[x] <="Z"))
      count[letters[x] - 'A']++;
    else if  ((letters[x] >= 'a') && (letters[x] <="a"))
      count[letters[x] - 'a']++;
    Gives you the same result....
    Last edited by CommonTater; 07-01-2011 at 04:00 PM.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You're overthinking the memory allocation in this program. Just allocate a buffer that is guaranteed to be large enough, and then once you're done, allocate something smaller and copy the data into there. Doing too much fine grained memory allocation will just lead to inefficiencies, leaks, fragmentation, and far more code than there needs to be.
    You should do away with any realloc calls IMHO.
    Also, don't even involve dynamic memory allocation where you don't need to. There's nothing wrong with having a fixed size array to hold the character frequencies.

    Don't use magic numbers like 48, use the meaningful character value '0' instead. One shouldn't need to refer to an ASCII table to understand your program.

    Using an XOR swap is not doing you any favours either.

    Code:
    		if(!flag)
    		{
    			flag = 0 ;
    This isn't being run on a quantum computer where observing the value might change it. That assignment statement is redundant.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    void foo( char *array, char **ret )
    {
        char *retval = NULL;
        if( array )
        {
            char *alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ", *p = alphabet;
            int alpha[ 52 ] = { 0 }, count = 0;
            
            for( p = array; *p; p++ )
            {
                char *index = strchr( alphabet, *p );
                if( index && alpha[ index - alphabet ]++ == 0 )
                        count++;
            }
            /* let's be lazy */
            if( count )
            {
                retval = malloc( count * 10 );
                if( retval )
                {
                    *retval = '\0';
                    for( count = 0; count < 52; count++ )
                    {
                        if( alpha[ count ] )
                        {
                            char buf[ BUFSIZ ] = {0};
                            sprintf( buf, "%c:%d ", alphabet[ count ], alpha[ count ] );
                            strcat( retval, buf );
                        }
                    }
                }
            }
        }
        if( ret )
            *ret = retval;
    }
    
    int main( void )
    {
        char buf[ BUFSIZ ] = "Hello World!";
        char *p = NULL;
        
        foo( buf, &p );
        printf( "\'%s\'\n", p );
        free( p );
        
        return 0;
    }
    Here's a fun version.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Exam question help: Take 2
    By ÉireKarl in forum C Programming
    Replies: 11
    Last Post: 05-02-2010, 02:12 PM
  2. Exam question help
    By ÉireKarl in forum C Programming
    Replies: 116
    Last Post: 05-02-2010, 12:03 PM
  3. Exam Question - Possible Mistake?
    By Richie T in forum C++ Programming
    Replies: 15
    Last Post: 05-08-2006, 03:44 PM
  4. another exam question
    By rjeff1804 in forum C Programming
    Replies: 4
    Last Post: 02-12-2003, 10:29 PM
  5. exam question
    By teja22 in forum C Programming
    Replies: 2
    Last Post: 10-08-2001, 08:03 PM