water jug problem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Water Jug\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "Water jug is an interesting problem. Basically you have two water jugs with different volume. The idea is to get certain amount of water inside one of the jugs without taking any measurement. All you can do is to pour water from one jug to the other. There are different ways to solve this problem. \n",
    "You can take dynamic programming approach, algebra approach or graph theory approach. Here, we intend to discuss BFS, DFS and Dijkstra from graph theory approach.\n",
    "\n",
    "Details of water jug problem can be found in the following link\n",
    "\n",
    "https://www.geeksforgeeks.org/puzzle-water-jug-problem/\n",
    "\n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "os.chdir('K:/ecole/github')\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.animation as pltani\n",
    "\n",
    "#graph adt\n",
    "#check the below link for more details\n",
    "# https://github.com/je-suis-tm/graph-theory/blob/master/graph.py\n",
    "import graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#assume the big jug is 5 gallon, the small jug is 3 gallon\n",
    "big=5\n",
    "small=3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#to add edges between vertices\n",
    "#lets look at all the possible scenarios\n",
    "#there are eight scenarios\n",
    "def check_around(big,small):\n",
    "    \n",
    "    ADT=graph.graph()\n",
    "\n",
    "    for i in range(big+1):\n",
    "        for j in range(small+1):\n",
    "\n",
    "            #when big jug is empty\n",
    "            #we can always fill up big jug\n",
    "            if i==0:\n",
    "\n",
    "                ADT.append((0,j),(big,j),1)\n",
    "\n",
    "            #when small jug is empty\n",
    "            #we can always fill up small jug\n",
    "            if j==0:\n",
    "\n",
    "                ADT.append((i,0),(i,small),1)\n",
    "\n",
    "            #when small jug is not empty\n",
    "            #we can always empty the small jug\n",
    "            #that condition avoids (0,0) to (0,0)\n",
    "            if j!=0:\n",
    "\n",
    "                ADT.append((i,j),(i,0),1)\n",
    "\n",
    "            #when big jug is not empty\n",
    "            #we can always empty the big jug\n",
    "            #that condition avoids (0,0) to (0,0)\n",
    "            if i!=0:\n",
    "\n",
    "                ADT.append((i,j),(0,j),1)\n",
    "\n",
    "            #when big jug is not filled up\n",
    "            #we pour water from small jug into the big jug\n",
    "            #we dont have water left in the small jug \n",
    "            #and the big jug is filled up\n",
    "            if i<big and j<=big-i:\n",
    "\n",
    "                ADT.append((i,j),(i+j,0),1)\n",
    "\n",
    "            #when big jug is not filled up\n",
    "            #we pour water from small jug into the big jug\n",
    "            #we still got some water left in the small jug \n",
    "            #and the big jug is filled up\n",
    "            if i<big and j>big-i:\n",
    "\n",
    "                ADT.append((i,j),(big,j-big+i),1)\n",
    "\n",
    "            #when small jug is not filled up\n",
    "            #we pour water from big jug into the small jug\n",
    "            #we dont have water left in the big jug \n",
    "            #and the small jug is filled up\n",
    "            if j<small and i<=small-j:\n",
    "\n",
    "                ADT.append((i,j),(0,j+i),1)\n",
    "\n",
    "            #when small jug is not filled up\n",
    "            #we pour water from big jug into the small jug\n",
    "            #we still have water left in the big jug \n",
    "            #and the small jug is filled up\n",
    "            if j<small and i>small-j:\n",
    "\n",
    "                ADT.append((i,j),(i-small+j,small),1)\n",
    "                \n",
    "    return ADT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#generate graph adt\n",
    "ADT=check_around(big,small)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length of the process: 7\n",
      "number of vertices BFS has travelled: 15\n"
     ]
    }
   ],
   "source": [
    "#bfs demonstrates the capability of finding an optimal for any graph adt\n",
    "#details of bfs can be found in the following link\n",
    "# https://github.com/je-suis-tm/graph-theory/blob/master/BFS%20DFS%20on%20DCG.ipynb\n",
    "len_of_process_bfs,process_bfs=graph.bfs_path(ADT,(0,0),(4,0))\n",
    "num_of_v_bfs=len([i for i in ADT.route() if ADT.route()[i]==1])\n",
    "ADT.clear(whole=True)\n",
    "\n",
    "print(f'length of the process:',len_of_process_bfs)\n",
    "print(f'number of vertices BFS has travelled:',num_of_v_bfs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length of the process: 10\n",
      "number of vertices DFS has travelled: 11\n"
     ]
    }
   ],
   "source": [
    "#dfs traveled fewer vertices\n",
    "#even though the result is not the optimal\n",
    "#details of dfs can be found in the following link\n",
    "# https://github.com/je-suis-tm/graph-theory/blob/master/BFS%20DFS%20on%20DCG.ipynb\n",
    "len_of_process_dfs,process_dfs=graph.dfs_path(ADT,(0,0),(4,0))\n",
    "num_of_v_dfs=len([i for i in ADT.route() if ADT.route()[i]==1])\n",
    "ADT.clear(whole=True)\n",
    "\n",
    "print(f'length of the process:',len_of_process_dfs)\n",
    "print(f'number of vertices DFS has travelled:',num_of_v_dfs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length of the process: 7\n",
      "number of vertices Dijkstra has travelled: 15\n"
     ]
    }
   ],
   "source": [
    "#dijkstra is guaranteed to find the optimal\n",
    "#details of dijkstra could be found in the following link\n",
    "# https://github.com/je-suis-tm/graph-theory/blob/master/dijkstra%20shortest%20path.ipynb\n",
    "len_of_process_dijkstra,process_dijkstra=graph.dijkstra(ADT,(0,0),(4,0))\n",
    "num_of_v_dijkstra=len([i for i in ADT.route() if ADT.route()[i]==1])\n",
    "ADT.clear(whole=True)\n",
    "\n",
    "print(f'length of the process:',len_of_process_dijkstra)\n",
    "print(f'number of vertices Dijkstra has travelled:',num_of_v_dijkstra)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#viz water jug change\n",
    "def draw_waterjug(ind,*args):\n",
    "    \n",
    "    ax,process=args\n",
    "\n",
    "    ax.collections.clear()\n",
    "    \n",
    "    #viz water\n",
    "    Y_big,Y_small=process[ind][0],process[ind][1]\n",
    "    xval_big=[i/10 for i in range(6,15)]\n",
    "    xval_small=[i/10 for i in range(26,35)]\n",
    "    yval_big=[big/10*i for i in range(Y_big*2+1)]\n",
    "    yval_small=[small/10*i for i in range(Y_small*2+1)]\n",
    "\n",
    "    ax.scatter(sorted(xval_big*len(yval_big)),\n",
    "               yval_big*len(xval_big),\n",
    "               color='cyan' if Y_big!=0 else 'w',\n",
    "               s=2)\n",
    "    ax.scatter(sorted(xval_small*len(yval_small)),\n",
    "               yval_small*len(xval_small),\n",
    "               color='cyan' if Y_small!=0 else 'w',\n",
    "               s=2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "MovieWriter ffmpeg unavailable.\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAATYAAAEoCAYAAADSYN1CAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAFDJJREFUeJzt3X1sXfV9x/HPl8TUjKSFhsDiJMTpA09NjLFvSSJADQXRTthZ/4ACLW2ZptxIGSiTkKYSaYlRVbV/tBP9Y23jFJZIsEUoQImjjQ3EQ4eawO51E0hJIkqVKLaz1mSl4NGwPHz3R46tGE7uvce+9xyfX94vyZLv8bnXHx9Fn5z7PQ/X3F0AEJJzsg4AAPVGsQEIDsUGIDgUG4DgUGwAgkOxAQhOTcVmZheY2VYz22dme81sWaODAcBETa9xvR9JesbdbzOzcyX9WQMzAcCkWLUTdM3s45J2S/qUczYvgByo5a3opyQNS/onM/uVmf3MzM5vcC4AmLBa9tgKknZKus7dXzGzH0l6193//kPrFSUVJen888/vvOKKKxoUGcDZqlwuv+3us6utV0ux/bmkne7eGj2+QdK33f3WMz2nUCh4qVRKlhgAqjCzsrsXqq1X9a2ou/+3pENmdnm06CZJb0wyHwA0TK1HRe+T9Fh0RPS3kv6qcZEAYHJqKjZ33yWp6u4fAEwFte6xAajBsWPHNDAwoKNHj2YdJdeam5s1b948NTU1Tej5FBtQRwMDA5o5c6ZaW1tlZlnHySV315EjRzQwMKCFCxdO6DW4VhSoo6NHj2rWrFmU2iSYmWbNmjWpvV6KDagzSm3yJrsNKTYgMNOmTVN7e7uuvvpqdXR06Je//KUkaWhoSLfddlui11q+fLnyeE4qxQY00OisrV5fra2tVX/neeedp127dmn37t363ve+pwceeECS1NLSoq1btzb4L54aKDaggQ4ePCh3r9vXwYMHE/3+d999VxdeeKEk6cCBA1q0aJEk6f3339dXv/pVtbW16Y477tCSJUuq7pnNmDFj7PutW7fqnnvukSS99dZbWrp0qT7/+c9r3bp149bLCkdFgcD86U9/Unt7u44eParDhw/r+eef/8g6P/7xj3XhhRfqtdde0549e9Te3j7h37dmzRqtWbNGd911l376059OJnrdsMcGBGb0rei+ffv0zDPP6Jvf/KY+fE34yy+/rDvvvFOStGjRIrW1tU349+3YsUO33367JOlrX/vaxIPXEcUGBGzZsmV6++23NTw8PG75RG6tePqRyql+AjLFBgRs3759OnHihGbNmjVu+fXXX6/HH39ckvTGG2/o9ddfr/pal1xyifbu3auTJ0/qqaeeGlu+dOlSPfHEE5KkLVu21DH9xDFjAwIzOmOTTu2Zbd68WdOmTRu3zurVq/Wtb31LbW1tuuaaa9TW1qZPfOITH3mt48eP62Mf+5gk6fvf/766uro0f/58LVq0SCMjI5Kkhx56SHfffbd++MMf6tZbb419nbRRbEADLViwoK4n7C5YsKDqOidOnIhd3traqj179kg6dS3mo48+qubmZr311lu66aabPvLaH3zwgQ4ePKhLL71UknTbbbfFngc3d+5c7dy5U2amLVu2qFDI/n4ZFBvQQAcOHMg6Qqz3339fN954o44dOyZ3109+8hOde+65Yz8vlUr6xje+odWrV1fdAyuXy7r33nvl7rrgggv0yCOPNDp+VRQbcBaaOXNmxfPWCoWC9u7dW9Nr3XDDDdq9e3e9otUFBw8ABIdiAxAcig1AcCg2AMGh2IDAfPe739XnPvc5tbW1qb29Xa+88kpdXnf04vbTL6Y/3ZmWZ4FiAxqsWCyOu/XQ0NCQ+vr6xi3r7e2VpHHLuru7JUnd3d3jlleyY8cObd++Xf39/Xrttdf03HPPaf78+Q3/G6caig1ooM7OTvX29o679VBLS4u6u7vHLSsWi5I0bllfX58kqa+vb9zySg4fPqyLLrpo7GqBiy66SC0tLZJOnaC7du1aLVu2TIVCQf39/frSl76kT3/602N35RgZGdFNN92kjo4OLV68WE8//fSE/u5Nmzbp3nvvHXvc1dWlF198UZL08MMP67LLLtPy5cu1cuXKcevVC8UGNFB/f39dX290z+5MbrnlFh06dEiXXXaZVq9erZdeemncz+fPn68dO3bohhtu0D333KOtW7dq586dWrdunaRTVyQ89dRT6u/v1wsvvKD7779/QhfMn8nQ0JC+853vaOfOnXr22We1b9++ur326Sg2IEdWrVpV8eczZsxQuVxWb2+vZs+erTvuuEObNm0a+/mKFSskSYsXL9aSJUs0c+ZMzZ49W83NzXrnnXfk7lq7dq3a2tp08803a3BwUL/73e/qlv/VV1/VF77wBX3yk59UU1PT2O2O6o0rD4AGmjNnTuq/c9q0aVq+fLmWL1+uxYsXa/PmzWN3ux19i3rOOeeMfT/6+Pjx43rsscc0PDyscrmspqYmtba2TugWRdOnT9fJkyfHHo++Rj33/iphjw1ooKGhoVR/3/79+/Xmm2+OPd61a1dNF86P+uMf/6iLL75YTU1NeuGFFxLfinxUa2urdu3apZMnT+rQoUN69dVXJUnXXnutXnrpJf3hD3/Q8ePHx253VG/ssQEN1NPTo56enrq93rZt2yr+fGRkRPfdd5/eeecdTZ8+XZ/5zGeqzuVO9/Wvf13d3d0qFApqb2/XFVdcUfNzT7/F0XXXXaeFCxdq8eLFWrRokTo6OiSduhPI2rVrtWTJErW0tOiqq65qzG2O6vlBE6NfnZ2dDpyN3njjjXGPJY37KpVKXiqVxi1bv369u7vPmTNnbFlHR4e7u69cuXLcuoODg2n/STX7+c9/7rfffnvV9d577z13dz927Jh3dXX5k08+Gbveh7elu7ukktfQQeyxAQ3kZ5gpxS2Pe9va29ubaI8rK+vWrdPTTz897kDFmfT09Oi5557T0aNHdcstt+grX/lK3fPYmTb8ZBQKBc/jh6wCk7V3715deeWVWccIQty2NLOyu1e9kyUHDwAEh2ID6qwR74LONpPdhhQbUEfNzc06cuQI5TYJ7q4jR46oubl5wq/BwQOgjubNm6eBgYGPfI4nkmlubta8efMm/HyKDaijpqYmLVy4MOsYZz3eigIITk17bGZ2QNJ7kk5IOl7L4VYAyEqSt6I3uvvbDUsCAHXCW1EAwam12FzSf5hZ2cyKjQwEAJNV61vR69x9yMwulvSsme1z91+cvkJUeEVJuvTSS+scc2JaW1snfNuVkC1YsEAHDhzIOgbQMImvFTWzHkkj7v6DM60zVa4VNTNOlIzBdkFe1e1aUTM738xmjn4v6RZJeyYfEQAao5a3opdIeir62K/pkv7Z3Z9paCoAmISqxebuv5V0dQpZAKAuON0DQHAoNgDBodgABIdiAxAcig1AcCg2AMGh2AAEh2IDEByKDUBwKDYAwaHYAASHYgMQHIoNQHAoNgDBodgABIdiAxAcig1AcCg2AMGh2AAEh2IDEByKDUBwKDYAwaHYAASHYgMQHIoNQHAoNgDBodgABIdiAxAcig1AcCg2AMGh2AAEh2IDEByKDUBwKDYAwaHYAASHYgMQHIoNQHBqLjYzm2ZmvzKz7Y0MBACTlWSPbY2kvY0KAgD1UlOxmdk8SbdK+llj4wDA5NW6x/aQpL+TdLKBWQCgLqoWm5l1Sfq9u5errFc0s5KZlYaHh+sWEACSqmWP7TpJK8zsgKQtkr5oZo9+eCV373X3grsXZs+eXeeYAFC7qsXm7g+4+zx3b5V0p6Tn3f3uhicDgAniPDYAwZmeZGV3f1HSiw1JAgB1wh4bgOBQbACCQ7EBCA7FBiA4FBuA4FBsAIJDsQEIDsUGIDgUG4DgUGwAgkOxAQgOxQYgOBQbgOBQbACCQ7EBCA7FBiA4FBuA4FBsAIJDsQEIDsUGIDgUG4DgUGwAgkOxAQgOxQYgOBQbgOBQbACCQ7EBCA7FBiA4FBuA4FBsAIJDsQEIDsUGIDgUG4DgUGwAgkOxAQgOxQYgOFWLzcyazexVM9ttZr82swfTCAYAEzW9hnU+kPRFdx8xsyZJL5vZv7n7zgZnA4AJqVps7u6SRqKHTdGXNzIUAExGTTM2M5tmZrsk/V7Ss+7+SmNjAcDE1VRs7n7C3dslzZN0rZkt+vA6ZlY0s5KZlYaHh+udE2i4lpYWSVJPT4/MbOyrXC6rXC6PW9bT0zP2nNFlnZ2dkqRisThu3aGhIfX19Y1b1tvbK0njlnV3d0uSuru7xy2XpN7e3nHL+vr6NDQ0NG5ZsViUJHV2do4tq9fflDd26p1mgieYrZf0v+7+gzOtUygUvFQqTTbbpJmZkv59ZwO2Szy2S7xisThWxFkzs7K7F6qtV8tR0dlmdkH0/XmSbpa0b/IRAeTBxo0bs46QWC1HRedI2mxm03SqCB939+2NjQWkr6OjI+sIqJNajoq+JumaFLIAmSqXy1lHQJ1w5QEQGR2+Y7zBwcGsIyRGsQGRPM6S0pDHPVmKDUBFK1asyDpCYhQbgOBQbEAkj7MkxKPYgEgeZ0lp2LBhQ9YREkt85UEtuPJgamO7xGO7TH11u/IAwNlt9HrVPKHYAASHYgMieZwlIR7FBkS48iBeV1dX1hESo9iASB5nSWno6+vLOkJiFBuAikZvgJknFBuAirZvz99dyig2IJLHWRLiUWxAJI+zJMSj2IBIHmdJacjj1RgUGxDJ4ywpDVPlg1ySoNgAVLRq1aqsIyRGsQEIDsUGRPI4S0I8ig2I5HGWlIZt27ZlHSExig2I5HGWlIbOzs6sIyRGsQGoaO7cuVlHSIxiAxAcig2I5HGWhHgUGxDJ4ywpDStXrsw6QmIUGxDJ4ywpDXk8WkyxAagoj3uyFBuAivr7+7OOkBjFBkTyOEtCPIoNiORxlpSGOXPmZB0hMYoNiORxlpSGoaGhrCMkRrEBkTzOktLQ09OTdYTEKDYAFT344INZR0iMYgMieZwlIV7VYjOz+Wb2gpntNbNfm9maNIIBacvjLAnxatljOy7pfne/UtJSSX9jZlc1NhaQvjzOktJQKpWyjpBY1WJz98Pu3h99/56kvZK49gTByeMsCfESzdjMrFXSNZJeaUQYAFNPoVDIOkJiNRebmc2Q9ISkv3X3d2N+XjSzkpmVhoeH65kRABKpqdjMrEmnSu0xd38ybh1373X3grsXZs+eXc+MQCryOEtCvFqOipqkhyXtdfd/aHwkAFPJ+vXrs46QmFX7yDEzu17Sf0p6XdLJaPFad//XMz2nUCj4VPjfz8z4SLUYbJd4bJepz8zK7l516De92gru/rIkq0sqALnT0tKSu3P8uPIAQEWHDx/OOkJiFBsQyeMsCfEoNiDClQfxOjo6so6QGMUGRFpaWrKOMCWVy+WsIyRGsQGRPM6S0lAsFrOOkBjFBqCijRs3Zh0hMYoNiORxloR4FBsQyeMsCfEoNiCSx1lSGgYHB7OOkBjFBkTyOEtKQx73ZCk2ABWtWLEi6wiJUWwAgkOxAZE8zpIQj2IDInmcJaVhw4YNWUdIrOr92CaC+7FNbWyXeGyXqa/W+7GxxwagolM30c4Xig1AcCg2IJLHWRLiUWxAhCsP4nV1dWUdITGKDYjkcZaUhr6+vqwjJEaxAaiou7s76wiJUWwAKtq+fXvWERKj2IBIHmdJiEexAZE8zpIQj2IDInmcJaUhj1djUGxAJI+zpDT09vZmHSExig1ARatWrco6QmIUG4DgUGxAJI+zJMSj2IBIHmdJadi2bVvWERKj2IBIHmdJaejs7Mw6QmIUG4CK5s6dm3WExCg2AMGh2IBIHmdJiEexAZE8zpLSsHLlyqwjJEaxAZE8zpLSkMejxRQbgIryuCdbtdjM7BEz+72Z7UkjEICppb+/P+sIidWyx7ZJ0pcbnAPIXB5nSYhXtdjc/ReS/ieFLECm8jhLSsOcOXOyjpAYMzYgksdZUhqGhoayjpBY3YrNzIpmVjKz0vDwcL1eFkhNHmdJaejp6ck6QmJWyx0NzKxV0nZ3X1TLixYKBS+VSpNLVgdmxh0bYrBd4rFd4k2l7WJmZXcvVFuPt6JAJI+zJMSr5XSPf5G0Q9LlZjZgZn/d+FhA+vI4S0K8Wo6K3uXuc9y9yd3nufvDaQQD0pbHWVIapsJYKSneigKRBx98MOsIqBOKDUBFhULVWf2UQ7EBCA7FBkTyOEtCPIoNQEXr16/POkJiNZ2gmxQn6E5tbJd4bJepjxN0AdRFS0tL1hESo9gAVHT48OGsIyRGsQGRPM6SEI9iAyJceRCvo6Mj6wiJUWxAJI+zpDSUy+WsIyRGsQGRPM6S0lAsFrOOkBjFBqCijRs3Zh0hMYoNiORxloR4FBsQyeMsCfEoNiCSx1lSGgYHB7OOkBjFBkTyOEtKQx73ZCk2ABWtWLEi6wiJUWwAgkOxAZE8zpIQj2IDInmcJaVhw4YNWUdIjPuxnYXYLvHYLlMf92MDUBdmlnWExCg2AMGh2IBIHmdJiEexARGuPIjX1dWVdYTEKDYgksdZUhr6+vqyjpAYxQagou7u7qwjJEaxAaho+/btWUdIjGIDInmcJSEexQZE8jhLQjyKDYjkcZaUhjxejUGxAZE8zpLS0Nvbm3WExCg2ABWtWrUq6wiJUWwAgkOxAZE8zpIQr6ZiM7Mvm9l+M/uNmX270aGALORxlpSGbdu2ZR0hsarFZmbTJP2jpL+QdJWku8zsqkYHA9KWx1lSGjo7O7OOkFgte2zXSvqNu//W3f9P0hZJf9nYWACmirlz52YdIbFaim2upEOnPR6IlgHAlDS9hnXibnnwkSmrmRUljd73ZcTM9k8mWL3E3bHh8ssv/+yMGTM+PjIy8u7+/fvfPJt+Vmm7gH8vOfj3sqCWlWoptgFJ8097PE/S0IdXcvdeSUxfAWSulrei/yXps2a20MzOlXSnpPwdJgFw1qi6x+bux83sXkn/LmmapEfc/dcNTwYAE9SQj98DgCxx5QGA4FBsAIJDsQEIDsUGIDgUG4DgUGwAgkOxAQgOxQYgOP8PxRPBVgwGzVEAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 360x360 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig,ax=plt.subplots(figsize=(5,5))\n",
    "\n",
    "#viz jug\n",
    "bigjug=plt.Rectangle((0.5,0),1,big,fill=False,\n",
    "                     label='Big Jug')\n",
    "smalljug=plt.Rectangle((2.5,0),1,small,fill=False,\n",
    "                       linestyle='--',\n",
    "                       label='Small Jug')\n",
    "plt.gca().add_patch(bigjug)\n",
    "plt.gca().add_patch(smalljug)\n",
    "\n",
    "#chic design\n",
    "ax.set_xticks([])\n",
    "ax.set_xlim(0,4)\n",
    "ax.set_ylim(0,big+1)\n",
    "ax.legend()\n",
    "\n",
    "#create animations\n",
    "anim=pltani.FuncAnimation(fig,draw_waterjug,\n",
    "                          frames=len(process_dijkstra),\n",
    "                          interval=700,\n",
    "                          fargs=(ax,process_dijkstra))\n",
    "anim.save('water jug.gif')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](./preview/water jug.gif)"
   ]
  },
  {
   "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
}