simulASAP_ALAP_Nathan.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "pycharm": {
     "is_executing": false
    }
   },
   "outputs": [],
   "source": [
    "\n",
    "import numpy as np\n",
    "\n",
    "G=2\n",
    "S=1\n",
    "T=3\n",
    "C=12\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "def succALAP(x,n):\n",
    "    tasktype=x[0]\n",
    "    i=x[1]\n",
    "    j=x[2]\n",
    "    k=x[3]\n",
    "    listsucc=[]\n",
    "    if tasktype==0:\n",
    "        if i>1:\n",
    "            y=(1,i,i-1,0)\n",
    "            listsucc.append(y)\n",
    "        else:\n",
    "            y=(4,0,0,0)\n",
    "            listsucc.append(y)            \n",
    "    if tasktype==1:\n",
    "        if j >=2:\n",
    "            y=(1,i,j-1,0)\n",
    "            listsucc.append(y)\n",
    "        y=(2,j,i,0)\n",
    "        listsucc.append(y)       \n",
    "    if tasktype==2:\n",
    "        y=(0,i,0,0)\n",
    "        listsucc.append(y)\n",
    "        if i>1:\n",
    "            y=(3,i,j,i-1)\n",
    "            listsucc.append(y)\n",
    "    if tasktype==3:\n",
    "        if k>1:\n",
    "            y=(3,i,j,k-1)\n",
    "            listsucc.append(y)\n",
    "        y=(2,k,j,0) \n",
    "        listsucc.append(y)\n",
    "        y=(2,k,i,0) \n",
    "        listsucc.append(y)\n",
    "\n",
    "    return listsucc\n",
    "\n",
    "\n",
    "\n",
    "# task type 0: POTRF 1:SYRK 2:TRSM 3: GEMMS\n",
    "# all have 4 values, but the last one is used for GEMMS only (-;\n",
    "# a task is a 4-uple and everything will be stored in dictionnaries later\n",
    "# succalap is the set of successors in the alap schedule, ie the predecessors in the original graph\n",
    "\n",
    "\n",
    "\n",
    "def succASAP(x,n):\n",
    "    tasktype=x[0]\n",
    "    i=x[1]\n",
    "    j=x[2]\n",
    "    k=x[3]\n",
    "    listsucc=[]\n",
    "    if tasktype==0:\n",
    "        if i<n:\n",
    "            for j in range(i+1,n+1,1):\n",
    "                y=(2,i,j,0)\n",
    "                listsucc.append(y)\n",
    "        else:\n",
    "            y=(4,0,0,0)\n",
    "            listsucc.append(y)  \n",
    "    \n",
    "    \n",
    "    if tasktype==1:\n",
    "        if j<i-1:\n",
    "            y=(1,i,j+1,0)\n",
    "            listsucc.append(y)\n",
    "        else:\n",
    "            y=(0,i,0,0)\n",
    "            listsucc.append(y)\n",
    "\n",
    "           \n",
    "            \n",
    "    if tasktype==2:\n",
    "        if i<=n-1:\n",
    "            for k in range(i+1,j):\n",
    "                y=(3,k,j,i)\n",
    "                listsucc.append(y)\n",
    "            for k in range(j+1,n+1):\n",
    "                y=(3,j,k,i)\n",
    "                listsucc.append(y)\n",
    "            y=(1,j,i,0)\n",
    "            listsucc.append(y)\n",
    "\n",
    "\n",
    "    if tasktype==3:\n",
    "        if k<i-1:\n",
    "            y=(3,i,j,k+1)\n",
    "            listsucc.append(y)\n",
    "        else:\n",
    "            y=(2,i,j,0)\n",
    "            listsucc.append(y)\n",
    "\n",
    "\n",
    "    return listsucc\n",
    "\n",
    "\n",
    "# duration is just the duration of a task\n",
    "\n",
    "def duration(x):\n",
    "    tasktype=x[0]\n",
    "    if tasktype==0:\n",
    "        duration=C\n",
    "    if tasktype==1:\n",
    "        duration=S        \n",
    "    if tasktype==2:\n",
    "        duration=T\n",
    "    if tasktype==3:\n",
    "        duration=G\n",
    "    return duration\n",
    "\n",
    "durations = [C, S, T, G]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true,
    "pycharm": {
     "is_executing": false
    }
   },
   "outputs": [],
   "source": [
    "def LengthASAP(n,P):\n",
    "\n",
    "    maxi=(G+T+S+C)*n*n*n\n",
    "    mini=-1\n",
    "\n",
    "\n",
    "    #ReadyTasks is the set of tasks that are ready to be processed (all their predecessors have been processed)\n",
    "    # due to limited resources, they might be waiting for resources\n",
    "    ReadyTasks=[]\n",
    "    ReadyTasks.append((0,1,0,0))\n",
    "\n",
    "\n",
    "    #Ltasks is the list of tasks that have not been processed and that are not yet ready\n",
    "    LTasks=[]\n",
    "\n",
    "    #disctionnary Processed provides, for each task, where and when it has been processed\n",
    "    Processed={}\n",
    "    #dictionnary Released provides, for each task, the minimum time when it can be processed (-1 at the beginning), \n",
    "    # given its already scheduled predecessors. The number of remaining predecessors to be \n",
    "    # scheduled is stored in NbSuccASAP={}\n",
    "    Released={}\n",
    "    NbPredASAP={}\n",
    "    # Prio is the priority of the task for the alap.\n",
    "    # at the moment, Prio is just the length of the critical path in ASAP (because I had the values at hand !)\n",
    "    Prio={}\n",
    "\n",
    "    CP=C+(n-1)*(T+S+C)\n",
    "\n",
    "    Released[(0,1,0,0)]=0\n",
    "    NbPredASAP[(0,1,0,0)]=0\n",
    "    Prio[(0,1,0,0)]=CP\n",
    "\n",
    "    # initialization of Prio (critical path in ASAP), Released (-1 at the beginning), \n",
    "    # NbSuccASAP (predecessors in ALAP) \n",
    "\n",
    "    for i in range(1,n+1):\n",
    "        Released[(0,i,0,0)]=mini\n",
    "        Prio[(0,i,0,0)]=C+(n-i)*(T+S+C)\n",
    "    #    Prio[(0,i,0,0)]=n-i\n",
    "    #    Prio[(0,i,0,0)]=i\n",
    "\n",
    "        NbPredASAP[(0,i,0,0)]=1\n",
    "        LTasks.append((0,i,0,0))\n",
    "\n",
    "\n",
    "    for j in range(1,n):\n",
    "        for i in range(j+1,n+1):\n",
    "            Released[(1,i,j,0)]=mini\n",
    "            LTasks.append((1,i,j,0))\n",
    "            if i < n:\n",
    "                Prio[(1,i,j,0)]=(i-j)*S+C+(n-i)*(T+S+C)\n",
    "    #            Prio[(1,i,j,0)]=n-j\n",
    "    #            Prio[(1,i,j,0)]=j            \n",
    "                if j>1:\n",
    "                    NbPredASAP[(1,i,j,0)]=2\n",
    "                else:\n",
    "                    NbPredASAP[(1,i,j,0)]=1\n",
    "\n",
    "            else:\n",
    "                Prio[(1,i,j,0)]=(i-j)*S+C+(n-i)*(T+S+C)\n",
    "    #            Prio[(1,i,j,0)]=n-j \n",
    "    #            Prio[(1,i,j,0)]=j \n",
    "                if j>1:\n",
    "                    NbPredASAP[(1,i,j,0)]=2\n",
    "                else:\n",
    "                    NbPredASAP[(1,i,j,0)]=1\n",
    "\n",
    "                    \n",
    "    for i in range(1,n):\n",
    "        for j in range(i+1,n+1):\n",
    "            LTasks.append((2,i,j,0))\n",
    "            Released[(2,i,j,0)]=mini\n",
    "            Prio[(2,i,j,0)]=(j-i-1)*(T+G)+(n-j+1)*(T+S+C)\n",
    "    #        Prio[(2,i,j,0)]=n-i\n",
    "    #        Prio[(2,i,j,0)]=i\n",
    "            if i>1:\n",
    "                NbPredASAP[(2,i,j,0)]=2\n",
    "            else:\n",
    "                NbPredASAP[(2,i,j,0)]=1\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "    for k in range(1,n-1):\n",
    "        for i in range(k+1,n):\n",
    "            for j in range(i+1,n+1):\n",
    "                LTasks.append((3,i,j,k))\n",
    "                Released[(3,i,j,k)]=mini\n",
    "                Prio[(3,i,j,k)]=(i-k)*G+(j-i-1)*(T + G)+(n-j +1)*(T +S +C)\n",
    "     #           Prio[(3,i,j,k)]=n-k\n",
    "    #            Prio[(3,i,j,k)]=k\n",
    "                if k>1:\n",
    "                    NbPredASAP[(3,i,j,k)]=3\n",
    "                else:\n",
    "                    NbPredASAP[(3,i,j,k)]=2\n",
    "\n",
    "    Released[(0,1,0,0)]=0\n",
    "    NbPredASAP[(0,1,0,0)]=0\n",
    "    Prio[(0,1,0,0)]=CP\n",
    "\n",
    "#    print(\"Prio\",Prio)\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "    #ProcReady[i] is the time when processor P_i is available.\n",
    "\n",
    "    ProcReady=[0]*P\n",
    "\n",
    "\n",
    "\n",
    "    # instant represents the current time\n",
    "    instant=0\n",
    "\n",
    "    while len(ReadyTasks)>0:\n",
    "\n",
    "        for i in range(P):\n",
    "            ProcReady[i]=max(instant,ProcReady[i])\n",
    "#    print('debut',\"\\n\",instant)\n",
    "#    print('ReadyTasks',ReadyTasks)\n",
    "#    print(\"Processed\",Processed)\n",
    "#    print('ProcReady',ProcReady,\"\\n\\n\\n\")\n",
    "\n",
    "#indices is the list of the processors that are ready the soonest\n",
    "        indices = [i for i, x in enumerate(ProcReady) if x == min(ProcReady)]\n",
    "        \n",
    "#nextinstant1 is the next instant when something can happen         \n",
    "\n",
    "        for i in indices:\n",
    "        # first find the highest priority task among the ready ones\n",
    "            if (len(ReadyTasks)>0):\n",
    "                HighestPrio=mini\n",
    "                for task in ReadyTasks:\n",
    "                    if Prio[task] >= HighestPrio:\n",
    "                        if Released[task]<=instant:\n",
    "                            if min(ProcReady)<=instant:\n",
    "                                HighestPrio = Prio[task]\n",
    "                                HPTask=task\n",
    "#                print(\"instant\",instant,\"HPTASK\",HPTask,\"ReadyTasks\",ReadyTasks)\n",
    "            #mark all its successors with one depedendency less        \n",
    "                for task in succASAP(HPTask,n):\n",
    "                    Released[task]=max(Released[task],ProcReady[i]+duration(HPTask))\n",
    "                    NbPredASAP[task]=NbPredASAP[task]-1\n",
    "#                print(\"released\",Released[(0,2,0,0)],NbPredASAP[(0,2,0,0)])\n",
    "#                print(instant)\n",
    "#                print(\"ReadyTasks\",ReadyTasks)\n",
    "        #mark the task processed, update the availability of the associated proc and remove it from some lists    \n",
    "                ProcReady[i]=max(ProcReady[i],instant)+duration(HPTask)\n",
    "                Processed[HPTask]=[i,ProcReady[i]]\n",
    "                ReadyTasks.remove(HPTask)\n",
    "                del Released[HPTask]\n",
    "        #mininstant1 is the next instant when a busy processor will be released\n",
    "\n",
    "        nextinstant=maxi\n",
    "\n",
    "    # if there are no more ready tasks, we should determine the time when something will happen\n",
    "    # ie a task that is not ready yet but will become soon given what has been scheduled (ie no dependencies\n",
    "    # but still running predecessors)\n",
    "    # in this first part, the goal is to find the first instant when a task will become ready\n",
    "#        if len(ReadyTasks)==0:\n",
    "#            print(\"zaza\")\n",
    "        for task in ReadyTasks:\n",
    "            nextinstant=min(nextinstant,Released[task])\n",
    "         \n",
    "        nextinstant=max(min(ProcReady),nextinstant)   \n",
    "        \n",
    "        for task in LTasks:\n",
    "            if task not in ReadyTasks:\n",
    "                if NbPredASAP[task] ==0:\n",
    "                    if task in Released:\n",
    "                        if Released[task] <= nextinstant:\n",
    "                            nextinstant=min(nextinstant,Released[task])\n",
    "#        nextinstant=min(ProcReady,nextinstant)\n",
    "#            print(\"zouzou\")\n",
    "\n",
    "   # once we now this instant (nextinstant) just put the corresponding task(s) into the ready list                       \n",
    "        for task in LTasks:\n",
    "            if task not in ReadyTasks:\n",
    "                if NbPredASAP[task] ==0:\n",
    "                    if task in Released:\n",
    "                        if Released[task] <= nextinstant:                       \n",
    "                            ReadyTasks.append(task)\n",
    "\n",
    "\n",
    "   \n",
    "    #and advance the time until the new instant when something will happen (and in particlar there\n",
    "    #should be a ready task)\n",
    "\n",
    "\n",
    "        instant=max(min(ProcReady),nextinstant)\n",
    "#        print(\"instant a la mise a jour\",instant)\n",
    "\n",
    "\n",
    "        \n",
    "        if (0,n,0,0) in ReadyTasks:\n",
    "            #we reached the first POTRF\n",
    "            break\n",
    "\n",
    "\n",
    "            \n",
    "    Processed[(0,n,0,0)]=[0,max(ProcReady)+C]  \n",
    "\n",
    "#    print(Processed)\n",
    "#    print(\"CP=\",CP,\"endtime=\",max(ProcReady)+C)\n",
    "                \n",
    "    for key in Processed:\n",
    "        Processed[key][1]=max(ProcReady)+C-Processed[key][1]+duration(key)\n",
    "        \n",
    "#    print(Processed)\n",
    "    return(Processed,max(ProcReady)+C)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "pycharm": {
     "is_executing": false
    }
   },
   "outputs": [],
   "source": [
    "def LengthALAP(n,P):\n",
    "\n",
    "    maxi=(G+T+S+C)*n*n*n\n",
    "    mini=-1\n",
    "\n",
    "\n",
    "\n",
    "    #ReadyTasks is the set of tasks that are ready to be processed (all their predecessors have been processed)\n",
    "    # due to limited resources, they might be waiting for resources\n",
    "    ReadyTasks=[]\n",
    "    ReadyTasks.append((0,n,0,0))\n",
    "\n",
    "\n",
    "    #Ltasks is the list of tasks that have not been processed and that are not yet ready\n",
    "    LTasks=[]\n",
    "\n",
    "    #disctionnary Processed provides, for each task, where and when it has been processed\n",
    "    Processed={}\n",
    "    #dictionnary Released provides, for each task, the minimum time when it can be processed (-1 at the beginning), \n",
    "    # given its already scheduled predecessors. The number of remaining predecessors to be \n",
    "    # scheduled is stored in NbSuccASAP={}\n",
    "    Released={}\n",
    "    NbSuccASAP={}\n",
    "    # Prio is the priority of the task for the alap.\n",
    "    # at the moment, Prio is just the length of the critical path in ASAP (because I had the values at hand !)\n",
    "    Prio={}\n",
    "\n",
    "    CP=C+(n-1)*(T+S+C)\n",
    "\n",
    "    Released[(0,n,0,0)]=mini\n",
    "    NbSuccASAP[(0,n,0,0)]=0\n",
    "    Prio[(0,n,0,0)]=0\n",
    "\n",
    "# initialization of Prio (critical path in ASAP), Released (-1 at the beginning), \n",
    "# NbSuccASAP (predecessors in ALAP) \n",
    "\n",
    "    for i in range(1,n):\n",
    "        Released[(0,i,0,0)]=mini\n",
    "        Prio[(0,i,0,0)]=CP-(i-1)*(C+S+T)\n",
    "#    Prio[(0,i,0,0)]=n-i\n",
    "#    Prio[(0,i,0,0)]=i\n",
    "\n",
    "        NbSuccASAP[(0,i,0,0)]=n-i\n",
    "        LTasks.append((0,i,0,0))\n",
    "\n",
    "\n",
    "\n",
    "    for j in range(1,n):\n",
    "        for i in range(j+1,n+1):\n",
    "            Released[(1,i,j,0)]=mini\n",
    "            NbSuccASAP[(1,i,j,0)]=1\n",
    "            LTasks.append((1,i,j,0))\n",
    "            if i < n:\n",
    "                Prio[(1,i,j,0)]=CP-(j-1)*(C+S+T)-C-T\n",
    " #           Prio[(1,i,j,0)]=n-j\n",
    "#            Prio[(1,i,j,0)]=j\n",
    "\n",
    "\n",
    "\n",
    "            else:\n",
    "                Prio[(1,i,j,0)]=CP-(j-1)*(C+S+T)-C-T\n",
    "#            Prio[(1,i,j,0)]=n-j \n",
    "#            Prio[(1,i,j,0)]=j \n",
    "\n",
    "\n",
    "    for i in range(1,n):\n",
    "        for j in range(i+1,n+1):\n",
    "            LTasks.append((2,i,j,0))\n",
    "            Released[(2,i,j,0)]=mini\n",
    "            Prio[(2,i,j,0)]=CP-(i-1)*(C+S+T)-C\n",
    "#        Prio[(2,i,j,0)]=n-i\n",
    "#        Prio[(2,i,j,0)]=i\n",
    "\n",
    "\n",
    "            NbSuccASAP[(2,i,j,0)]=n-i\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    for k in range(1,n-1):\n",
    "        for i in range(k+1,n):\n",
    "            for j in range(i+1,n+1):\n",
    "                LTasks.append((3,i,j,k))\n",
    "                Released[(3,i,j,k)]=mini\n",
    "                Prio[(3,i,j,k)]=CP-(k-1)*(C+S+T)-C-T\n",
    " #           Prio[(3,i,j,k)]=n-k\n",
    "#            Prio[(3,i,j,k)]=k\n",
    "                NbSuccASAP[(3,i,j,k)]=1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "#ProcReady[i] is the time when processor P_i is available.\n",
    "\n",
    "    ProcReady=[0]*P\n",
    "\n",
    "\n",
    "\n",
    "# instant represents the current time\n",
    "\n",
    "\n",
    "\n",
    "    # instant represents the current time\n",
    "    instant=0\n",
    "\n",
    "    while len(ReadyTasks)>0:\n",
    "\n",
    "        for i in range(P):\n",
    "            ProcReady[i]=max(instant,ProcReady[i])\n",
    "#    print('debut',\"\\n\",instant)\n",
    "#    print('ReadyTasks',ReadyTasks)\n",
    "#    print(\"Processed\",Processed)\n",
    "#    print('ProcReady',ProcReady,\"\\n\\n\\n\")\n",
    "\n",
    "#indices is the list of the processors that are ready the soonest\n",
    "        indices = [i for i, x in enumerate(ProcReady) if x == min(ProcReady)]\n",
    "        \n",
    "#nextinstant1 is the next instant when something can happen         \n",
    "\n",
    "        for i in indices:\n",
    "        # first find the highest priority task among the ready ones\n",
    "            if len(ReadyTasks)>0:\n",
    "                HighestPrio=maxi\n",
    "                for task in ReadyTasks:\n",
    "                    if Prio[task] <= HighestPrio:\n",
    "                        if Released[task]<=instant:\n",
    "                            if min(ProcReady)<=instant:                    \n",
    "                                HighestPrio = Prio[task]\n",
    "                                HPTask=task\n",
    "            #mark all its successors with one depedendency less        \n",
    "                for task in succALAP(HPTask,n):\n",
    "                    Released[task]=max(Released[task],ProcReady[i]+duration(HPTask))\n",
    "                    NbSuccASAP[task]=NbSuccASAP[task]-1\n",
    "\n",
    "        #mark the task processed, update the availability of the associated proc and remove it from some lists    \n",
    "                ProcReady[i]=max(ProcReady[i],instant)+duration(HPTask)\n",
    "                Processed[HPTask]=[i,ProcReady[i]]\n",
    "                ReadyTasks.remove(HPTask)\n",
    "                del Released[HPTask]\n",
    "        #mininstant1 is the next instant when a busy processor will be released\n",
    "\n",
    "        nextinstant=maxi\n",
    "\n",
    "    # if there are no more ready tasks, we should determine the time when something will happen\n",
    "    # ie a task that is not ready yet but will become soon given what has been scheduled (ie no dependencies\n",
    "    # but still running predecessors)\n",
    "    # in this first part, the goal is to find the first instant when a task will become ready\n",
    "        for task in ReadyTasks:\n",
    "            nextinstant=min(nextinstant,Released[task])    \n",
    "        nextinstant=max(min(ProcReady),nextinstant)   \n",
    "\n",
    "        \n",
    "        for task in LTasks:\n",
    "            if task not in ReadyTasks:\n",
    "                if NbSuccASAP[task] ==0:\n",
    "                    if task in Released:\n",
    "                        if Released[task] <= nextinstant:\n",
    "                            nextinstant=min(nextinstant,Released[task])\n",
    "\n",
    "\n",
    "   # once we now this instant (nextinstant) just put the corresponding task(s) into the ready list                       \n",
    "        for task in LTasks:\n",
    "            if task not in ReadyTasks:\n",
    "                if NbSuccASAP[task] ==0:\n",
    "                    if task in Released:\n",
    "                        if Released[task] <= nextinstant:                       \n",
    "                            ReadyTasks.append(task)\n",
    "\n",
    "    \n",
    "    #and advance the time until the new instant when something will happen (and in particlar there\n",
    "    #should be a ready task)\n",
    "\n",
    "\n",
    "        instant=max(min(ProcReady),nextinstant)\n",
    "        \n",
    "        if (0,1,0,0) in ReadyTasks:\n",
    "            #we reached the first POTRF\n",
    "            break\n",
    "\n",
    "\n",
    "            \n",
    "    Processed[(0,1,0,0)]=[0,max(ProcReady)+C]  \n",
    "\n",
    "#    print(Processed)\n",
    "#    print(\"CP=\",CP,\"endtime=\",max(ProcReady)+C)                \n",
    "\n",
    "    return(Processed,max(ProcReady)+C)\n",
    "    \n",
    "  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "outputs": [
    {
     "data": {
      "text/plain": "({(0, 1, 0, 0): [0, 124],\n  (2, 1, 2, 0): [0, 112],\n  (2, 1, 3, 0): [1, 112],\n  (2, 1, 4, 0): [2, 112],\n  (2, 1, 5, 0): [3, 112],\n  (1, 2, 1, 0): [0, 109],\n  (3, 2, 3, 1): [1, 109],\n  (1, 3, 1, 0): [2, 109],\n  (3, 2, 4, 1): [3, 109],\n  (0, 2, 0, 0): [0, 108],\n  (3, 3, 4, 1): [2, 108],\n  (1, 4, 1, 0): [1, 107],\n  (3, 2, 5, 1): [3, 107],\n  (3, 3, 5, 1): [1, 106],\n  (3, 4, 5, 1): [2, 106],\n  (2, 1, 6, 0): [3, 105],\n  (1, 5, 1, 0): [1, 104],\n  (2, 1, 7, 0): [2, 104],\n  (2, 1, 8, 0): [1, 103],\n  (3, 2, 6, 1): [3, 102],\n  (3, 3, 6, 1): [2, 101],\n  (3, 4, 6, 1): [1, 100],\n  (3, 5, 6, 1): [3, 100],\n  (3, 2, 7, 1): [2, 99],\n  (3, 3, 7, 1): [1, 98],\n  (1, 6, 1, 0): [3, 98],\n  (3, 4, 7, 1): [2, 97],\n  (3, 5, 7, 1): [3, 97],\n  (2, 2, 3, 0): [0, 96],\n  (2, 2, 4, 0): [1, 96],\n  (2, 2, 5, 0): [2, 95],\n  (2, 2, 6, 0): [3, 95],\n  (1, 3, 2, 0): [0, 93],\n  (3, 3, 4, 2): [1, 93],\n  (0, 3, 0, 0): [0, 92],\n  (1, 4, 2, 0): [2, 92],\n  (3, 3, 5, 2): [3, 92],\n  (3, 4, 5, 2): [1, 91],\n  (1, 5, 2, 0): [2, 91],\n  (3, 3, 6, 2): [2, 90],\n  (3, 4, 6, 2): [3, 90],\n  (3, 5, 6, 2): [1, 89],\n  (2, 2, 7, 0): [2, 88],\n  (1, 6, 2, 0): [3, 88],\n  (3, 2, 8, 1): [1, 87],\n  (3, 6, 7, 1): [3, 87],\n  (3, 3, 7, 2): [1, 85],\n  (3, 4, 7, 2): [2, 85],\n  (3, 5, 7, 2): [3, 85],\n  (2, 2, 8, 0): [1, 83],\n  (3, 6, 7, 2): [2, 83],\n  (3, 3, 8, 1): [3, 83],\n  (3, 4, 8, 1): [2, 81],\n  (3, 5, 8, 1): [3, 81],\n  (2, 3, 4, 0): [0, 80],\n  (2, 3, 5, 0): [1, 80],\n  (2, 3, 6, 0): [2, 79],\n  (2, 3, 7, 0): [3, 79],\n  (1, 4, 3, 0): [0, 77],\n  (3, 4, 5, 3): [1, 77],\n  (0, 4, 0, 0): [0, 76],\n  (1, 5, 3, 0): [2, 76],\n  (3, 4, 6, 3): [3, 76],\n  (3, 5, 6, 3): [1, 75],\n  (1, 6, 3, 0): [2, 75],\n  (3, 4, 7, 3): [2, 74],\n  (3, 5, 7, 3): [3, 74],\n  (3, 6, 7, 3): [1, 73],\n  (3, 3, 8, 2): [2, 72],\n  (3, 4, 8, 2): [3, 72],\n  (1, 7, 1, 0): [1, 71],\n  (2, 3, 8, 0): [1, 70],\n  (1, 7, 2, 0): [2, 70],\n  (3, 5, 8, 2): [3, 70],\n  (1, 7, 3, 0): [2, 69],\n  (3, 6, 8, 1): [2, 68],\n  (3, 7, 8, 1): [3, 68],\n  (3, 4, 8, 3): [1, 67],\n  (3, 5, 8, 3): [2, 66],\n  (3, 6, 8, 2): [3, 66],\n  (3, 7, 8, 2): [1, 65],\n  (2, 4, 5, 0): [0, 64],\n  (2, 4, 6, 0): [2, 64],\n  (2, 4, 7, 0): [3, 64],\n  (2, 4, 8, 0): [1, 63],\n  (1, 5, 4, 0): [0, 61],\n  (3, 5, 6, 4): [2, 61],\n  (1, 6, 4, 0): [3, 61],\n  (0, 5, 0, 0): [0, 60],\n  (3, 5, 7, 4): [1, 60],\n  (3, 6, 7, 4): [3, 60],\n  (1, 7, 4, 0): [2, 59],\n  (3, 5, 8, 4): [1, 58],\n  (3, 6, 8, 3): [2, 58],\n  (3, 7, 8, 3): [3, 58],\n  (3, 6, 8, 4): [1, 56],\n  (3, 7, 8, 4): [2, 56],\n  (1, 8, 1, 0): [3, 56],\n  (1, 8, 2, 0): [3, 55],\n  (1, 8, 3, 0): [1, 54],\n  (1, 8, 4, 0): [1, 53],\n  (2, 5, 6, 0): [0, 48],\n  (2, 5, 7, 0): [1, 48],\n  (2, 5, 8, 0): [2, 48],\n  (1, 6, 5, 0): [0, 45],\n  (3, 6, 7, 5): [1, 45],\n  (1, 7, 5, 0): [2, 45],\n  (3, 6, 8, 5): [3, 45],\n  (0, 6, 0, 0): [0, 44],\n  (3, 7, 8, 5): [2, 44],\n  (1, 8, 5, 0): [1, 43],\n  (2, 6, 7, 0): [0, 32],\n  (2, 6, 8, 0): [1, 32],\n  (1, 7, 6, 0): [0, 29],\n  (3, 7, 8, 6): [1, 29],\n  (1, 8, 6, 0): [2, 29],\n  (0, 7, 0, 0): [0, 28],\n  (2, 7, 8, 0): [0, 16],\n  (1, 8, 7, 0): [0, 13],\n  (0, 8, 0, 0): [0, 12]},\n 124)"
     },
     "metadata": {},
     "output_type": "execute_result",
     "execution_count": 6
    }
   ],
   "source": [
    "LengthASAP(8,4)\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n",
     "is_executing": false
    }
   }
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "name": "pycharm-cd5d51f2",
   "language": "python",
   "display_name": "PyCharm (relational_RL_graphs)"
  },
  "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.6.6"
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "source": [],
    "metadata": {
     "collapsed": false
    }
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}