344 [Intermediate] Banker's Algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 179,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Not all objectives could not be achieved:\n",
      " [5]\n",
      "Achieved goals:\n",
      " [1, 3, 0, 2, 4]\n",
      "1 loop, best of 1: 5.1 ms per loop\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "inx =  '[3 3 2]\\n[0 1 0 7 5 3]\\n[2 0 0 3 2 2]\\n[3 0 2 9 0 2]\\n[2 1 1 2 2 2]\\n[0 0 2 4 3 3]\\n[0 0 0 20 20 20]'\n",
    "\n",
    "def do(inx):\n",
    "\n",
    "    inx = inx.replace('[','').replace(']','')\n",
    "    Linx = [[ix]+[int(y) for y in x.split(' ')] for ix,x in enumerate(inx.split('\\n'))]\n",
    "\n",
    "    available = np.array(Linx[0][1:])\n",
    "    Requires = np.array(Linx[1:])\n",
    "\n",
    "    correction = [1,0,0,0,0,0,0]\n",
    "\n",
    "    series  = []\n",
    "    c = True\n",
    "\n",
    "    while c:\n",
    "        c = False\n",
    "        Possible = Requires[:,:4].copy()\n",
    "        Possible[:,1:] += available - Requires[:,4:]\n",
    "        \n",
    "        does = np.all(np.where(Possible >= 0,True,False),1).reshape(-1,1)\n",
    "        if sum(does):\n",
    "            c = True\n",
    "    \n",
    "        Mod = (Requires + correction) * does\n",
    "        series += np.extract(np.where(Mod[:,0] > 0,True,False),Mod[:,0]-2).tolist()\n",
    "        available += np.sum(Mod[:,1:4],0)\n",
    "        Requires -= Mod\n",
    "    \n",
    "    if len(series) != len(Requires):\n",
    "        not_done = np.extract(np.where(Requires[:,0] > 0,True,False),Requires[:,0]-1)\n",
    "        print('Not all objectives could not be achieved:\\n', not_done)\n",
    "    \n",
    "    print('Achieved goals:\\n',str(series))\n",
    "    \n",
    "%timeit -n1 -r1 do(inx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0, [0, 1, 0], [7, 5, 3]), (1, [2, 0, 0], [3, 2, 2]), (2, [3, 0, 2], [9, 0, 2]), (3, [2, 1, 1], [2, 2, 2]), (4, [0, 0, 2], [4, 3, 3]), (5, [0, 0, 0], [20, 20, 20])]\n",
      "P1, P3, P0, P2, P4, P5\n",
      "1 loop, best of 1: 474 µs per loop\n"
     ]
    }
   ],
   "source": [
    "def add(iter1, iter2):\n",
    "    for a, b in zip(iter1, iter2):\n",
    "        yield a + b\n",
    "\n",
    "def subtract(iter1, iter2):\n",
    "    for a, b in zip(iter1, iter2):\n",
    "        yield a - b\n",
    "\n",
    "def greater_equal(iter1, iter2):\n",
    "    for a, b in zip(iter1, iter2):\n",
    "        yield a >= b\n",
    "\n",
    "def do(inx):\n",
    "\n",
    "    inx = inx.replace('[','').replace(']','')\n",
    "    lines = [[int(y) for y in x.split(' ')] for ix,x in enumerate(inx.split('\\n'))]\n",
    "\n",
    "    available = lines[0]\n",
    "    processes = [(i, process[:len(available)], process[len(available):]) for i, process in enumerate(lines[1:])]\n",
    "    print(processes)\n",
    "    order = []\n",
    "\n",
    "    while processes:\n",
    "        for process in processes:\n",
    "            if all(greater_equal(available, subtract(process[2], process[1]))):\n",
    "                processes.remove(process)\n",
    "                available = add(available, process[1])\n",
    "                order.append(process[0])\n",
    "                break\n",
    "        else:\n",
    "            print(\"no solution found\")\n",
    "            break\n",
    "    else:\n",
    "        print(', '.join(['P' + str(n) for n in order]))\n",
    "        \n",
    "%timeit -n1 -r1 do(inx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5]"
      ]
     },
     "execution_count": 130,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.extract(np.where(Mod[:,0] > 0,True,False),Mod[:,0]).tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1])"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(np.all(np.where(Requires >= 0,True,False),1).reshape(-1,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[1],\n",
       "        [1],\n",
       "        [1],\n",
       "        [1],\n",
       "        [1]]), array([[0, 1, 0, 7, 5, 3],\n",
       "        [2, 0, 0, 3, 2, 2],\n",
       "        [3, 0, 2, 9, 0, 2],\n",
       "        [2, 1, 1, 2, 2, 2],\n",
       "        [0, 0, 2, 4, 3, 3]]))"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.ones(((len(inx)-1),1),int), np.array(inx[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all([ True,  True,  True,  True])"
   ]
  },
  {
   "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}