Writing a word puzzle solver and having a problem with freeing heap memory. Would really appreciate some help!

Question

I am having some trouble with heap memory. I am writing some code 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 only up to the start of week 5 in CS50 so heap memory is fairly new to me and hopefully someone can explain and anyone with similar question can learn too!

Answer 1

When I tried to run your program, it ran for a long time before finally segfaulting. I put in a print statement to count the number of calls to your checkPermutations function, and it was more than 1.5 million in some of my runs before I ctrl-c'd out of it.

I haven't analysed your code to see where the segfault is happening, because, quite honestly, the algorithm you've used (with permutations/combinations) is not the best. A permutation-based approach may work in some circumstances (where the size of the dictionary is much larger than the possible permutations), but in this example with 9 characters, you have 9! = 362,880 possibilities. Yet the dictionary is just under 100k words.

Out of curiousity, when you say it runs if you remove those calls to free, how long does it actually take?

A much quicker solution in this scenario would be to do a linear search of the dictionary itself, comparing each word to the letters that are given to see if the word can be made.

This type of solution will be return the answer in the order of milliseconds while using much less memory.

If you are interested, here's a version I did: countdown.c

I "over-commented" it so I hope it's understandable.