Jeremy Tung Jeremy Tung - 2 months ago 9
C Question

Writing a word puzzle solver and getting segmentation fault. Seems to be to do with freeing heap memory. Can someone take a look?

I am having some trouble with heap memory. I am writing some code in C to solve word puzzles - (from a game called Countdown here in the UK). The game is that you are given 9 letters and the goal is to make the longest word you can.

My code works (although I haven't fully tested it) if I comment out all the calls to free() but when I put the free calls in I get a segmentation fault. I have run valgrind and get error messages like "Address 0x9cbe627 is 7 bytes inside a block of size 9 free'd" and "invalid read of size 1." I have tried looking online to find out about this and I still don't understand.

Can anyone take a look and explain what is going on? (Code given below) I would be very appreciative!

/**
* Program to solve word puzzles from the TV show Countdown. Asks for 9
* letters for input and then prints out the
* maximum score and an example word of that score
*/

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

/*
uses recursion to iterate over combinations of size "length" from
data[] of size "lengthData." Stores combinations generated in
combination[] and permutations in permutation[]. For each combination
calls checkPermutations to iterate over all permutations
of the combination checking against a dcitionary for word matches
returning true if a match is found
*/
bool checkForWords(char data[], int lengthData, int length, char
combination[], int lengthCombination, char permutation[]);

/**
* takes in an array - (in practice combination[] from main()) and
* iterates through all the permutations of the array storing
* generated permutations in permutation[] by using recursion. For
* each checks against a dictionary for word match. Returns true
* when match is found
*/
bool checkPermutations(char data[], int lengthData, char permutation[],
int lengthPermutation);

/**
* takes an array of some length and an index and then retruns a
* pointer to an array on the heap that is the same but with the
* elements at the index and to the left removed and then remaining
* elements "shifted down"
*/
char* removeLeftOfIndex(char data[], int lengthData, int index);

/**
* takes an array of some length and index position and returns a
* pointer to an array on the heap that has the element removed
* and remaining elements "shifted down"
*/
char* removeElementAtIndex(char data[], int lengthData, int index);

int main(void)
{
char letters[9];

// getting letters
for (int i = 0; i < 9; i++)
{
printf("Please enter letter %i: ", i + 1);
letters[i] = GetChar();
}

// formatting
printf("\n");


// iterating over the length of word to look for starting at 9 and
decrementing
for (int i = 9; i > 0; i--)
{
char* data = malloc(9 * sizeof(char));
char* permutation = malloc(10 * sizeof(char));
char* combination = malloc(9 * sizeof(char));

for (int j = 0; j < 9; j++)
data[j] = letters[j];

// checks to see if there is a word of length i
if (checkForWords(data, 9, i, combination, i, permutation) == true)
{
printf("Max score: %i\nExample word: %s\n", i, permutation);
free(permutation);
return 0;
}

free(permutation);
}

// no words found
printf("Max score: 0\nNo words can be made\n");
return 0;
}

bool checkForWords(char data[], int lengthData, int length, char
combination[], int lengthCombination, char permutation[])
{
// base recursive case
if (length == 0)
{
free(data);

// checks for permutations for the fixed combination
return checkPermutations(combination, lengthCombination, permutation, lengthCombination);
}

else
{
// generating combination by fixing one element and the recursively generating and checking
for (int j = 0; j <= lengthData - length; ++j)
{
// fixes one element
combination[lengthCombination - length] = data[j];

// recursive part
if (checkForWords(removeLeftOfIndex(data, lengthData, j), lengthData - j - 1, length - 1, combination,
lengthCombination, permutation) == true)
{
free(data);
return true;
}
}

free(data);
return false;
}
}

bool checkPermutations(char data[], int lengthData, char permutation[], int lengthPermutation)
{

// base recursive case
if (lengthData == 0)
{
// null character for printing string later
permutation[lengthPermutation] = '\0';


// checking against dictionary - make this much faster with binary search!!!!
FILE* dictionary= fopen("/usr/share/dict/words", "r");
char word[15];
while (fgets(word, sizeof(word), dictionary) != NULL)
{
// checks to see if match
if (strncmp(permutation, word, lengthPermutation) == 0)
{
fclose(dictionary);
free(data);
return true;
}

}

// not in dictionary
fclose(dictionary);


free(data);
return false;

}

else
{
// generating permutations and checking for words by fixing one element and then using recursion.
for (int j = 0; j < lengthData; j++)
{
// fixing element
permutation[lengthPermutation - lengthData] = data[j];

// recursive part
if (checkPermutations(removeElementAtIndex(data, lengthData, j), lengthData - 1, permutation, lengthPermutation) == true)
{
free(data);
return true;
}

}
free(data);
return false;
}
}

char* removeLeftOfIndex(char data[], int lengthData, int index)
{
// allocating heap memory
char* newData = malloc((lengthData - index - 1) * sizeof(char));

// loop to copy relevant parts
for (int j = 0; j < lengthData - index - 1; j++)
newData[j] = data[j + index + 1];

return newData;
}

char* removeElementAtIndex(char data[], int lengthData, int index)
{
// allocating heap memory
char* newData = malloc((lengthData - 1) * sizeof(char));

// loops to copy relevant parts
for (int i = 0; i < index; i++)
newData[i] = data[i];
for(int i = index; i < lengthData - 1; i++)
newData[i] = data[i + 1];

return newData;

}


It might also be worth mentioning that when I tried debugging that the segmentation fault appeared to be happening on a call to malloc() in the implementation of the last function in the code:

// allocating heap memory
char* newData = malloc((lengthData - 1) * sizeof(char));


Thanks in advance for any help. I am relatively new to programming so heap memory is fairly new to me and hopefully someone can explain and anyone with similar question can learn too!

Answer

Your code is quite a spider's web of memory allocation and freeing. I've reworked it so the memory allocation make a little more sense (to me, anyway.) Having a subroutine free memory of its caller is odd -- the opposite is OK, having a caller free the return result of a subroutine.

Although the basic case (exact match for word in dictionary) seems to work, I can't say I was able to test the other possibilities so this code may need more debugging. But it's not complaining about memory errors:

/**
 * Program to solve word puzzles from the TV show Countdown. 
 * Asks for 9 letters for input and then prints out the
 * maximum score and an example word of that score
 */

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

/**
 uses recursion to iterate over combinations of size "length" from 
 data[] of size "lengthData." Stores combinations generated in
 combination[] and permutations in permutation[]. For each combination
 calls checkPermutations to iterate over all permutations
 of the combination checking against a dictionary for word matches 
 returning true if a match is found
 */
bool checkForWords(char data[], int lengthData, int length, char combination[], int lengthCombination, char permutation[]);

/**
 * takes in an array - (in practice combination[] from main()) and
 * iterates through all the permutations of the array storing
 * generated permutations in permutation[] by using recursion. For 
 * each checks against a dictionary for word match. Returns true
 * when match is found
 */
bool checkPermutations(char data[], int lengthData, char permutation[], int lengthPermutation);

/**
 * takes an array of some length and an index and then returns a
 * pointer to an array on the heap that is the same but with the
 * elements at the index and to the left removed and then remaining 
 * elements "shifted down"
 */
char *removeLeftOfIndex(char data[], int lengthData, int index);

/**
 * takes an array of some length and index position and returns a
 * pointer to an array on the heap that has the element removed
 * and remaining elements "shifted down"
 */
char *removeElementAtIndex(char data[], int lengthData, int index);

#define LETTER_COUNT (9)

int main(void)
{
    char letters[LETTER_COUNT];

    // getting letters
    for (int i = 0; i < LETTER_COUNT; i++)
    {
        printf("Please enter letter %i: ", i + 1);
        letters[i] = GetChar();
    }

    // formatting
    printf("\n");

    bool success = false;

    char *data = malloc(LETTER_COUNT);
    char *permutation = malloc(LETTER_COUNT + 1);
    char *combination = malloc(LETTER_COUNT);

    // iterating over the length of word to look for starting at 9 and decrementing
    for (int i = LETTER_COUNT; i > 0; i--)
    {
        (void) strncpy(data, letters, LETTER_COUNT);

        // checks to see if there is a word of length i
        if (checkForWords(data, LETTER_COUNT, i, combination, i, permutation))
        {
            printf("Max score: %i\nExample word: %s\n", i, permutation);
            success = true;
            break;
        }
    }

    if (!success)
    {
        printf("Max score: 0\nNo words can be made\n");
    }

    free(data);
    free(permutation);
    free(combination);

    return EXIT_SUCCESS;
}

bool checkForWords(char data[], int lengthData, int length, char combination[], int lengthCombination, char permutation[])
{
    // base recursive case
    if (length == 0)
    { 
        // checks for permutations for the fixed combination
        return checkPermutations(combination, lengthCombination, permutation, lengthCombination);
    }

    // generating combination by fixing one element and the recursively generating and checking
    for (int j = 0; j <= lengthData - length; ++j)
    { 
        // fixes one element
        combination[lengthCombination - length] = data[j];

        // recursive part
        char *reduced = removeLeftOfIndex(data, lengthData, j);
        if (checkForWords(reduced, lengthData - j - 1, length - 1, combination, lengthCombination, permutation))
        {
            free(reduced);
            return true;
        }
        free(reduced);
    }

    return false;
}

bool checkPermutations(char data[], int lengthData, char permutation[], int lengthPermutation)
{
    // base recursive case
    if (lengthData == 0)
    { 
        // null character for printing string later
        permutation[lengthPermutation] = '\0';

        // checking against dictionary - make this much faster with binary search!!!!
        FILE* dictionary= fopen("/usr/share/dict/words", "r");
        char word[64];

        while (fgets(word, sizeof(word), dictionary) != NULL)
        { 
            // checks to see if match
            if (strncmp(permutation, word, lengthPermutation) == 0)
            { 
                fclose(dictionary);
                return true;
            }
        }

        // not in dictionary
        fclose(dictionary);
        return false;
    }

    // generating permutations and checking for words by fixing one element and then using recursion.
    for (int j = 0; j < lengthData; j++)
    { 
        // fixing element
        permutation[lengthPermutation - lengthData] = data[j];

        // recursive part
        char *reduced = removeElementAtIndex(data, lengthData, j);
        if (checkPermutations(reduced, lengthData - 1, permutation, lengthPermutation))
        {
            free(reduced);
            return true;
        }
        free(reduced);
    }

    return false;
}

char *removeLeftOfIndex(char data[], int lengthData, int index)
{ 
    // allocating heap memory
    char *newData = malloc(lengthData - index - 1);

    // loop to copy relevant parts
    for (int j = 0; j < lengthData - index - 1; j++)
    {
        newData[j] = data[j + index + 1];
    }

    return newData;
}

char *removeElementAtIndex(char data[], int lengthData, int index)
{ 
    // allocating heap memory
    char *newData = malloc(lengthData - 1);

    // loops to copy relevant parts
    for (int i = 0; i < index; i++)
    {
        newData[i] = data[i];
    }

    for (int i = index; i < lengthData - 1; i++)
    {
        newData[i] = data[i + 1];
    }

    return newData;
}

Good luck and I hope this helps!