Euler300.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Starting paths for dynamically getting all paths.\n",
    "# We can fix the first two vertex of the path, because if we picked a different \n",
    "# position for the second vertex it would have rotational symmetry to the path starting with (0,0),(1,0).\n",
    "# This will reduce the number of paths to check.\n",
    "L1 = [[[{(0,0)},(0,0)]],[[{(0,0),(1,0)},(0,0),(1,0)]]]\n",
    "\n",
    "# Returns one of the four possible coordinates for the next vertex on the path, num selects between them.\n",
    "def NextTuple(path, num): \n",
    "    return [(path[-1][0]+1, path[-1][1]), (path[-1][0], path[-1][1]+1), (path[-1][0]-1, path[-1][1]), (path[-1][0], path[-1][1]-1)][num]\n",
    "\n",
    "# Returns the number of contact points for the last vertex in the path.\n",
    "def LastContacts(path):\n",
    "    return ((path[-1][0]+1, path[-1][1]) in path[0]) + ((path[-1][0], path[-1][1]+1) in path[0]) + ((path[-1][0]-1, path[-1][1]) in path[0]) + ((path[-1][0], path[-1][1]-1) in path[0])\n",
    "\n",
    "# Returns the number of neighbors that \"item\" has in the set \"items\"\n",
    "def NumNeighbors(item, items):\n",
    "    return ((item[0]+1, item[1]) in items) + ((item[0], item[1]+1) in items) + ((item[0]-1, item[1]) in items) + ((item[0], item[1]-1) in items)\n",
    "\n",
    "# Returns the number of H-H contact points for a specific protein on a specific path\n",
    "def TotalNumContacts(path, protein):\n",
    "    aminoset = {path[i+1] for i in range(len(protein)) if protein[i]==\"1\"}\n",
    "    return sum([NumNeighbors(amino, aminoset) for amino in aminoset])//2\n",
    "\n",
    "# Dynamically generates a list of all possible paths.\n",
    "# Currently the filter is filtering out too many paths.\n",
    "# If the filter is commented out it will work correctly.\n",
    "# I am working on figuring out a better filter.\n",
    "def GetPaths(L, N): \n",
    "    while len(L) <= N: \n",
    "        L.append([L[-1][j]+[NextTuple(L[-1][j], i)] for j in range(len(L[-1])) for i in range(4) if NextTuple(L[-1][j], i) not in L[-1][j][0]])\n",
    "        L[-1] = list(map(lambda x: [x[0] | {x[-1]}] + x[1:] , L[-1]))\n",
    "        \n",
    "        # Filter out bad paths by number of contact points.\n",
    "        #C = [LastContacts(path) for path in L[-1]]\n",
    "        #MaxC = max(C)\n",
    "        #L[-1] = [L[-1][i] for i in range(len(C)) if C[i] == MaxC]\n",
    "\n",
    "# Simple way to display a path.        \n",
    "def DisplayPath(path):  \n",
    "    MaxX = max(path[0], key = lambda x: x[0])[0]\n",
    "    MaxY = max(path[0], key = lambda x: x[1])[1]\n",
    "    MinX = min(path[0], key = lambda x: x[0])[0]\n",
    "    MinY = min(path[0], key = lambda x: x[1])[1]\n",
    "    \n",
    "    display = [ \" \".join([str(path.index((X,Y))) if (X,Y) in path[0] else \"-\" for X in range(MinX, MaxX+1)]) for Y in range(MinY, MaxY+1)]\n",
    "    \n",
    "    for item in display: print(item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer for N = 8 is 3.3203125\n",
      "Wall time: 896 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "N = 8\n",
    "\n",
    "GetPaths(L1,N-1)\n",
    "\n",
    "# All leading and trailing 0's can be removed from the protein,\n",
    "# and then you can think of it as a protein of a shorter length. Reducing the amount of computation.\n",
    "proteins = [bin(i)[2:] for i in range(2**N)]\n",
    "    \n",
    "average = sum([max([TotalNumContacts(path,protein) for path in L1[len(protein)-1]]) for protein in proteins])/2**N\n",
    "#maxcontactlist =[max([TotalNumContacts(path,protein) for path in L1[len(protein)-1]]) for protein in proteins]\n",
    "\n",
    "print(\"Answer for N =\",N, \"is\", average)\n",
    "\n",
    "#for path in L1[N-1]:\n",
    "#    print()\n",
    "#    DisplayPath(path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}