Priority Queues and Bin Packing.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq # https://docs.python.org/3/library/heapq.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 15, 10, 100]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h = []\n",
    "heapq.heappush(h, 100)\n",
    "heapq.heappush(h, 10)\n",
    "heapq.heappush(h, 1)\n",
    "heapq.heappush(h, 15)\n",
    "h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 'Elemento do Inicio'), (10, 'Elemento do Meio'), (100, 'Elemento do Fim')]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h = []\n",
    "heapq.heappush(h, (10, \"Elemento do Meio\"))\n",
    "heapq.heappush(h, (1, \"Elemento do Inicio\"))\n",
    "heapq.heappush(h, (100, \"Elemento do Fim\"))\n",
    "h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 'Elemento do Inicio')"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n, msg = heapq.heappop(h)\n",
    "n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Elemento do Meio'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "msg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(100, '100')"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [(100, \"100\"), (10, \"10\"), (1, \"1\"), (1000, \"1000\")]\n",
    "heapq.heappop(l) # wrong answer!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, '1'), (10, '10'), (1000, '1000')]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l # was \"heapified\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, '1')"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10, '10')"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1000, '1000')"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, '1'), (10, '10'), (100, '100'), (1000, '1000')]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [(100, \"100\"), (10, \"10\"), (1, \"1\"), (1000, \"1000\")]\n",
    "heapq.heapify(l) # before treat list as heap you need to heapify\n",
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, '1')"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(l) # correct answer!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MinPQ:\n",
    "    def __init__(self):\n",
    "        self.h = []\n",
    "    def __str__(self):\n",
    "        return self.h.__str__()\n",
    "    def __repr__(self):\n",
    "        return self.__str__()\n",
    "    def __assert_not_empty(self):\n",
    "        if (self.isEmpty()): raise Exception(\"this priority queue is empty\")\n",
    "    def insert(self, item, priority):\n",
    "        heapq.heappush(self.h, (priority, item))\n",
    "    def min(self):\n",
    "        #if (self.isEmpty()): raise Exception(\"this priority queue is empty\")\n",
    "        self.__assert_not_empty()\n",
    "        _, item = self.h[0]\n",
    "        return item\n",
    "        # try:\n",
    "        #     return self.h[0]\n",
    "        # except IndexError:\n",
    "        #     raise Exception(\"this priority queue is empty\")\n",
    "    def delMin(self):\n",
    "        self.__assert_not_empty()\n",
    "        _, item = heapq.heappop(self.h)\n",
    "        return item\n",
    "    def size(self):\n",
    "        return len(self.h)\n",
    "    def isEmpty(self):\n",
    "        return len(self.h) == 0\n",
    "    def clear(self):\n",
    "        self.h = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq1 = MinPQ()\n",
    "pq1.insert(\"100\", 100)\n",
    "pq1.insert(\"1\", 1)\n",
    "pq1.insert(\"1000\", 1000)\n",
    "pq1.size()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, '1'), (100, '100'), (1000, '1000')]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1'"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq1.delMin()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'100'"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq1.delMin()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq1.size()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq1.isEmpty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1000'"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq1.delMin()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq1.isEmpty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MaxPQ:\n",
    "    def __init__(self):\n",
    "        self.h = []\n",
    "    def __str__(self):\n",
    "        return self.h.__str__()\n",
    "    def __repr__(self):\n",
    "        return self.__str__()\n",
    "    def __assert_not_empty(self):\n",
    "        if (self.isEmpty()): raise Exception(\"this priority queue is empty\")    \n",
    "    def insert(self, item, priority):\n",
    "        heapq.heappush(self.h, (-priority, item))\n",
    "    def max(self):\n",
    "        self.__assert_not_empty()\n",
    "        _, item = self.h[0]\n",
    "        return item\n",
    "    def delMax(self):\n",
    "        self.__assert_not_empty()\n",
    "        _, item = heapq.heappop(self.h)\n",
    "        return item\n",
    "    def size(self):\n",
    "        return len(self.h)\n",
    "    def isEmpty(self):\n",
    "        return len(self.h) == 0\n",
    "    def clear(self):\n",
    "        self.h = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq2 = MaxPQ()\n",
    "pq2.insert(\"100\", 100)\n",
    "pq2.insert(\"1\", 1)\n",
    "pq2.insert(\"1000\", 1000)\n",
    "pq2.size()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1000'"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq2.delMax()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'100'"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq2.delMax()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq2.size()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq2.isEmpty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1'"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq2.delMax()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq2.isEmpty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def highestPriority(self):\n",
    "    isMaxPQ = isinstance(self, MaxPQ)\n",
    "    isMinPQ = isinstance(self, MinPQ)\n",
    "    if not (isMaxPQ or isMinPQ): raise Exception(\"not a priority queue\")\n",
    "    if isMaxPQ:\n",
    "        self._MaxPQ__assert_not_empty()\n",
    "        priority, _ = self.h[0]\n",
    "        return -priority\n",
    "    else:\n",
    "        self._MinPQ__assert_not_empty()\n",
    "        priority, _ = self.h[0]\n",
    "        return priority"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq1 = MinPQ()\n",
    "pq1.insert(\"100\", 100)\n",
    "pq1.insert(\"1\", 1)\n",
    "pq1.insert(\"1000\", 1000)\n",
    "highestPriority(pq1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1000"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq2 = MaxPQ()\n",
    "pq2.insert(\"100\", 100)\n",
    "pq2.insert(\"1\", 1)\n",
    "pq2.insert(\"1000\", 1000)\n",
    "highestPriority(pq2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, '1'), (2, '2'), (3, '3'), (4, '4'), (5, '5'), (6, '6'), (7, '7')]"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Binary heap\n",
    "pq1 = MinPQ()\n",
    "pq1.insert(\"1\",1)\n",
    "pq1.insert(\"2\",2)\n",
    "pq1.insert(\"3\",3)\n",
    "pq1.insert(\"4\",4)\n",
    "pq1.insert(\"5\",5)\n",
    "pq1.insert(\"6\",6)\n",
    "pq1.insert(\"7\",7)\n",
    "pq1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, '1'), (5, '5'), (7, '7')]"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq1 = MinPQ()\n",
    "pq1.insert(\"1\",1)\n",
    "pq1.insert(\"5\",5)\n",
    "pq1.insert(\"7\",7)\n",
    "pq1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, '1'), (4, '4'), (7, '7'), (5, '5')]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq1.insert(\"4\",4)\n",
    "pq1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, '1'), (2, '2'), (7, '7'), (5, '5'), (4, '4')]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq1.insert(\"2\",2)\n",
    "pq1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, '1'), (2, '2'), (6, '6'), (5, '5'), (4, '4'), (7, '7')]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq1.insert(\"6\",6)\n",
    "pq1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, '1'), (2, '2'), (3, '3'), (5, '5'), (4, '4'), (7, '7'), (6, '6')]"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pq1.insert(\"3\",3)\n",
    "pq1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Bin packing\n",
    "class Bin:\n",
    "    def __init__(self, capacity):\n",
    "        if (capacity < 0): capacity = 0\n",
    "        self.capacity = capacity\n",
    "        self.items = []\n",
    "    def __str__(self):\n",
    "        return \"(remaining: %d items: %s)\" % (self.capacity, self.items)\n",
    "    def __repr__(self):\n",
    "        return self.__str__()\n",
    "    def __lt__(self, that):\n",
    "        return self.size() < that.size()\n",
    "    def size(self):\n",
    "        return self.capacity\n",
    "    def isFull(self):\n",
    "         return self.capacity == 0\n",
    "    def tryDecrease(self, size):\n",
    "        if (0 < size) and (size <= self.capacity):\n",
    "            self.capacity -= size\n",
    "            self.items.append(size)\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "def binPackingBestFit(weights, binCapacity):\n",
    "    pq = MaxPQ()\n",
    "    pq.insert(Bin(binCapacity), binCapacity)\n",
    "    for w in weights:\n",
    "        if (w <= binCapacity):\n",
    "            if (pq.max().size() < w):\n",
    "                pq.insert(Bin(binCapacity), binCapacity)\n",
    "            b = pq.delMax()\n",
    "            b.tryDecrease(w)\n",
    "            pq.insert(b, b.size())\n",
    "        else:\n",
    "            raise Exception(\"weight [%d] greater than bin capacity [%d]\" % (w, binCapacity))\n",
    "    return list(map(lambda b: b[1], pq.h))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b1 = Bin(10)\n",
    "b1.size()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(remaining: 10 items: [])"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b1.tryDecrease(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(remaining: 9 items: [1])"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b1.tryDecrease(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b1.tryDecrease(9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(remaining: 0 items: [1, 9])"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b1.isFull()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(remaining: 2 items: [8]), (remaining: 1 items: [4, 2, 3])]"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "binPackingBestFit([8,4,2,3], 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(remaining: 3 items: [7]),\n",
       " (remaining: 3 items: [2, 5]),\n",
       " (remaining: 2 items: [4, 1, 3]),\n",
       " (remaining: 2 items: [8])]"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "binPackingBestFit([2,5,4,7,1,3,8], 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(remaining: 2 items: [8]),\n",
       " (remaining: 1 items: [9]),\n",
       " (remaining: 2 items: [3, 4, 1])]"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "binPackingBestFit([8,3,4,9,1], 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(binPackingBestFit([8,3,4,9,1], 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}