Jeremy Tung - 1 month ago 9
C Question

# Writing a word puzzle solver and getting segmentation fault freeing heap memory

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 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 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));
``````

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!