yaworsw/euler-manager

---
:id: 300
:name: Protein folding
:url: https://projecteuler.net/problem=300
:content: "In a very simplified form, we can consider proteins as strings consisting
  of hydrophobic (H) and polar (P) elements, e.g. HHPPHHHPHHPH.   \nFor this problem,
  the orientation of a protein is important; e.g. HPP is considered distinct from
  PPH. Thus, there are 2<sup><var>n</var></sup> distinct proteins consisting of <var>n</var>
  elements.\n\nWhen one encounters these strings in nature, they are always folded
  in such a way that the number of H-H contact points is as large as possible, since
  this is energetically advantageous.  \nAs a result, the H-elements tend to accumulate
  in the inner part, with the P-elements on the outside.  \nNatural proteins are folded
  in three dimensions of course, but we will only consider protein folding in <u>two
  dimensions</u>.\n\nThe figure below shows two possible ways that our example protein
  could be folded (H-H contact points are shown with red dots).\n\n ![p300_protein.gif]({{
  images_dir }}/p300_protein.gif)\n\nThe folding on the left has only six H-H contact
  points, thus it would never occur naturally.  \nOn the other hand, the folding on
  the right has nine H-H contact points, which is optimal for this string.\n\nAssuming
  that H and P elements are equally likely to occur in any position along the string,
  the average number of H-H contact points in an optimal folding of a random protein
  string of length 8 turns out to be 850&nbsp;/&nbsp;2<sup>8</sup>=3.3203125.\n\nWhat
  is the average number of H-H contact points in an optimal folding of a random protein
  string of length 15?  \nGive your answer using as many decimal places as necessary
  for an exact result.\n\n"