title: Writing a word puzzle solver and getting segmentation fault freeing heap memory
body: <p>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. </p>
  
  <p>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. </p>
  
  <p>Can anyone take a look and explain what is going on? (Code given below) I would be very appreciative!</p>
  
  <pre><code>/**
   * 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 &lt;stdio.h&gt;
  #include &lt;cs50.h&gt;
  #include &lt;string.h&gt;
  
  /*
   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 &lt; 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 &gt; 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 &lt; 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 &lt;= 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 &lt; 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 &lt; 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 &lt; index; i++)
      newData[i] = data[i];
  for(int i = index; i &lt; lengthData - 1; i++)
      newData[i] = data[i + 1];
  
  return newData;
  
  }
  </code></pre>
  
  <p>It might also be worth mentioning that when I tried debugging that the segmentation fault appeared to be happening on a call to <code>malloc()</code> in the implementation of the last function in the code:</p>
  
  <pre><code>// allocating heap memory
  char* newData = malloc((lengthData - 1) * sizeof(char));
  </code></pre>