missionaries and cannibals problems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Missionaries and Cannibals\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "Missionaries and cannibals problem is a famous toy problem in artificial intelligence. You have one boat, three missionaries and three cannibals. The objective is to move everyone from left bank to right bank. There are two constraints. One, the boat can only take two people at most and it cannot operate without people. Two, whenever cannibals outnumber missionaries on each bank, missionaries get eaten.\n",
    "\n",
    "Details of the game could be found in the following link\n",
    "\n",
    "https://en.wikipedia.org/wiki/Missionaries_and_cannibals_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": [
    "#the tricky part is to convert the possibilities into a graph structure\n",
    "#denote a vertex (a,b,c,d,e)\n",
    "#a is the number of cannibals on left bank\n",
    "#b is the number of missionaries on left bank\n",
    "#c is the number of cannibals on right bank\n",
    "#d is the number of missionaries on right bank\n",
    "#e is the location of a boat\n",
    "#denote 0 as the boat is on left bank\n",
    "#1 as the boat is on right bank\n",
    "#what we intend to do is to build up all the possible occasions as vertices\n",
    "#and convert the valid moves from one status to another into edges\n",
    "#weights are 1 for the purpose of dijkstra\n",
    "def check_around():\n",
    "\n",
    "    #to build up vertices\n",
    "    #lets split all the possibilities in two\n",
    "    #when the boat is on left bank and on right bank\n",
    "    #when the boat is on left bank should connect to the scenario when the boat is on right bank\n",
    "    #cuz we wanna ship people from left to right and boat requires a sailor\n",
    "    #vice versa\n",
    "    ADT=graph.graph()\n",
    "    \n",
    "    #lets look at the case when the boat is on left bank\n",
    "    #denote i as number of cannibals on left bank\n",
    "    #denote j as number of missionaries on left bank\n",
    "    #and 3-i is apparently the number of cannibals on right bank\n",
    "    #cuz the sum of cannibals is 3\n",
    "    #the same idea applies to missionaries\n",
    "    #this way would save us a lot of time from iterations\n",
    "    #and the valid edges should be the boat from left bank to right bank\n",
    "    #which is 0 to 1\n",
    "    #the boat can only carry two people\n",
    "    #there are five possible scenarios for crossing river\n",
    "    for i in range(0,4):\n",
    "        for j in range(0,4):\n",
    "            \n",
    "            #two people on boat, carry two cannibals\n",
    "            #the representation of carrying two cannibals is\n",
    "            #from (i,j,3-i,3-j,0) to (i-2,j,3-i+2,3-j,1)\n",
    "            #two cannibals are extracted from left bank and added to the right bank\n",
    "            #missionaries for both banks stay the same\n",
    "            #the boat status changes from 0 to 1\n",
    "            if validate(i-2,j,3-i+2,3-j):\n",
    "                ADT.append((i,j,3-i,3-j,0),(i-2,j,3-i+2,3-j,1),1)\n",
    "                \n",
    "            #two people on boat, carry two missionaries\n",
    "            if validate(i,j-2,3-i,3-j+2):\n",
    "                ADT.append((i,j,3-i,3-j,0),(i,j-2,3-i,3-j+2,1),1)\n",
    "                \n",
    "            #two people on boat, carry one cannibal and one missionary\n",
    "            if validate(i-1,j-1,3-i+1,3-j+1):\n",
    "                ADT.append((i,j,3-i,3-j,0),(i-1,j-1,3-i+1,3-j+1,1),1)\n",
    "            \n",
    "            #only one person on boat, carry one cannibal\n",
    "            if validate(i-1,j,3-i+1,3-j):\n",
    "                ADT.append((i,j,3-i,3-j,0),(i-1,j,3-i+1,3-j,1),1)\n",
    "            \n",
    "            #only one person on boat, carry one missionary\n",
    "            if validate(i,j-1,3-i,3-j+1):\n",
    "                ADT.append((i,j,3-i,3-j,0),(i,j-1,3-i,3-j+1,1),1)\n",
    "\n",
    "    #boat from right to left, vice versa\n",
    "    for i in range(0,4):\n",
    "        for j in range(0,4):\n",
    "            if validate(i+1,j,3-i-1,3-j):\n",
    "                ADT.append((i,j,3-i,3-j,1),(i+1,j,3-i-1,3-j,0),1)\n",
    "            if validate(i,j+1,3-i,3-j-1):\n",
    "                ADT.append((i,j,3-i,3-j,1),(i,j+1,3-i,3-j-1,0),1)\n",
    "            if validate(i+2,j,3-i-2,3-j):\n",
    "                ADT.append((i,j,3-i,3-j,1),(i+2,j,3-i-2,3-j,0),1)\n",
    "            if validate(i,j+2,3-i,3-j-2):\n",
    "                ADT.append((i,j,3-i,3-j,1),(i,j+2,3-i,3-j-2,0),1)\n",
    "            if validate(i+1,j+1,3-i-1,3-j-1):\n",
    "                ADT.append((i,j,3-i,3-j,1),(i+1,j+1,3-i-1,3-j-1,0),1)\n",
    "                \n",
    "    return ADT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#validate the possibility of connecting two scenarios\n",
    "def validate(a,b,c,d):\n",
    "    \n",
    "    #number of missionaries or cannibals for either bank cannot be negative\n",
    "    if a<0 or b<0 or c<0 or d<0:\n",
    "        return False\n",
    "    \n",
    "    #for either bank, missionaries cannot be outnumbered by cannibals\n",
    "    if (a>b and b!=0) or (c>d and d!=0):\n",
    "        return False\n",
    "    else:\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#viz the solution\n",
    "def draw_boat(ind,*args):\n",
    "    \n",
    "    #unpack\n",
    "    ax,process,bateau=args   \n",
    "    left_can,left_mis,right_can,right_mis,boat=process[ind]\n",
    "\n",
    "    #cleanse\n",
    "    ax.collections.clear()\n",
    "        \n",
    "    #viz left bank\n",
    "    ax.scatter(range(1,1+left_can),[2.5]*left_can,color='blue',label='cannibals')\n",
    "    ax.scatter(range(1,1+left_mis),[3]*left_mis,color='green',label='missionaries')\n",
    "    \n",
    "    #viz right bank\n",
    "    ax.scatter(range(10,10+right_can),[2.5]*right_can,color='blue')\n",
    "    ax.scatter(range(10,10+right_mis),[3]*right_mis,color='green')\n",
    "    \n",
    "    #viz boat\n",
    "    bateau.set_xdata([4,5,6] if boat==0 else [7,8,9])    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#generate graph adt\n",
    "ADT=check_around()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length of the process: 11\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,(3,3,0,0,0),(0,0,3,3,1))\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": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length of the process: 11\n",
      "number of vertices DFS has travelled: 12\n"
     ]
    }
   ],
   "source": [
    "#dfs traveled fewer vertices\n",
    "#in this case, dfs surprisingly offers an optimal solution\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,(3,3,0,0,0),(0,0,3,3,1))\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": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length of the process: 11\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,(3,3,0,0,0),(0,0,3,3,1))\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": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "MovieWriter ffmpeg unavailable.\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAASwAAAElCAYAAABect+9AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAFXRJREFUeJzt3XtM1ff9x/HXgVLhiJcps82qBZrUaeDA4Y7aAYq1RiZ1DmosWlg30Dm3/NrNZSuzIC3LNpvV+cdmNau1LTMMe1F3i1MxalpjMaJUa0fXotArhZWMIlrk8/uDeVoElPvhU56PhNh+e87n+6HNnvuer1/eOowxAgAb+Hh7AwDQWwQLgDUIFgBrECwA1iBYAKxBsABYg2ABsAbBAmANggXAGgQLgDVu6suLg4KCTEhIyBBtBcBodeLEiY+NMV+90ev6FKyQkBBVVFT0f1cA0A2Hw3G+N6/jIyEAaxAsANYgWACs0ad7WICtPvvsM9XV1am1tdXbWxnV/P39NXXqVPn5+fXr/QQLo0JdXZ3GjRunkJAQORwOb29nVDLGqKGhQXV1dQoNDe3XGnwkxKjQ2tqqyZMnEysvcjgcmjx58oCucrnCwpfehg0bvHLegoICr5x3JBvo/2FwhQUMk5qaGoWHhw94nWeeeUbvvffeIOzIPgQLsAzBAjAs2tralJ2drYiICGVkZKilpUUHDhxQVFSUXC6XHnzwQV26dEmSVFRUpLi4OIWHhysvL0/GGO3atUsVFRXKysqS2+3WxYsXvfwdDS+CBQyjN998U3l5eTp9+rTGjx+v3/72t8rJyVFpaamqqqrU1tamP/zhD5KktWvX6rXXXtPrr7+uixcv6i9/+YsyMjIUGxurkpISVVZWKiAgwMvf0fAiWMAwmjZtmubMmSNJWrFihQ4cOKDQ0FBNnz5dkpSdna3Dhw9LksrLy5WQkCCXy6WDBw/qzJkzXtv3SMHvEgLDqLe/S9ba2qo1a9aooqJC06ZNU2FhIQ+9iissYFhduHBBr776qiRp586dmj9/vmpqavTWW29Jkp577jklJyd74hQUFKTm5mbt2rXLs8a4ceP03//+d/g3PwIQLGAYzZw5Uzt27FBERIQaGxv10EMPafv27crMzJTL5ZKPj49Wr16tiRMnKjc3Vy6XS0uWLFFcXJxnjZycHK1evXpU3nR3GGN6/eLY2FjDPCzYhgdHR5Y33nhDM2fO7HTM4XCcMMbE3ui93MPCl15BQUG3/yOBffhICMAaBAuANQgWAGsQLADWIFgArEGwgGESGBh4w9ds3rxZM2fOVFZWlg4dOqRXXnml29cVFhbqiSeeGJR9paSkWPPH9/FYA0alF5OS1NrQMGjr+U+erKX/+xnAgfj973+vv//97woNDVVhYaECAwM1e/bsQdjhlwNXWBiVBjNW/Vlv48aNiouLU0REhOcB09WrV+vtt99Wenq6nnzySW3ZskVPPvmk3G63jhw50mWNU6dOad68ebrzzju1bds2SVJzc7NSU1MVHR0tl8ul3bt3S+oYHjhz5kzl5uYqLCxMCxYs6PKUfHt7u7Kzs/WLX/yiP/8KhgVXWMAw27dvn6qrq3X8+HEZY5Senq7Dhw9ry5Yt+sc//qHy8nIFBQWpqalJgYGB+slPftLtOqdPn9axY8f06aefKioqSmlpaZoyZYpeeukljR8/Xh9//LESExOVnp4uSaqurtbOnTu1bds23XfffXrhhRe0YsUKSR1zurKyshQeHq78/Pxh+3fRV1xhAcNs37592rdvn6KiohQdHa1z586purq6z+vce++9CggIUFBQkObOnesJ4COPPKKIiAjNnz9f7777rj788ENJUmhoqNxutyQpJiZGNTU1nrVWrVo14mMlcYUFDDtjjH7+859r1apVA1rn2lE1DodDJSUlqq+v14kTJ+Tn56eQkBDP5IcxY8Z4Xuvr69vpI+Hs2bNVXl6uH//4x/L39x/QvoYSV1jAMLvnnnv09NNPq7m5WZL07rvv6qOPPuryuhuNkdm9e7daW1vV0NCgQ4cOKS4uTk1NTZoyZYr8/PxUXl6u8+fP92pP3/3ud7Vo0SJlZmaqra2tf9/YMCBYwDBbsGCB7r//fs2aNUsul0sZGRndhmnx4sV66aWXerzpHh8fr7S0NCUmJmr9+vX62te+pqysLFVUVHjGKM+YMaPX+3r44YcVHR2tlStXqr29fUDf41BhvAxGhWunNYzUxxpGA8bLAH1EXOzER0IA1iBYAKxBsABYg2ABsAbBAmANggV4yaJFi/TJJ59c9zU9jX6prKzU3/72t27f88wzz2jt2rWDssecnJxOfyait/FYA0anF2+VWj8cvPX8b5GWftCrlxpjZIzpMTi9UVlZqYqKCi1atKjfa9iIKyyMToMZq16sd3W8y5o1axQdHa3a2lqFhITo448/liQ99thjmjFjhu6++24tX76803C+srIyxcfHa/r06Tpy5IguX76sRx99VKWlpXK73SotLe1yvtraWi1cuFBf//rXO/25jEuWLFFMTIzCwsK0detWz/HAwEDl5+crMjJSiYmJnh+Y/qL169crJyfHq0/BEyxgmLz55pt64IEHdPLkSQUHB3uOV1RU6IUXXtDJkyf14osvdvkI2NbWpuPHj2vTpk3asGGDbr75ZhUVFWnZsmWqrKzUsmXLupzr+PHjKikpUWVlpcrKyjxrPv300zpx4oQqKiq0efNmNfzvaf9PP/1UiYmJOnXqlJKSkjzzta766U9/qo8++kjbt2+Xj4/3skGwgGESHBysxMTELsePHj3qGRUzbtw4LV68uNM/X7p0qaSuI2Gu5+6779bkyZMVEBCgpUuX6ujRo5I6RjBfvYqqra31jLW5+eab9c1vfrPb8zz22GP65JNP9NRTT3WZEDHcuIcFDJOxY8d2e/xGP897dSyMr69vrycpdDd65tChQ9q/f79effVVOZ1OpaSkeEbP+Pn5ed5z7Xni4uJ04sQJNTY2atKkSb06/1DhCgvwsrvuukt79+5Va2urmpub9de//vWG77nR6Jl//vOfamxs1MWLF/Xyyy9rzpw5ampq0le+8hU5nU6dO3dOx44d69X+Fi5cqJ/97GdKS0u77jmHA8ECvCwuLk7p6emKjIzU0qVLFRsbqwkTJlz3PXPnztXZs2d7vOl+1113aeXKlXK73fr2t7+t2NhYLVy4UG1tbYqIiND69eu7/Xjak8zMTOXm5io9Pb3LLPjhxHgZjApdRpp48bGG7jQ3NyswMFAtLS1KSkrS1q1bFR0dPXj7G0EYLwP01QDiMhTy8vJ09uxZtba2Kjs7+0sbq4EiWMAI8Kc//cnbW7AC97AAWINgAbAGwQJgDYIFwBoEC/gSePTRR7V//35J6vRD1b0xmONohhq/Swh8CRQVFXl7C8OCKyygGyUlUkiI5OPT8WtJycDXfPbZZxUREaHIyEitXLlSe/fuVUJCgqKiojR//nzPSJfCwkI9+OCDSklJ0R133KHNmzdL+nxETW5ursLCwrRgwQLPU+fXDtrbuHGj4uPjFR8fr7feekuSejzfF5WVlSk8PFyRkZFKSkoa+Dc92K4OE+vNV0xMjAFsdPbs2V6/9vnnjXE6jZE+/3I6O4731+uvv26mT59u6uvrjTHGNDQ0mMbGRtPe3m6MMWbbtm3m4YcfNsYYU1BQYGbNmmVaW1tNfX29mTRpkrl8+bJ55513jK+vrzl58qQxxpjMzEzz3HPPGWOMyc7ONmVlZcYYY4KDg83jjz9ujDFmx44dJi0tzRhjejzf9u3bzQ9+8ANjjDHh4eGmrq7OGGPMf/7zn/5/w9fR3X8LSRWmFw3iIyFwjfx8qaWl87GWlo7jWVn9W/PgwYPKyMhQUFCQJGnSpEmqqqrSsmXL9P777+vy5csKDQ31vD4tLU1jxozRmDFjNGXKFM/VUGhoqNxut6Trj5tZvny559eHHnpIklRXV9fj+a6aM2eOcnJydN9993nG2owkfCQErnHhQt+O94YxpsvIlx/+8Idau3atqqqq9NRTT3lGvUifj5SROo976en4tb54rqt/fb3zXbVlyxY9/vjjqq2tldvt9gz4GykIFnCN22/v2/HeSE1N1Z///GdPABobG9XU1KTbbrtNkrRjx47+L96NqxMcSktLNWvWLEnq1fn+/e9/KyEhQUVFRQoKClJtbe2g7mug+EgIXKO4WMrL6/yx0OnsON5fYWFhys/PV3Jysnx9fRUVFaXCwkJlZmbqtttuU2Jiot55552Bb/5/Ll26pISEBLW3t2vnzp2S1KvzrVu3TtXV1TLGKDU1VZGRkYO2p8HAeBmMCt2NNLmekpKOe1YXLnRcWRUX9//+FTpjvAwwyLKyCNRIxD0sANYgWACsQbAAWINgAbAGwQJgDYIFjCB79uzRr371qz6/b/bs2UOwm862bNmiZ599dsjPcz08h4VRoa/PYaGztrY23XTT4DwFNZDnsLjCArpRUlWikE0h8tngo5BNISqpGvh8mZqaGs2YMUPf+973FB4erqysLO3fv19z5szRnXfeqePHj3captfdqJczZ84oPj5ebrdbERERqq6uliQFBgZK6viZxXXr1ik8PFwul8vzIzqHDh1SSkqKMjIyNGPGDGVlZenqxUpRUZHi4uIUHh6uvLw8z/GUlBQ98sgjSk5O1u9+9zsVFhbqiSeekNTxIzwLFy5UTEyMvvGNb+jcuXM97nlQ9Wakg2G8DCzXp/Eyp583zmKnUaE8X85ip3n+9ADmyxjjGQ9z+vRpc+XKFRMdHW2+853vmPb2dvPyyy+be++994ajXtauXWue/9+cm0uXLpmWlhZjjDFjx441xhiza9cuM3/+fNPW1mY++OADM23aNPPee++Z8vJyM378eFNbW2uuXLliEhMTzZEjR4wxHaNurlqxYoXZs2ePMcaY5ORk8/3vf9/zzwoKCszGjRuNMcbMmzfP/Otf/zLGGHPs2DEzd+7cHvd8rYGMl+EKC7hG/oF8tXzWeb5My2ctyj+QP+C1Q0ND5XK55OPjo7CwMKWmpsrhcMjlcnUZFXN11Mu2bdt05coVSdKsWbP0y1/+Ur/+9a91/vx5BQQEdHrP0aNHtXz5cvn6+uqWW25RcnKyXnvtNUlSfHy8pk6dKh8fH7ndbs/5ysvLlZCQIJfLpYMHD+rMmTOe9ZYtW9ble2hubtYrr7yizMxMud1urVq1Su+//36Pex5MBAu4xoWm7ufI9HS8L744HsbHx8fz9z4+Pl1GxXQ36uX+++/Xnj17FBAQoHvuuUcHDx7s9B5znXvS3Y2maW1t1Zo1a7Rr1y5VVVUpNze309iZsWPHdlmnvb1dEydOVGVlpefrjTfe6HHPg4lgAde4fUL3c2R6Oj5Uuhv18vbbb+uOO+7Qj370I6Wnp+v06dOd3pOUlKTS0lJduXJF9fX1Onz4sOLj43s8x9U4BQUFqbm5udOY5Z6MHz9eoaGhKisrk9QRyVOnTvW458FEsIBrFKcWy+nn7HTM6edUceoA5sv0w7p16+RyuRQeHq6kpCRFRkaqtLRU4eHhcrvdOnfunB544IFO7/nWt77lmRs/b948/eY3v9Gtt97a4zkmTpyo3NxcuVwuLVmyRHFxcb3aW0lJif74xz8qMjJSYWFh2r17d497Hkw81oBRoc/jZapKlH8gXxeaLuj2CberOLVYWS7GNwwGxssAgyzLlUWgRiA+EgKwBsECYA2ChVGjL/drMTQG+t+AYGFU8Pf3V0NDA9HyImOMGhoa5O/v3+81uOmOUWHq1Kmqq6tTfX29t7cyqvn7+2vq1Kn9fj/Bwqjg5+fX7Z90DLvwkRCANQgWAGsQLADWIFgArEGwAFiDYAGwBsECYA2CBcAaBAuANQgWAGsQLADWIFgArEGwAFiDYAGwBsECYA2CBcAaBAuANQgWAGsQLADWIFgArEGwAFiDYAGwBsECYA2CBcAaBAuANQgWAGsQLADWIFgArEGwAFiDYAGwBsECYA2CBcAaBAuANQgWAGsQLADWIFgArEGwAFiDYAGwBsECYA2CBcAaBAuANQgWAGsQLADWIFgArEGwAFiDYAGwBsECYA2CBcAaBAuANQgWAGsQLADWIFgArEGwAFiDYAGwBsECYA2CBcAaBAuANQgWAGsQLADWIFgArEGwAFiDYAGwBsECYA2CBcAaBAuANQgWAGsQLADW8FqwSqpKFLIpRD4bfBSyKUQlVSUjdt2h2iuAvrnJGyctqSpR3t48tXzWIkk633ReeXvzJElZrqwRte5Q7RVA3zmMMb1+cWxsrKmoqBjwSUM2heh80/kux4MnBKvm/2pG1LpDtVcAn3M4HCeMMbE3ep1XPhJeaLrQp+PeXHeo9gqg77wSrNsn3N6n495cd6j2CqDvvBKs4tRiOf2cnY45/ZwqTi0ecesO1V4B9J1XgpXlytLWxVsVPCFYDjkUPCFYWxdvHfBN7KFYd6j2CqDvvHLTHQC+aETfdAeA/iBYAKxBsABYg2ABsAbBAmANggXAGgQLgDUIFgBrECwA1iBYAKxBsABYw3sjkkukkBDJx6fj15JBmjo8FOsO1V4B9JExptdfMTExZjA8/7wxTqcx0udfTmfH8ZG27lDtFcDnJFWYXjTIOyOSQ6TzXacOKzhYqqkZWesO1V4BfG5ET2u40MN04Z6Oe3PdodorgL7zzojkHqYL93Tcm+sO1V4B9J13RiQXS87OU4fldHYcH2nrDtVeAfSdd0YkZ0lbt3bcB3I4On7durXj+Ehbd6j2CqDvGJEMwOtG9E13AOgPggXAGgQLgDUIFgBrECwA1iBYAKxBsABYg2ABsAbBAmANggXAGjd5ewOjzYYNG7y9hUFVUFDg7S1gFOEKC4A1CBYAaxAsANYgWACs4fWb7i8mJam1ocHb2+gV/8mTtfTwYW9vA182L94qtX7o7V30jv8t0tIPvHZ6r19h2RIrya69wiK2xEry+l69HiwA6C2CBcAaBAuANbx+03204clwoP+4wgJgDYIFwBoEC4A1CBYAaxAsANYgWACsQbAAWINgAbAGwQJgDYIFwBoEC4A1CBYAaxAsANYgWACsQbAAWINgAbAGwQJgDYIFwBoEC4A1CBYAaxAsANYgWACsQbAAWINgAbAGwQJgDYIFwBoEC4A1CBYAaxAsANYgWACsQbAAWINgAbAGwQJgDYIFwBoEC4A1CBYAaxAsANYgWACsQbAAWINgAbAGwQJgDYIFwBoEC4A1CBYAaxAsANYgWACsQbAAWINgAbAGwQJgDYIFwBoEC4A1CBYAaxAsANYgWACsQbAAWINgAbAGwQJgDYIFwBoEC4A1CBYAaxAsANYgWACsQbAAWINgAbAGwQJgDYIFwBoEC4A1CBYAaxAsANYgWACsQbAAWMNhjOn9ix2Oeknnh247AEapYGPMV2/0oj4FCwC8iY+EAKxBsABYg2ABsAbBAmANggXAGgQLgDUIFgBrECwA1iBYAKzx/1BZq0T3TyMOAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 360x360 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig,ax=plt.subplots(figsize=(5,5))\n",
    "\n",
    "#viz banks\n",
    "leftbank=plt.Rectangle((1,0),2,2,color='brown',\n",
    "                     label='left bank')\n",
    "rightbank=plt.Rectangle((10,0),2,2,color='orange',\n",
    "                       label='right bank')\n",
    "plt.gca().add_patch(leftbank)\n",
    "plt.gca().add_patch(rightbank)\n",
    "\n",
    "ax.scatter([1,2,3],[2.5,2.5,2.5],color='blue',label='cannibals')\n",
    "ax.scatter([1,2,3],[3,3,3],color='green',label='missionaries')\n",
    "ax.scatter([],[],color='blue')\n",
    "ax.scatter([],[],color='green')\n",
    "bateau=ax.plot([4,5,6],[2,2,2],linewidth=10,color='grey',label='boat')[0]\n",
    "\n",
    "ax.legend(loc='upper right')\n",
    "ax.set_xticks([])\n",
    "ax.set_yticks([])\n",
    "ax.set_xlim(0,13)\n",
    "ax.set_ylim(0,7)\n",
    "\n",
    "anim=pltani.FuncAnimation(fig,draw_boat,\n",
    "                          frames=len(process_dijkstra),\n",
    "                          interval=900,\n",
    "                          fargs=(ax,process_dijkstra,bateau))\n",
    "anim.save('missionaries and cannibals.gif')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](./preview/missionaries and cannibals.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
}