My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.

       
#include <iostream>
       
#include <iomanip>
       
#include <vector>
       
#include <set>
       
 
       
// operate on a 30x30 grid, each protein starts at (Center, Center)

       
const unsigned int GridSize = 30;
       
const unsigned int Center   = GridSize / 2;
       
typedef char Grid[GridSize][GridSize];
       
 
       
// indicator for an empty cell

       
const char Empty = 0;
       
// protein's first element is 'a', then 'b', ..., 'e'

       
const char First = 'a';
       
 
       
// optimized number of hydrophobic contacts per protein

       
std::vector<unsigned int> best;
       
// number of direct contacts between immediate neighbors (minimum value, independent of folding)

       
std::vector<unsigned int> direct;
       
// keep track of past contact points sequences (detect duplicates / strong similiarities)

       
std::set<std::vector<unsigned int>> visited;
       
 
       
// check each protein whether the current grid is better than anything seen before

       
void optimize(unsigned int length, const Grid& grid)
       
{
       
  // list of neighbors, each pair is stored as a bitmask
       
  std::vector<unsigned int> contacts;
       
 
       
  // count how many occupied cells I've seen
       
  unsigned int seen = 0;
       
 
       
  // extremely straight foldings can't be optimal because they have only contacts between directs neighbors
       
  unsigned int ignoreStraight = 9; // empirical value
       
  if (length != 15)
       
    ignoreStraight = 0;
       
 
       
  // walk through the grid
       
  for (unsigned int i = ignoreStraight; i + 1 + ignoreStraight < GridSize; i++)
       
    for (unsigned int j = ignoreStraight; j + 1 + ignoreStraight < GridSize; j++)
       
    {
       
      // already visited the entire protein ?
       
      if (seen + 1 >= length)
       
        break;
       
 
       
      // ignore empty cells
       
      if (grid[i][j] == Empty)
       
        continue;
       
 
       
      // one more element visited
       
      seen++;
       
      // get its index (0..length-1)
       
      auto from = grid[i][j] - First;
       
 
       
      // check right neighbor
       
      if (grid[i + 1][j] != Empty)
       
      {
       
        auto to = grid[i + 1][j] - First;
       
        if (from != to + 1 && from + 1 != to)
       
          contacts.push_back((1 << from) | (1 << to));
       
      }
       
      // check bottom neighbor
       
      if (grid[i][j + 1] != Empty)
       
      {
       
        auto to = grid[i][j + 1] - First;
       
        if (from != to + 1 && from + 1 != to)
       
          contacts.push_back((1 << from) | (1 << to));
       
      }
       
    }
       
 
       
  // no contacts at all ? (besides direct contact)
       
  if (contacts.empty())
       
    return;
       
 
       
  // already had a similar folding ? (same contact points)
       
  if (visited.count(contacts) != 0)
       
    return;
       
  visited.insert(contacts);
       
 
       
  // for each protein check whether more hydrophobic contacts exist
       
  auto numProteins = 1 << length;
       
  for (auto protein = 0; protein < numProteins; protein++)
       
  {
       
    // at least all direct contacts
       
    auto found = direct[protein];
       
 
       
    // can't beat the previous record ?
       
    if (found + contacts.size() <= best[protein])
       
      continue;
       
 
       
    // count other contact points
       
    for (auto contactMask : contacts)
       
    {
       
      // are both neighbors hydrophobic ?
       
      if ((protein & contactMask) == 0)
       
        found++;
       
    }
       
 
       
    // better than before ?
       
    if (best[protein] < found)
       
      best[protein] = found;
       
  }
       
}
       
 
       
// generate recursive all possible layouts

       
void search(unsigned int current, unsigned int length, Grid& grid, unsigned int x, unsigned int y)
       
{
       
  // protein completely placed on grid ?
       
  if (current == length)
       
  {
       
    // don't check layouts mirrored along y-axis
       
    if (y >= Center)
       
      optimize(length, grid);
       
 
       
    // done
       
    return;
       
  }
       
 
       
  // try all possible continuations
       
  // go left
       
  if (grid[x - 1][y] == Empty)
       
  {
       
    grid[x - 1][y] = current + First;
       
    search(current + 1, length, grid, x - 1, y);
       
    grid[x - 1][y] = Empty;
       
  }
       
 
       
  // go right
       
  if (grid[x + 1][y] == Empty)
       
  {
       
    grid[x + 1][y] = current + First;
       
    search(current + 1, length, grid, x + 1, y);
       
    grid[x + 1][y] = Empty;
       
  }
       
 
       
  // go down
       
  if (grid[x][y - 1] == Empty)
       
  {
       
    grid[x][y - 1] = current + First;
       
    search(current + 1, length, grid, x, y - 1);
       
    grid[x][y - 1] = Empty;
       
  }
       
 
       
  // go up
       
  if (grid[x][y + 1] == Empty)
       
  {
       
    grid[x][y + 1] = current + First;
       
    search(current + 1, length, grid, x, y + 1);
       
    grid[x][y + 1] = Empty;
       
  }
       
}
       
 
       
int main()
       
{
       
  unsigned int length = 15;
       
  std::cin >> length;
       
 
       
  // allocate memory
       
  auto numProteins = 1 << length;
       
  direct.resize(numProteins, 0);
       
  best  .resize(numProteins, 0);
       
 
       
  // count direct neighboring hydrophobic elements in each protein
       
  for (auto protein = 0; protein < numProteins; protein++)
       
  {
       
    for (unsigned int i = 0; i < length - 1; i++)
       
      if ((protein & (3 << i)) == 0) // 3 => bitmask of two bits
       
        direct[protein]++;
       
 
       
    best[protein] = direct[protein];
       
  }
       
 
       
  // create an empty grid
       
  Grid grid;
       
  for (unsigned int x = 0; x < GridSize; x++)
       
    for (unsigned int y = 0; y < GridSize; y++)
       
      grid[x][y] = Empty;
       
 
       
  // always start in the middle
       
  unsigned int x = Center;
       
  unsigned int y = Center;
       
  grid[x][y] = First;
       
  // due to symmetries I can also place the second element
       
  x++;
       
  grid[x][y] = First + 1;
       
 
       
  // generate all layouts and then call optimize()
       
  search(2, length, grid, x, y);
       
 
       
  // count optimized contact points
       
  unsigned int sum = 0;
       
  for (auto x : best)
       
    sum += x;
       
  // display average
       
  std::cout << std::setprecision(14)
       
            << sum / double(best.size()) << std::endl;
       
  return 0;
       
}

This solution contains 30 empty lines, 42 comments and 4 preprocessor commands.