a_star maze.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A* Algorithm\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "Previously we have talked about Dijkstra's algorithm, which is a special case of A\\* algorithm, it's time to introduce the generalized form. A\\* algorithm is an algorithm to find the shortest path as well. Besides the distance from the beginning to the current vertex, A\\* has one more criterion which is called heuristic function. Heuristic function is an estimation of the potential steps from the current vertex to the end. A\\* intends to choose the vertex with the least distance from the beginning and potentially the least distance to the end. As two distances are taken into consideration, A\\* has higher space complexity than Dijkstra. The tradeoff is its faster execution time than Dijkstra. Given the heuristic function, it is supposed to travel fewer vertices than Dijkstra. Btw, in Dijkstra, the heuristic function equals to zero.\n",
    "\n",
    "Details of Dijkstra's algorithm could be found in the following link\n",
    "\n",
    "https://github.com/je-suis-tm/graph-theory/blob/master/dijkstra%20shortest%20path.ipynb\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "### Heuristic\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "In this case, we choose walking out of a maze as an example. There are three different ways to calculate the heuristic function. \n",
    "\n",
    "###### Manhattan Distance\n",
    "\n",
    "We are gonna use Manhattan distance since we are only allowed to move up, down, left and right in the maze. Think of the maze as street blocks in Manhattan. The only way for a taxi travelling from one point to another is to drive through twists and turns. Let's denote start as (x,y), end as (i,j). The heuristic for Manhattan distance is \n",
    "\n",
    "$$\n",
    "|x-i|+|y-j|\n",
    "$$\n",
    "\n",
    "###### Diagonal Distance\n",
    "\n",
    "In order to use diagonal distance, we must be able to move like a queen on the chessboard with eight different directions. The idea of Avinguda Diagonal may work in Barcelona but apparently not in a maze. The heuristic function of Barcelona distance is \n",
    "\n",
    "$$\n",
    "max(|x-i|,|y-j|)+(\\sqrt{2}-1) \\times min(|x-i|,|y-j|)\n",
    "$$\n",
    "\n",
    "###### Euclidean Distance\n",
    "\n",
    "Euclidean distance is widely used in geometry. This heuristic function requires us to have the flexibility to move whatever directions we want. Every angle should be valid instead of $90^{\\circ}$ in Manhattan distance or $45^{\\circ}$ in Barcelona distance. The heuristic function of Euclidean distance is \n",
    "\n",
    "$$\n",
    "\\sqrt{(x-i)^2+(y-j)^2}\n",
    "$$\n",
    "\n",
    "&nbsp;\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "os.chdir('K:/ecole/github')\n",
    "import matplotlib.pyplot as plt\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 structure of a* is similar to dijkstra's\n",
    "#we compute distance from the beginning to the current vertex\n",
    "#as well as the heuristic function\n",
    "#for each vertex we iterate, we pick the minimum sum of both\n",
    "#until we reach the destination\n",
    "def a_star(ADT,start,end):\n",
    "    \"\"\"A* Algorithm,\n",
    "    a generalized Dijkstra's algorithm with heuristic function to reduce execution time\"\"\"\n",
    "    \n",
    "    #all weights in dcg must be positive \n",
    "    #otherwise we have to use bellman ford instead\n",
    "    # https://github.com/je-suis-tm/graph-theory/blob/master/bellman_ford%20forex%20arbitrage.ipynb\n",
    "    neg_check=[j for i in ADT.reveal() for j in ADT.reveal()[i].values()]\n",
    "    assert min(neg_check)>=0,\"negative weights are not allowed, please use Bellman-Ford\"\n",
    "    \n",
    "    #queue in a* is the same as the queue in dijkstra\n",
    "    queue={}\n",
    "    queue[start]=0\n",
    "    \n",
    "    #same as dijkstra\n",
    "    #distance keeps track of distance from starting vertex to any vertex\n",
    "    distance={} \n",
    "    \n",
    "    #heuristic keeps track of distance from ending vertex to any vertex\n",
    "    heuristic={}\n",
    "    \n",
    "    #route is a dict of the summation of distance and heuristic\n",
    "    route={}\n",
    "    \n",
    "    #criteria\n",
    "    for i in ADT.vertex():\n",
    "        \n",
    "        #same as dijkstra\n",
    "        distance[i]=float('inf')\n",
    "        \n",
    "        #manhattan distance\n",
    "        heuristic[i]=abs(i[0]-end[0])+abs(i[1]-end[1])\n",
    "        \n",
    "    #same as dijkstra\n",
    "    distance[start]=0\n",
    "\n",
    "    #pred keeps track of how we get to the current vertex\n",
    "    pred={}\n",
    "    \n",
    "    while queue:\n",
    "        \n",
    "        #same as dijkstra\n",
    "        current=min(queue,key=queue.get)\n",
    "        queue.pop(current)\n",
    "        \n",
    "        #find the minimum summation of both distances\n",
    "        minimum=float('inf')\n",
    "\n",
    "        for j in ADT.edge(current):\n",
    "            \n",
    "            #check if the current vertex can construct the optimal path\n",
    "            #from the beginning and to the end\n",
    "            distance[j]=distance[current]+ADT.weight(current,j)\n",
    "            route[j]=distance[j]+heuristic[j]\n",
    "            if route[j]<minimum:\n",
    "                minimum=route[j]\n",
    "\n",
    "        for j in ADT.edge(current):\n",
    "            \n",
    "            #we only append unvisited and unqueued vertices\n",
    "            #note that we could have two vertices with the minimum summation\n",
    "            #that is why we use a loop to find all valid vertices\n",
    "            if (route[j]==minimum) and (ADT.go(j)==0) and (j not in queue):\n",
    "                queue[j]=route[j]\n",
    "                pred[j]=current\n",
    "        \n",
    "        #each vertex is visited only once\n",
    "        ADT.visit(current)\n",
    "        \n",
    "        #traversal ends when the target is met\n",
    "        if current==end:\n",
    "            break        \n",
    "    \n",
    "    #create the shortest path by backtracking\n",
    "    #trace the predecessor vertex from end to start\n",
    "    previous=end\n",
    "    path=[]\n",
    "    while pred:\n",
    "        path.insert(0, previous)\n",
    "        if previous==start:\n",
    "            break\n",
    "        previous=pred[previous]\n",
    "    \n",
    "    #note that if we cant go from start to end\n",
    "    #we may get inf for distance[end]\n",
    "    #additionally, the path may not include start position\n",
    "    return distance[end],path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#the difficult part of a maze problem is to convert maze into a graph adt\n",
    "#assume maze is an i*j matrix\n",
    "#we can convert it into a nested list or a matrix\n",
    "#then assign coordinates to each vertex, the same as the index\n",
    "#the top left would be (0,0)\n",
    "#the bottom right would be (i-1,j-1)\n",
    "def check_around(matrix,maze,i,j):\n",
    "    \n",
    "    #for a vertex with coordinate (i,j)\n",
    "    #we wanna check its top, bottom, left and right\n",
    "    #which are (i-1,j),(i+1,j),(i,j-1),(i,j+1)\n",
    "    #if those vertices mentioned above are not walls\n",
    "    #'+' denotes wall in the maze, space denotes available path\n",
    "    #we will append those edges into the graph adt   \n",
    "    for k,l in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "        try:\n",
    "            if matrix[k][l]!='+':\n",
    "                maze.append((i,j),(k,l),1)\n",
    "        \n",
    "        #for boundary vertices, we wont find all four vertices near them\n",
    "        #e.g. only bottom (1,0) and right (0,1) for the top left (0,0)\n",
    "        #thus, we need to exclude index error\n",
    "        except IndexError:\n",
    "            pass\n",
    "        \n",
    "    return maze"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#before we make comparison of how a* outperforms dijkstra\n",
    "#we would also love to compare the result with bfs and dfs\n",
    "#although some minor changes will be applied to the standard bfs and dfs\n",
    "#bfs_path,dfs_path would give us the path and the length of the path\n",
    "#unlike the organic bfs or dfs, we stop the iteration when we reach the destination\n",
    "#details of bfs and 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",
    "def bfs_path(ADT,start,end):\n",
    "    \"\"\"Breadth First Search to find the path from start to end\"\"\"\n",
    "    \n",
    "    #create a queue with rule of first-in-first-out\n",
    "    queue=[]\n",
    "    queue.append(start)\n",
    "    \n",
    "    #pred keeps track of how we get to the current vertex\n",
    "    pred={}\n",
    "    \n",
    "    while queue:\n",
    "                \n",
    "        #keep track of the visited vertices\n",
    "        current=queue.pop(0)\n",
    "        ADT.visit(current)\n",
    "                \n",
    "        for newpos in ADT.edge(current):\n",
    "            \n",
    "            #visit each vertex once\n",
    "            if ADT.go(newpos)==0 and newpos not in queue:\n",
    "                queue.append(newpos)\n",
    "                pred[newpos]=current\n",
    "                \n",
    "        #traversal ends when the target is met\n",
    "        if current==end:\n",
    "            break\n",
    "\n",
    "    #create the path by backtracking\n",
    "    #trace the predecessor vertex from end to start\n",
    "    previous=end\n",
    "    path=[]\n",
    "    while pred:\n",
    "        path.insert(0, previous)\n",
    "        if previous==start:\n",
    "            break\n",
    "        previous=pred[previous]\n",
    "    \n",
    "    #note that if we cant go from start to end\n",
    "    #we may get inf for distance\n",
    "    #additionally, the path may not include start position\n",
    "    return len(path)-1,path\n",
    "\n",
    "\n",
    "#to make our life easier, we use dfs iteration instead of dfs recursion\n",
    "def dfs_path(ADT,start,end):\n",
    "    \"\"\"Depth First Search to find the path from start to end\"\"\"\n",
    "    \n",
    "    queue=[]\n",
    "    queue.append(start) \n",
    "    \n",
    "    #pred keeps track of how we get to the current vertex\n",
    "    pred={}\n",
    "    \n",
    "    #the loop is the backtracking part when it reaches cul-de-sac\n",
    "    while queue:\n",
    "        \n",
    "        #keep track of the visited vertices\n",
    "        current=queue.pop(0)\n",
    "        ADT.visit(current)\n",
    "        \n",
    "        #priority queue\n",
    "        smallq=[]        \n",
    "        \n",
    "        #find children and add to the priority\n",
    "        for newpos in ADT.edge(current):\n",
    "            if ADT.go(newpos)==0:\n",
    "                \n",
    "                #if the child vertex has already been in queue\n",
    "                #move it to the frontline of queue\n",
    "                if newpos in queue:\n",
    "                    queue.remove(newpos)\n",
    "                smallq.append(newpos)\n",
    "                pred[newpos]=current\n",
    "                \n",
    "        queue=smallq+queue\n",
    "        \n",
    "        #traversal ends when the target is met\n",
    "        if current==end:\n",
    "            break\n",
    "            \n",
    "    #create the path by backtracking\n",
    "    #trace the predecessor vertex from end to start\n",
    "    previous=end\n",
    "    path=[]\n",
    "    while pred:\n",
    "        path.insert(0, previous)\n",
    "        if previous==start:\n",
    "            break\n",
    "        previous=pred[previous]\n",
    "    \n",
    "    #note that if we cant go from start to end\n",
    "    #we may get inf for distance\n",
    "    #additionally, the path may not include start position\n",
    "    return len(path)-1,path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#viz\n",
    "def maze_viz(matrix,start,end,route=None):\n",
    "\n",
    "    #prepare walls for viz\n",
    "    #for available paths, we just leave em blank\n",
    "    walls=[(i,j) for i in range(len(matrix)) for j in range(len(matrix[0])) if matrix[i][j]=='+']\n",
    "    \n",
    "    if route:\n",
    "        \n",
    "        #create markers for the optimal path\n",
    "        #direction is derived from the difference\n",
    "        #between the current state and the previous state\n",
    "        direction=[]\n",
    "        for i in range(1,len(route)):\n",
    "            if route[i][0]-route[i-1][0]>0:\n",
    "                direction.append('^')\n",
    "            elif route[i][0]-route[i-1][0]<0:\n",
    "                direction.append('v')        \n",
    "            elif route[i][1]-route[i-1][1]>0:\n",
    "                direction.append('>')\n",
    "            else:\n",
    "                direction.append('<')  \n",
    "\n",
    "        #remove the start\n",
    "        direction.pop(0)\n",
    "\n",
    "    #viz\n",
    "    ax=plt.figure(dpi=100).add_subplot(111)\n",
    "\n",
    "    #remove boundaries\n",
    "    for i in ['top','bottom','right','left']:\n",
    "        ax.spines[i].set_visible(False)\n",
    "\n",
    "    #walls\n",
    "    plt.scatter([i[1] for i in walls],[i[0] for i in walls],\n",
    "                marker='X',s=100,color='black')\n",
    "\n",
    "    #starting point\n",
    "    plt.scatter(start[1],start[0],marker='*',\n",
    "                s=100,color='gold')\n",
    "    \n",
    "    #walk out of the maze\n",
    "    if route:\n",
    "        \n",
    "        #remove start and end from route\n",
    "        for i in range(len(route)-2):\n",
    "            plt.scatter(route[i+1][1],route[i+1][0],\n",
    "                        marker=direction[i],color='silver')\n",
    "\n",
    "    #ending point\n",
    "    plt.text(end[1],end[0],'EXIT',color='red',\n",
    "         horizontalalignment='center',\n",
    "         verticalalignment='center')\n",
    "    plt.xticks([])\n",
    "    plt.yticks([])\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#read the maze file\n",
    "#it can be downloaded from the data subfolder\n",
    "# https://github.com/je-suis-tm/graph-theory/blob/master/data/maze.txt\n",
    "f=open('maze.txt','r')\n",
    "text=f.read()\n",
    "matrix=[list(i) for i in text.splitlines()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "#create graph adt\n",
    "maze=graph.graph()\n",
    "\n",
    "for i in range(len(matrix)):\n",
    "    for j in range(len(matrix[0])):\n",
    "        \n",
    "        #for vertices in the maze\n",
    "        #'S' is the starting point\n",
    "        #when we find it, we set the start variable\n",
    "        #and dont forget to append start into graph adt\n",
    "        if matrix[i][j]=='S':\n",
    "            start=(i,j)\n",
    "            maze=check_around(matrix,maze,i,j)\n",
    "            \n",
    "        #when we find ' ', we use check_around function to add edges\n",
    "        elif matrix[i][j]==' ':\n",
    "            maze=check_around(matrix,maze,i,j)\n",
    "            \n",
    "            #if there is a breach on the boundary wall\n",
    "            #we consider it as exit\n",
    "            #we assume there is only one exit in this maze\n",
    "            #we can also change the destination to somewhere inside the maze\n",
    "            #in that case we have to consider the situation \n",
    "            #what if we cannot get to the destination\n",
    "            if (i==0) or (i==len(matrix)-1) or (j==0) or (j==len(matrix[0])-1):\n",
    "                end=(i,j)\n",
    "                \n",
    "        #when we find '+', we skip the brick wall\n",
    "        else:\n",
    "            pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAewAAAFJCAYAAABZ+x49AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3U+oLHlW4PETt9PMtG0QbRvd3NddAUVP/VLQHFfKMG4EZWAQmYFpdNEudeVqXMyiQTe24MZdr2zB1dALYZbSI8VbtQFaNGhZWAPCq0wab1ptMz30jYjOrjOL7PteZt6o+zL+/CLOyd/3A5fsquh73jnnF/FOZkRWRKaqAgAAbLuZOgEAAPB6DGwAABxgYAMA4AADGwAABxjYAAA4wMAGAMABBjYAAA4wsAEAcICBDQCAAwxsAAAcYGADAOAAAxsAAAcY2AAAODDr8bs85gsAgG6ytr/AJ2wAABxgYAMA4AADGwAABxjYAAA4wMAGAMCBSQd2XddSVVXjtrIspa5r4jmO5yFH4hFvyngeciRev3iDUtWuP73c3d1pCEHzPNfNZnOybbPZaJ7nGkLQu7s74jmM5yFH4hGPY4R4MeO9Ruu5O8nAvru707feektns5nOZjN94403XjZns9noG2+88XLbW2+99drmEM9WPA85Eo94HCPEixnvAvYH9nFT5HDzlZfNKYriZVOOtz3VHOLZiuchR+IRj2OEeLHX+AK2B3ZVVRpCOCn8uAHHr+fbQghaVRXxDMfzkCPxiMcxQrzYa3yh1nN31C+dqaqUZdm4bb/fn7yeK8vy8A6DeGbjeciReMTjGCFezHhRdZny2uOU+PG1ADl7x9L083Ba4vwLAMSzGc9DjsQjHscI8WKv8QVsnxJ/cGlzLm0K8WzF85Aj8YjHMUK8mPEu4GNgq6oWRfFkUx5+iqIgnsN4HnIkHvE4RogXM95r+BjY1t8ZEa9fPA85Eo94HCPEixnvAvYHtvVrD8TrF89DjsQjHscI8WKv8QVsD+z7+3vN8/ziphw3J89zLcuSeIbjeciReMTjGCFe7DW+UOu5O+p/1nVzcyPL5bJx22w2O3k9t1wuJcsy4hmO5yFH4hGPY4R4MeNF1WXKa49T4tbvUEO8fvE85Eg84nGMEC/2Gl/A9inxB9bvAUs87pNMPOLFjOchR+JxL/GX7u5sP2WFeP3ieciReMTjGCFezHiv0XruZqp6+fnzU51/8UFd16KqslgsHm2rqkqyLJP5fE48p/E85Eg84nGMEC9mvCe0vvg96cAGACBRrQf2qN8SBwAA3TCwAQBwgIENAIADDGwAABxgYAMA4AADGwAABxjYAAA4wMAGAMABBjYAAA5MOrDrupaqqhq3lWUpdV0Tb8R4MXjIcUjW6yU/TM36GlvOb7KBvdvtZL1eSwhBttvtybbtdiur1UrW67XsdjvijRAvBg85Dsl6veSHqVlfY+v58XhN4kXhIcchWa+X/DA162vM4zUbWH/weGrxYvCQ45Cs10t+mJr1NZ4oP9sDu6oqDSGcFH7cgOPX820hBK2qingDxovBQ45Dsl4v+WFq1td4wvxaz91Rr2GrqpRl2bhtv9+fvJ4ry/LwDoN4g8WLwUOOQ7JeL/lhatbX2Hp+J7pMee1xSvz4WoCcvWNp+jm/lkC8YePF4CHHIVmvl/wwNetrPFF+tk+JP7i0OZc2hXg2dnpvOQ7Jer3kh6lZX+MJ8vMxsFVVi6K46J1MURTEGyFeDB5yHJL1eskPU7O+xiPn52NgW//EmVq8GDzkOCTr9ZIfpmZ9jfmE3cD6Nd3U4sXgIcchWa+X/DA162vMNewG9/f3muf5xU05bk6e51qWJfEGjBeDhxyHZL1e8sPUrK/xhPm1nruj/mddNzc3slwuG7fNZrOT13PL5VKyLCPegPFi8JDjkKzXS36YmvU1tp7fiS5TXnucErd+56/U4sXgIcchWa+X/DA162vMnc6eYP3e2qnFi8FDjkOyXi/5YWrW15h7iT/h7u5OQwia5/mjC/ebzUbzPNcQwsVNIV6/eDF4yHFI1uslP0zN+hqPnF/ruZupauez6V1/8UFd16KqslgsHm2rqkqyLJP5fE68keLF4CHHIVmvl/wwNetrPGJ+rS9+TzqwAQBIVOuBPeq3xAEAQDcMbAAAHGBgAwDgAAMbAAAHGNgAADjAwAYAwAEGNgAADjCwAQBwgIENAIADkw7suq6lqqrGbWVZSl3XI2cEXDfrx5z1/B75wXd7h7Bes/X8hma53skG9m63k/V6LSEE2W63J9u2262sVitZr9ey2+0myhC4LtaPOev5PVK+I/L+pw+vHVmv2Xp+QzNfb5cnhqixx2sCeJr1Y856fo3+5b+r/qOo/svvd/p16zVbz29oPF6zgfUHmQPXxvoxZz2/Rh99pPr+s8PAfv+zh39uwXrN1vMb2kT12h7YVVVpCOGk8OMGHL+ebwshaFVV3doCJMr6MWc9v491/3eHYf3wc//Oxb9qvWbr+Q1twnpbz91Zl9PoXamqlGXZuG2/35+8nivL8vAOA8DFrB9z1vMTEZHqPZHqm6f/7v/9LxH5hIj84PD67T8R+dR/Pv3/LH5OZPHvHoWzXrP1/Ibmqt4uU157nBI/vhYgZ+9Ymn7OryUAaMf6MWc9P/3gv5x+mr7054P/6rZm6/kNbaJ6bZ8Sf3Bpc7zvBIAV1o850/ntv6O6+W/thvXmC4ffe4Lpmh3kN7QJ6vUxsFVVi6K46J1MURR9/ygAav+YM53fRx+p/tufqb63VP3H2ccM6tlh+7999eIvoZmu2UF+Qxu5Xh8DO7V3bsDUrB9z1vN7qXxP9b0fbR7Y7/3oYfuFrNdsPb+h8Qm7QWrXRoCpWT/mrOd3onr/6VPh1f+5KIz1mq3nNzQv17AzVZWOWv9iWZayWq3kxYsXH/utuyaz2UyePXsm7777riwWi7Z/LJAs68ec9fwe+fCPRXb/Q0Q+klffEp+JyF5EbkQ+80cin/79J0NYr9l6fkObsN6s7S+MemvSm5sbWS6Xjdtms9nJ67nlcilZ1ro+IGnWjznr+T3yf/+nHIa1iHzyP4p87m9FPvkffrjxox9uf5r1mq3nNzRP9Y46sOfzubz99tvy5ptvnjRgNpvJ7e2tFEUht7e3j7a9+eab8vbbb8t8Ph8zXcA968ec9fxOfP+FSPWOiHxC5DN/LHL7dZHlvxe5/d8in/ny4d9Xfyfy/Q+eDGO9Zuv5Dc1VvV3Oo2vPL52ldo9aYGrWjznr+amqav2B6ov/pPq9v2ne/r1vHLbXH1wUznrN1vMbGvcSf8Ld3Z2GEDTP80cX7jebjeZ5riEE9zsBYIX1Y856fjFYr9l6fkMbuV7bXzo7V9e1qGrjBfuqqiTLMnenVwDLrB9z1vOLwXrN1vMb2oj1tr74PenABgAgUba/JQ4AALphYAMA4AADGwAABxjYAAA4wMAGAMABBjYAAA4wsAEAcICBDQCAAwxsAAAcYGADAODApAO7rmupqqpxW1mWUtc18UaMF4P1mj30cEjW67WeXwzs07ZY7t9kA3u328l6vZYQgmy325Nt2+1WVquVrNdr2e12xBshXgzWa/bQwyFZr9d6fjGwT9tivn9dHvGlxp6HTTx7z6m1XrOHHg7Jer3W84uBfdoWnofd4Lgpcnji18vmFEXxsinH255qDvH6xYvBes0eejgk6/Vazy8G9mlbJuqf7YFdVZWGEE4KP27A8ev5thCCVlVFvAHjxWC9Zg89HJL1eq3nFwP7tC0T9q/13B31GraqSlmWjdv2+/3J67myLA/vMIg3WLwYrNfsoYdDsl6v9fxiYJ+2xVX/ukx57XFK/PhagJy9Y2n6Ob+WQLxh48VgvWYPPRyS9Xqt5xcD+7QtE/XP9inxB5c259KmEM/eQWm9Zg89HJL1eq3nFwP7tC0T9M/HwFZVLYrioncyRVEQb4R4MViv2UMPh2S9Xuv5xcA+bcvI/fMxsK2/s0wtXgzWa/bQwyFZr9d6fjGwT9vCJ+wG1q/dpBYvBus1e+jhkKzXaz2/GNinbeEadoP7+3vN8/ziphw3J89zLcuSeAPGi8F6zR56OCTr9VrPLwb2aVsm7F/ruTvqf9Z1c3Mjy+WycdtsNjt5PbdcLiXLMuINGC8G6zV76OGQrNdrPb8Y2KdtcdW/LlNee5wSt36Hn9TixWC9Zg89HJL1eq3nFwP7tC3c6ewJ1u+hm1q8GKzX7KGHQ7Jer/X8YmCftoV7iT/h7u5OQwia5/mjC/ebzUbzPNcQwsVNIV6/eDFYr9lDD4dkvV7r+cXAPm3LyP1rPXczVe18Nr3rLz6o61pUVRaLxaNtVVVJlmUyn8+JN1K8GKzX7KGHQ7Jer/X8YmCftmXE/rW++D3pwAYAIFGtB/ao3xIHAADdMLABAHCAgQ0AgAMMbAAAHGBgAwDgAAMbAAAHGNgAADjAwAYAwAEGNgAADkw6sOu6lqqqGreVZSl1XRNvxHgxWM/Ren6wJcb+kto+aL1ey/lNNrB3u52s12sJIch2uz3Ztt1uZbVayXq9lt1uR7wR4sVgPUfr+cGWGPtLavug9Xqt58fjNYkXhfUcrecHW2LsL6ntg9br5fGaDaw/uD21eDFYz9F6frAlxv6S2j5ovd6J8rM9sKuq0hDCSeHHDTh+Pd8WQtCqqog3YLwYrOdoPT/YEmN/SW0ftF7vhPm1nrujXsNWVSnLsnHbfr8/eT1XluXhHQbxBosXg/UcrecHW2LsL6ntg9brtZ7fiS5TXnucEj++FiBn71iafs6vJRBv2HgxWM/Ren6wJcb+kto+aL3eifKzfUr8waXNubQpxLOx03vK0Xp+sCXG/pLaPmi93gny8zGwVVWLorjonUxRFMQbIV4M1nO0nh9sibG/pLYPWq935Px8DGzrnzhTixeD9Ryt5wdb+ITdn/V6+YTdwPo13dTixWA9R+v5wRauYfdnvV6uYTe4v7/XPM8vbspxc/I817IsiTdgvBis52g9P9gSY39JbR+0Xu+E+bWeu6P+Z103NzeyXC4bt81ms5PXc8vlUrIsI96A8WKwnqP1/GBLjP0ltX3Qer3W8zvRZcprj1Pi1u/8lVq8GKznaD0/2MKdzvqzXi93OnuC9XtrpxYvBus5Ws8PtnAv8f6s18u9xJ9wd3enIQTN8/zRhfvNZqN5nmsI4eKmEK9fvBis52g9P9gSY39JbR+0Xu/I+bWeu5mqdj6b3vUXH9R1Laoqi8Xi0baqqiTLMpnP58QbKV4M1nO0nh9sibG/pLYPWq93xPxaX/yedGADAJCo1gN71G+JAwCAbhjYAAA4wMAGAMABBjYAAA4wsAEAcICBDQCAAwxsAAAcYGADAOAAAxsAAAcY2AAAODDpwK7rWqqqatxWlqXUdT1yRsB1G/qYS+0YjlEvPXzFQr2W85tsYO92O1mv1xJCkO12e7Jtu93KarWS9Xotu91uogyB6zL0MZfaMRyjXnr4ioV6red3Fc/DBvC0FJ/JPiSeh92f9Xp5HnaD46bI4YlfL5tTFMXLphxvu4adFZjK0MdcasdwjHrpoa16J8rP9sCuqkpDCCeFHzfg+PV8WwhBq6rq1hYgUUMfc6kdwzHqpYe26p0wv9Zzd9Rr2KoqZVk2btvv9yev58qyPLzDAHCxoY+51I7hGPXSw1cs1Gs9v2OjDuzFYiHPnz+X29tbmc1mF/3ObDaT29tbef78uSwWi8gZAtdl6GMutWM4Rr308PXGrNd6fie6fCzXnl86O76AL2enGeTslMPxhX8A3Qx9zKV2DMeolx7aqneC/Gxfwz5WFMWTTXn4KYqi7x8FQIc/5lI7hmPUSw9t1Ttyfj4GtvV3WsC14RN2P3zC7s96vXzCbnBpU6ZePOBaDH3MpXYMx6iXHtqqd6L8Ws/dTLt/w631L5ZlKavVSl68ePGx37prMpvN5NmzZ/Luu++6+8IFMKWhj7nUjuEY9dLDy4xV74T5ZW1/YdRvid/c3MhyuWzc9vDtvI/7lt5yuZQsa10fkLShj7nUjuEY9dLDVyzUaz2/E10+lmuPU+LW73gDXBvudNYPdzrrz3q93OnsCdbvKQtcG+4l3g/3Eu/Per3cS/wJd3d3GkLQPM8fXbjfbDaa57mGENzvpIAVQx9zqR3DMeqlh69YqHfk/Gx/6excXdeiqo0X7KuqkizLZD6f9/1jAPzQ0MdcasdwjHrp4SsW6h0xv9YXvycd2AAAJMr2t8QBAEA3DGwAABxgYAMA4AADGwAABxjYAAA4wMAGAMABBjYAAA4wsAEAcICBDQCAA5MO7Lqupaqqxm1lWUpd1yNndMp6fh5Y72Fq+VmvN0XW1zi1fcZyvZMN7N1uJ+v1WkIIst1uT7Ztt1tZrVayXq9lt9uRn1PWe5haftbrTZH1NU5tnzFfb5cnhuiVP17Ten4eWO9havlZrzdF1tc4tX2Gx2s24EHm1896D1PLz3q9KbK+xqntMxPVa3tgV1WlIYSTwo8bcPx6vi2EoFVVdWvLleTngfUeppaf9XpTZH2NU9tnJqy39dwd9Rq2qkpZlo3b9vv9yeu5siwP7zAisp6fB9Z7mFp+1utNkfU1Tm2fcVVvlymvPU6JH18LkLN3LE0/59cSYrOenwfWe5haftbrTZH1NU5tn5moXtunxB9c2pypdgLr+XlgvYep5We93hRZX+PU9pkJ6vUxsFVVi6K46J1MURR9/6irzM8D6z1MLT/r9abI+hqnts+MXK+PgW39nZv1/Dyw3sPU8rNeb4qsr3Fq+wyfsBtYvzZiPT8PrPcwtfys15si62uc2j7DNewG9/f3muf5xU05bk6e51qWZbe2XEl+HljvYWr5Wa83RdbXOLV9ZsJ6W8/dUf+zrpubG1kul43bZrPZyeu55XIpWZZFy03Efn4eWO9havlZrzdF1tc4tX3GVb1dprz2OCVu/Q461vPzwHoPU8vPer0psr7Gqe0z3OnsCdbvUWs9Pw+s9zC1/KzXmyLra5zaPsO9xJ9wd3enIQTN8/zRhfvNZqN5nmsIYbKdwHp+HljvYWr5Wa83RdbXOLV9ZuR6W8/dTFU7n03v+osP6roWVZXFYvFoW1VVkmWZzOfzvn9MZ9bz88B6D1PLz3q9KbK+xqntMyPW2/ri96QDGwCARLUe2KN+SxwAAHTDwAYAwAEGNgAADjCwAQBwgIENAIADDGwAABxgYAMA4AADGwAABxjYAAA4MOnArutaqqpq3FaWpdR1PXJGp6znl6Kh1yS1NbbeP+vxYrBes/UeplTvZAN7t9vJer2WEIJst9uTbdvtVlarlazXa9ntduQHERl+TVJbY+v9sx4vBus1W+9havXyeE2H+aWIRwf2Y71/1uPFYL1m6z28gnrtP17T+oPRreeXoqHXJLU1tt4/6/FisF6z9R5eSb22B3ZVVRpCOCn8uAHHr+fbQghaVVW3tlxJfikaek1SW2Pr/bMejzWx18Mrqrf13B31GraqSlmWjdv2+/3J67myLA/vMCKynl+Khl6T1NbYev+sx4vBes3We5havSe6THntcUr8+FqAnL1jafo5v5YQm/X8UjT0mqS2xtb7Zz1eDNZrtt7DK6nX9inxB5c2Z6q/KK3nl6Kh1yS1NbbeP+vxYrBes/UeXkG9Pga2qmpRFBe9kymKou8fdZX5pWjoNUltja33z3q8GKzXbL2Hzuv1MbBTe+eG/q7g3fSkrPfPerwYrNdsvYdXUK/9gZ3atRH0dyXXqyZjvX/W48VgvWbrPbySem0P7Pv7e83z/OKmHDcnz3Mty7JbW64kvxQNvSaprbH1/lmPx5rY6+EV1dt67o76n3Xd3NzIcrls3DabzU5ezy2XS8myLFpuIvbzS9HQa5LaGlvvn/V4MViv2XoPU6v3RJcprz1Oiad2Bx30dyV3NZqM9f5ZjxeD9Zqt9/BK6rV9SvxBaveoRX9XcN/gSVnvn/V4MViv2XoPr6BeHwNb9dCcEILmef7owv1ms9E8zzWEMNlflNbzS9HQa5LaGlvvn/V4MViv2XoPndfbeu5mqtr5bHrXX3xQ17WoqiwWi0fbqqqSLMtkPp/3/WM6s55fioZek9TW2Hr/rMeLwXrN1nvouN7WF78nHdgAACSq9cAe9VviAACgGwY2AAAOMLABAHCAgQ0AgAMMbAAAHGBgAwDgAAMbAAAHGNgAADjAwAYAwAEGNgAADjCwEVVd11JVVeO2siylruuRM8KQhl7f1OJ5yJF4/eINiYGNaHa7nazXawkhyHa7Pdm23W5ltVrJer2W3W43UYboY+j1TS2ehxyJ1y/e4Lo84ktf93jNL37x8OTO859f/VXV7Vb1J35C9U//9PR3vvEN1dlM9a/+6vDPX/2q6o//+OF///IvN8d7+PnsZy97mBlGY/1ZuujH+rOIrcfzkCPxUnke9he/qPprv6b6rW+d/nz724ftf/EXqp/8pOo//dPhn7/3PdXPf171d37nVYzjgf3hh69iFMUh7a9//dW/4y97U453fDk81e3lAVAUxcsd/3gbQ9uPodc3tXgeciTeKH9nGRrYv/7rT6f6G7+h+ku/pPqDH6j+3u+pvvGG6ne/+2r78cA+9s//fEj7nXeejo9JVFWlIYSTnft4Jz9+Pd8WQtCqqqYuAU8Yen1Ti+chR+KN9ndW67k7k6l85SsiP/uzIr/1WyJf+5rIX/+1yKc+NVk6GIaqSlmWjdv2+/3J67myLA/vImHW0OubWjwPORKvX7youkx5veQT9ic+ofpjP3b684d/ePr/+8pXDp+Wf/d3H8fgE7Zbx9d75OxdadPP+fUi2Db0+qYWz0OOxBvl7yxDp8R/5VdU33//9OfDD1/9f/Z71V/8xcO17PVa9fvfP43BwHbt0gOAYe3T0OubWjwPORIv+t9Zhgb2665hf/nLqj/1U6r/8A+qP/3Tqn/wB6fbGdjuFUVx0bvVoiimThUdDL2+qcXzkCPxov6d5WRg//3fqy4Wql/72uGf//IvVX/kR1S/+c1X/x8Gtmt8wr5u1j/dWI/nIUfiRf87y9DAbvrPuna7w6nvX/gF1S984fR3fvM3T0+NM7Dd4hr2dbN+/dB6PA85Em+Uv7MMDWyRxz+f//zh1PfP/Izqv/7r6e98+OHh3z+cGmdgu3R/f695nl+84x8fAHmea1mWU5eAJwy9vqnF85Aj8Ub7O6v13I1za9I///OmcS3y3nsiX/qSyLe+JfLpT5/+zk/+5OHff+lLh3/+7d8W+c53Hsf+3OcOsX7+56Okjn5ubm5kuVw2bpvNZiev55bLpWRZFi039Df0+qYWz0OOxOsXL6ouU15f9wkbSeNOZ9fN+l2mrMfzkCPxUrrTGZLHvcSvm/X7OFuP5yFH4qVyL3FADwdACEHzPH/05YzNZqN5nmsIgWHt1NDrm1o8DzkSr1+812g9dzNV7Xw2vesvIh11XYuqymKxeLStqirJskzm8/kEmWEIQ69vavE85Ei8fvGe0PriNwMbAIDxtR7Ycb4lDgAABsXABgDAAQY2AAAOMLABAHCAgQ0AgAMMbAAAHGBgAwDgAAMbAAAHGNgAADgw6cCu61qqqmrcVpal1HU9cka+0L/+hu6h9TVJrV6gLcv79GQDe7fbyXq9lhCCbLfbk23b7VZWq5Ws12vZ7XYTZWgb/etv6B5aX5PU6gXaMr9Pd3liiPZ8WhePXuyH/vV3BY/mayW1eoG2eLxmg4keFH416F9/Q/fQ+pqkVi/Q1kT7tO2BXVWVhhBOCj9uwPHr+bYQglZV1a0tV4L+9Td0D62vSWr1Am1NuE+3nrujXsNWVSnLsnHbfr8/eT1XluXhHUbC6F9/Q/fQ+pqkVi/Qlqd9etSBvVgs5Pnz53J7eyuz2eyi35nNZnJ7eyvPnz9vfKB4Suhff0P30PqapFYv0JarfbrLx3Lt+aWz4wv4cnaaQc5OORxf+McB/etv6B5aX5PU6gXammCftn0N+1hRFE825eGnKIq+f9RVon/9Dd1D62uSWr1AWyPv0z4GNu/O+6F//aX2iTO1eoG2+ITd4NKmcMA3o3/9Dd1D62uSWr1AWxPt063nbqbdv+HW+hfLspTVaiUvXrz42G/dNZnNZvLs2TN59913k/7SCv3rb+geWl+T1OoF2ppwn87a/sKo3xK/ubmR5XLZuO3h23kf9y295XIpWda6vqtC//obuofW1yS1eoG2XO3TXT6Wa49T4twlqR/6119qd/5KrV6gLe509gTuQ9wP/esvtXtrp1Yv0Bb3En/C3d2dhhA0z/NHF+43m43mea4hBA70j0H/+hu6h9bXJLV6gbZG3qdtf+nsXF3XoqqNF+yrqpIsy2Q+n/f9Y64W/etv6B5aX5PU6gXaGnGfbn3xe9KBDQBAomx/SxwAAHTDwAYAwAEGNgAADjCwAQBwgIENAIADDGwAABxgYAMA4AADGwAABxjYAAA4MOnArutaqqpq3FaWpdR1TTzH8TzkSDziTRnPQ47E6xdvUF1uQK4GH/5BPFvxPORIPOJxjBAvZrzX8PG0LuuP+iNe/8fKWc+ReMTjGCFezHgXsD+wh35QOPFsxfOQI/GIxzFCvNhrfAHbA7uqKg0hnBR+3IDj1/NtIQStqop4huN5yJF4xOMYIV7sNb5Q67k76pfOVFXKsmzctt/vT17PlWV5eIdBPLPxPORIPOJxjBAvZryoukx57XFK/PhagJy9Y2n6eTgtcf4FAOLZjOchR+IRj2OEeLHX+AK2T4k/uLQ5lzaFeLbieciReMTjGCFezHgX8DGwVVWLoniyKQ8/RVEQz2E8DzkSj3gcI8SLGe81fAxs6++MiNcvnocciUc8jhHixYx3AfsD2/q1B+L1i+chR+IRj2OEeLHX+AK2B/b9/b3meX5xU46bk+e5lmVJPMPxPORIPOJxjBAv9hpfqPXcHfU/67q5uZHlctm4bTabnbyeWy6XkmUZ8QzH85Aj8YjHMUK8mPGi6jLltccpcet3qCFev3geciQe8ThGiBd7jS9g+5T4A+v3gCUe90kmHvFixvOQI/G4l/hLd3e2n7JCvH7xPORIPOJxjBAvZrzXaD13M1W9/Pz5qc6/+KCua1FVWSwWj7ZVVSWPPQjjAAAAkklEQVRZlsl8Piee03geciQe8ThGiBcz3hNaX/yedGADAJCo1gN71G+JAwCAbhjYAAA4wMAGAMABBjYAAA4wsAEAcKD5fmuXGfF+bAAApI1P2AAAOMDABgDAAQY2AAAOMLABAHCAgQ0AgAMMbAAAHGBgAwDgAAMbAAAHGNgAADjAwAYAwAEGNgAADjCwAQBw4P8Dj3GE7EufGaoAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 600x400 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#gods view\n",
    "maze_viz(matrix,start,end)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length of the path: 21\n",
      "number of vertices A* has travelled: 45\n"
     ]
    }
   ],
   "source": [
    "#a* iterates through the least vertices\n",
    "#it slightly faster than dijkstra for that reason\n",
    "len_of_path_astar,path_astar=a_star(maze,start,end)\n",
    "num_of_v_astar=len([maze.route()[i] for i in maze.route() if maze.route()[i]==1])\n",
    "maze.clear(whole=True)\n",
    "\n",
    "print(f'length of the path:',len_of_path_astar)\n",
    "print(f'number of vertices A* has travelled:',num_of_v_astar)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "480 µs ± 2.64 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "_,_=graph.a_star(maze,start,end)\n",
    "maze.clear(whole=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length of the path: 21\n",
      "number of vertices Dijkstra has travelled: 86\n"
     ]
    }
   ],
   "source": [
    "len_of_path_dijkstra,path_dijkstra=graph.dijkstra(maze,start,end)\n",
    "num_of_v_dijkstra=len([maze.route()[i] for i in maze.route() if maze.route()[i]==1])\n",
    "maze.clear(whole=True)\n",
    "\n",
    "print(f'length of the path:',len_of_path_dijkstra)\n",
    "print(f'number of vertices Dijkstra has travelled:',num_of_v_dijkstra)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "551 µs ± 3.44 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "_,_=graph.dijkstra(maze,start,end)\n",
    "maze.clear(whole=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length of the path: 21\n",
      "number of vertices BFS has travelled: 86\n"
     ]
    }
   ],
   "source": [
    "#bfs is guaranteed to find the optimal path\n",
    "#it is funny that bfs is faster than both a* and dijkstra\n",
    "len_of_path_bfs,path_bfs=bfs_path(maze,start,end)\n",
    "num_of_v_bfs=len([maze.route()[i] for i in maze.route() if maze.route()[i]==1])\n",
    "maze.clear(whole=True)\n",
    "\n",
    "print(f'length of the path:',len_of_path_bfs)\n",
    "print(f'number of vertices BFS has travelled:',num_of_v_bfs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "216 µs ± 2.71 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "_,_=graph.bfs_path(maze,start,end)\n",
    "maze.clear(whole=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length of the path: 35\n",
      "number of vertices DFS has travelled: 66\n"
     ]
    }
   ],
   "source": [
    "#dfs may find the path, it may not be the optimal\n",
    "#it is funny that dfs is faster than both a* and dijkstra\n",
    "len_of_path_dfs,path_dfs=dfs_path(maze,start,end)\n",
    "num_of_v_dfs=len([maze.route()[i] for i in maze.route() if maze.route()[i]==1])\n",
    "maze.clear(whole=True)\n",
    "\n",
    "print(f'length of the path:',len_of_path_dfs)\n",
    "print(f'number of vertices DFS has travelled:',num_of_v_dfs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "213 µs ± 2.32 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "_,_=graph.dfs_path(maze,start,end)\n",
    "maze.clear(whole=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAewAAAFJCAYAAABZ+x49AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3U9sJHlW4PEXJmQHzbTczKirDpZrXCG6xx1GanIPdUBbgziBVlrBaAfVCg7dJwTiAJflsIfhAGIXaS6c4LQziAslbitOaBaVXBdvoqVoBEWpeyVKZSfjymTGXdRqKiJI59uDJ6sy05npjIz4Rbyf4/uRUjk94Xx+7/eLqJfxxxGBqgoAALBto+kEAADA1WjYAAB4gIYNAIAHaNgAAHiAhg0AgAdo2AAAeICGDQCAB2jYAAB4gIYNAIAHaNgAAHiAhg0AgAdo2AAAeICGDQCAB8ISn+UxXwAArCco+gH2sAEA8AANGwAAD9CwAQDwAA0bAAAP0LABAPBAow07z3PJsmzusjRNJc9z4nkcz4cciUe8JuP5kCPxysWrlKqu+yql3+9rkiQax7GenJxMLTs5OdE4jjVJEu33+8TzMJ4PORKPeGwjxHMZ7wqF+24jDbvf7+sHH3ygYRhqGIZ6+/bt14NzcnKit2/ffr3sgw8+uHJwiGcrng85Eo94bCPEcxlvBfYb9uSgyMXNV14PTrfbfT0ok8uWDQ7xbMXzIUfiEY9thHiu53gFtht2lmWaJMlU4ZMDMPk+uyxJEs2yjHiG4/mQI/GIxzZCPNdzvKLCfbfWi85UVdI0nbtsOBxOvc9K0/TiGwbxzMbzIUfiEY9thHgu4zm1TpfXEofEJ88FyMw3lnmv8WGJ2QsAiGczng85Eo94bCPEcz3HK7B9SHxs1cFZdVCIZyueDzkSj3hsI8RzGW8FfjRsVdVut7t0UMavbrdLPA/j+ZAj8YjHNkI8l/Gu4EfDtv7NiHjl4vmQI/GIxzZCPJfxVmC/YVs/90C8cvF8yJF4xGMbIZ7rOV6B7Yb96tUrjeN45UGZHJw4jjVNU+IZjudDjsQjHtsI8VzP8YoK991a/6xrY2NDoiiauywMw6n3WVEUSRAExDMcz4cciUc8thHiuYzn1DpdXkscErd+hxrilYvnQ47EIx7bCPFcz/EKbB8SH7N+D1jicZ9k4hHPZTwfciQe9xJ/rd+3/ZQV4pWL50OOxCMe2wjxXMa7QuG+G6jq6sfPp639wbE8z0VVZWtr69KyLMskCALZ3NwknqfxfMiReMRjGyGey3hLFD753WjDBgCgpQo37FqvEgcAAOuhYQMA4AEaNgAAHqBhAwDgARo2AAAeoGEDAOABGjYAAB6gYQMA4AEaNgAAHmi0Yed5LlmWzV2WpqnkeU68GuO54EOOVbJeL/mhadbn2HJ+jTXswWAgnU5HkiSRXq83tazX68nBwYF0Oh0ZDAbEqyGeCz7kWCXr9ZIfmmZ9jq3nx+M1ieeEDzlWyXq95IemWZ9jHq85h/UHj7ctngs+5Fgl6/WSH5pmfY4bys92w86yTJMkmSp8cgAm32eXJUmiWZYRr8J4LviQY5Ws10t+aJr1OW4wv8J9t9Zz2KoqaZrOXTYcDqfeZ6VpevENg3iVxXPBhxyrZL1e8kPTrM+x9fymrNPltcQh8clzATLzjWXea/ZcAvGqjeeCDzlWyXq95IemWZ/jhvKzfUh8bNXBWXVQiGdjpfctxypZr5f80DTrc9xAfn40bFXVbre70jeZbrdLvBriueBDjlWyXi/5oWnW57jm/Pxo2Nb3ONsWzwUfcqyS9XrJD02zPsfsYc9h/Zxu2+K54EOOVbJeL/mhadbnmHPYc7x69UrjOF55UCYHJ45jTdOUeBXGc8GHHKtkvV7yQ9Osz3GD+RXuu7X+WdfGxoZEUTR3WRiGU++zoiiSIAiIV2E8F3zIsUrW6yU/NM36HFvPb8o6XV5LHBK3fuevtsVzwYccq2S9XvJD06zPMXc6W8L6vbXbFs8FH3KskvV6yQ9Nsz7H3Et8iX6/r0mSaBzHl07cn5ycaBzHmiTJyoNCvHLxXPAhxypZr5f80DTrc1xzfoX7bqCqax9NX/eDY3mei6rK1tbWpWVZlkkQBLK5uUm8muK54EOOVbJeL/mhadbnuMb8Cp/8brRhAwDQUoUbdq1XiQMAgPXQsAEA8AANGwAAD9CwAQDwAA0bAAAP0LABAPAADRsAAA/QsAEA8AANGwAADzTasPM8lyzL5i5L01TyPK85I+B6s77NWc/vkvOXpUNYr9l6flWzXG9jDXswGEin05EkSaTX600t6/V6cnBwIJ1ORwaDQUMZAteL9W3Oen6XpI9EPvvSxfuarNdsPb+qma93nSeGqLHHawJYzvo2Zz2/uZ7/F9V/FNXnv73Wx63XbD2/qvF4zTmsP8gcuG6sb3PW85trNFL97NZFw/7syxf/XYD1mq3nV7WG6rXdsLMs0yRJpgqfHIDJ99llSZJolmXrDQvQUta3Oev5LfTqby6a9fj16tHKH7Ves/X8qtZgvYX7brjOYfR1qaqkaTp32XA4nHqflabpxTcMACuzvs1Zz09ERLInItkn0//f//ufIvIjInJ+8f79b4p84T9O/8zWhyJb+5fCWa/Zen5V86redbq8ljgkPnkuQGa+scx7zZ5LAFCM9W3Oen56/J+m96ZXfR1/3duaredXtYbqtX1IfGzVwfF9JQCssL7Nmc5v+Lnqyb1izfrkP198bgnTNXuQX9UaqNePhq2q2u12V/om0+12y/4qAGp/mzOd32ikevY/VJ9Eqv8YLmjU4cXys2+tfBGa6Zo9yK9qNdfrR8Nu2zc3oGnWtznr+b2WPlF98qPzG/aTH71YviLrNVvPr2rsYc/RtnMjQNOsb3PW85uSfbb8UHj2f1cKY71m6/lVzZdz2IGqypoKfzBNUzk4OJBnz54tvOpunjAM5datW/L48WPZ2toq+muB1rK+zVnP75Lv/YHI4L+KyEjeXCUeishQRDZE3v1vIl/67aUhrNdsPb+qNVhvUPQDtd6adGNjQ6IomrssDMOp91lRFEkQFK4PaDXr25z1/C751/ty0axF5K2viuz9H5G3/v0PF45+uHw56zVbz69qPtVba8Pe3NyUBw8eyHvvvTc1AGEYyu7urnS7Xdnd3b207L333pMHDx7I5uZmnekC3rO+zVnPb8q/PRPJHonIj4i8+wciu98Rif6dyO7/Enn3v1/8/9nfiPzb8dIw1mu2nl/VvKp3nePoWvKis7bdoxZomvVtznp+qqqaH6s++w+qP/jf85f/4OhieX68UjjrNVvPr2rcS3yJfr+vSZJoHMeXTtyfnJxoHMeaJIn3KwFghfVtznp+Lliv2Xp+Vau5XtsXnc3K81xUde4J+yzLJAgC7w6vAJZZ3+as5+eC9Zqt51e1GustfPK70YYNAEBL2b5KHAAArIeGDQCAB2jYAAB4gIYNAIAHaNgAAHiAhg0AgAdo2AAAeICGDQCAB2jYAAB4gIYNAIAHGm3YeZ5LlmVzl6VpKnmeE6/GeC5Yr9mHMayS9Xqt5+cC67QtlsevsYY9GAyk0+lIkiTS6/WmlvV6PTk4OJBOpyODwYB4NcRzwXrNPoxhlazXaz0/F1inbTE/fus84kuNPQ+bePaeU2u9Zh/GsErW67Wenwus07bwPOw5JgdFLp749Xpwut3u60GZXLZscIhXLp4L1mv2YQyrZL1eV/mdn59rv9/X09PTha9+v6/n5+eV1DEajfTs7GyleKzTtjQ0frYbdpZlmiTJVOGTAzD5PrssSRLNsox4FcZzwXrNPoxhlazX6zK/s7MzffDgwZWvs7OzUjWMRiM9PT3Vo6MjffDgwZX/iLNO29Lg+BXuu6HUSFUlTdO5y4bD4dT7rDRNL75hEK+yeC5Yr9mHMayS9Xpd5re9vS1RFC2MLyISRZFsb28XyPgNVZV+vy9Pnz6d+h2j0ejKz7FO2+HT+NV60dnW1pYcHh7K7u6uhOFq3xXCMJTd3V05PDyUra0t4lUYzwXrNfswhlWyXq/L/IIgkL29vaWx9vb2JAiCIimLqsrz58+l2+3KkydPln4hmId12havxm+d3XItedHZ5Al8mTnMIDOHHCZP/BPPTTwXrNfswxhWyXq9rvIbjUavD1XPvo6OjnQ0Gq2c4+yh70Wv09PTRmq2PsfWNTB+ts9hT+p2u0sHZfzqdrvEqyGeC9Zr9mEMq2S9Xlf5nZ6elmqsYy9evFjpnHiRuKzTttQ8fn40bOvfLNsWzwXrNfswhlWyXq/L/ObtZRfdux7HYQ/7+mIPe45VB2XVwSFeuXguWK/ZhzGskvV668hvdi+76N71pKsa9yqxWadtaWj8bDfsV69eaRzHKw/K5ODEcaxpmhKvwnguWK/ZhzGskvV668pvci97nb3rRTHnNe6rGjbrtC0Njl/hvlvrVeIbGxsSRdHcZeOr8xZdpRdF0aWrOYlXLp4L1mv2YQyrZL3euvKbvGJ8nSvDF8W8efOm3LlzR/b391/XsbGx/J9V1mlbvBq/dbq8ljgkbv0OP22L54L1mn0YwypZr7eu/Eajkb548aKSvetF8bnTmZ+409kS1u+h27Z4Lliv2YcxrJL1eq3n5wLrtC3cS3yJfr+vSZJoHMeXTtyfnJxoHMeaJMnKg0K8cvFcsF6zD2NYJev1Ws/PBdZpW2oev8J9N1DVtY+mr/vBsTzPRVXn3ikmyzIJgkA2NzeJV1M8F6zX7MMYVsl6vdbzc4F12pYax6/wye9GGzYAAC1VuGHXepU4AABYDw0bAAAP0LABAPAADRsAAA/QsAEA8AANGwAAD9CwAQDwAA0bAAAP0LABAPBAow07z3PJsmzusjRNJc9z4tUYzwXrOVrPD7a4WF/atg5ar9dyfo017MFgIJ1OR5IkkV6vN7Ws1+vJwcGBdDodGQwGxKshngvWc7SeH2xxsb60bR20Xq/1/Hi8JvGcsJ6j9fxgi4v1pW3roPV6ebzmHNYf3N62eC5Yz9F6fmPn5+fa7/f19PR04avf7+v5+Xklv280GunZ2RnxZrhYX3xZB6tivd6G8rP9eM08z6XT6cinn34qw+FwalkYhjIcDl+/zy57//335dGjR1OPNSNeuXguWM/Ren6TPv/8c/nkk0+u/LkPP/xQ3nnnnbV/j6pKv9+Xp0+fSpqmkiSJvPvuu8QTN+uLT+tgFazX22B+hZ/WFa7zW9alqpKm6dxl48GYHZSxNE1l9ssF8crFc8F6jtbzm7S9vS1RFC3MV0QkiiLZ3t5eK/5s4xobjUbEm/hM1euLT+tgFazXaz2/SbVedLa1tSWHh4eyu7srYbjad4UwDGV3d1cODw8vPVCceOXiuWA9R+v5TQqCQPb29pb+zN7engRBsS/qqirPnz+XbrcrT548WfqFoO3xXKwvPq2DVbBer/X8JtV+lfjOzo48fPhwpcEZD8rDhw9lZ2eHeA7iuWA9R+v5Tbpx44ZEUTR3WRRFcuPGjZVjWWqEPsVzsb74tA5WwXq91vMba+TPunZ2duT+/fsLDzOMDYdDuX///pWDQrxy8VywnqP1/MaW7WUX3bt++fJlJY2wjfFcrC++rINVsV6v9fxEGmrYvV5P7t27t9I3mXv37l36ezjiVRvPBes5Ws9v0ry97KJ71yIib7/9tuzv7y/cYy+qTfFcrC8+rYNVsF6v9fxEGmjYvV5P7t69K8fHxyt9kzk+Ppa7d+8uHBzilYvngvUcrec3a95e9jrnroMgkJs3b8qdO3cqaWRtiediffFtHSzLer3W8xur9c+60jSVg4MDefbs2ZWDMikMQ7l165Y8fvx46gQ/8crFc8F6jtbzW0RVpdvtSpqmEkWR3Llzp3DDnhdz3lXT+/v7cvPmTeKJm/XF13VwXdbrbTC/whtwrXvYGxsbC7/ljg9DLDocEUXRpX+giFcungvWc7Se3yKTe9nr7F0vijlvD3RjY71/Fq5jPBfri6/r4Lqs12s9vynr3G1FudPZtYnngvUcree3yGg00hcvXuhoNHIW/zrcmazqeNzprDzr9fpypzPuJU48J6znaD0/2MK9xMuzXi/3El+i3+9rkiQax/HrQRk7OTnROI41SZKVB4V45eK5YD1H6/nBFhfrS9vWQev11pyf7XuJz8rzXFR17gn7LMskCIJC92glXrl4LljP0Xp+sMXF+tK2ddB6vTXmV/jkd6MNGwCAlrJ9lTgAAFgPDRsAAA/QsAEA8AANGwAAD9CwAQDwAA0bAAAP0LABAPAADRsAAA/QsAEA8AANGwAADzTasPM8lyzL5i5L01TyPK85I+B6q3qba9s27KJexvANC/Vazq+xhj0YDKTT6UiSJNLr9aaW9Xo9OTg4kE6nI4PBoKEMgeul6m2ubduwi3oZwzcs1Gs9v2vxPGwAy7XxmexV4nnY5Vmvl+dhzzE5KHLxxK/Xg9Ptdl8PyuSy67CyWnd+fq79fl9PT08Xvvr9vp6fn1f2O0ejkZ6dnVUWk3jzVb3NtW0bdlEvY2ir3obys/087DzPpdPpyKeffirD4XBqWRiGMhwOX7/PLnv//ffl0aNH1+q5sJZ8/vnn8sknn1z5cx9++KG88847pX6Xqkq/35enT59KmqaSJIm8++67xHMQr+ptrm3bsIt6GcM3LNTbYH6FH68ZrvNb1qWqkqbp3GXjwZgdlLE0TaXElwtcYXt7W6IoWjg/IiJRFMn29vbav2O20YyNRiPiOYpX9TbXtm3YRb2M4RsW6rWe36RaLzrb2tqSw8ND2d3dlTBc7btCGIayu7srh4eHsrW15TjD9gqCQPb29pb+zN7engRB4S+Foqry/Plz6Xa78uTJk6VfCohXbbyqt7m2bcMu6mUMr1Znvdbzm1T7VeI7Ozvy8OHDlQZnPCgPHz6UnZ2dmjJsrxs3bkgURXOXRVEkN27cKBTPUuNqc7yqt7m2bcMu6mUMF2uiXuv5jTXyZ107Ozty//79hYcZxobDody/f9/bldQ3y/ay19m7fvnyZSWNi3jl41W9zbVtG3ZRL2M4X1P1Ws9PpKGG3ev15N69eyt9k7l3796lv4eDO/P2stfZuxYRefvtt2V/f3/hXjvx6otX9TbXtm3YRb2M4XxN1Ws9P5EGGnav15O7d+/K8fHxSt9kjo+P5e7du96vrL6Yt5e97rnrIAjk5s2bcufOnUoaD/HWi1f1Nte2bdhFvYzhYk3Uaz2/sVr/rCtNUzk4OJBnz55dOSiTwjCUW7duyePHj7274MJHqirdblfSNJUoiuTOnTtrNex5cedd5by/vy83b94knoN4VW9zbduGXdTLGK6mrnobzK/wP6q17mFvbGws3EsYH4ZYdDgiiqJKmgauNrmXve7e9aK48/YYNzbWWw2Jd3W8qre5tm3DLuplDN+wUK/1/Kasc7cV5U5n195oNNIXL17oaDRy+juuw53ErMfjTmflcKez8qzX68udzriXONAC3Eu8HO4lXp71ermX+BL9fl+TJNE4jl8PytjJyYnGcaxJkni/kgJWVL3NtW0bdlEvY/iGhXprzs/2vcRn5Xkuqjr3hH2WZRIEgVf3zAWsq3qba9s27KJexvANC/XWmF/hk9+NNmwAAFrK9lXiAABgPTRsAAA8QMMGAMADNGwAADxAwwYAwAM0bAAAPEDDBgDAAzRsAAA8QMMGAMADjTbsPM8ly7K5y9I0lTzPa85omvX8fGB9DNuWn/V628j6HLdtnbFcb2MNezAYSKfTkSRJpNfrTS3r9XpycHAgnU5HBoMB+XnK+hi2LT/r9baR9Tlu2zpjvt51nhii1/zxmtbz84H1MWxbftbrbSPrc9y2dYbHa87Bg8xtOj8/136/r6enpwtf/X5fz8/Pr4xlfQzblp/1etvI+hy3bZ1pqF7bDTvLMk2SZKrwyQGYfJ9dliSJZlm23rBck/xcOjs70wcPHlz5Ojs7WxrH+hi2LT/r9baR9Tlu2zrTYL2F+26t57BVVdI0nbtsOBxOvc9K0/TiG4ZD1vNzaXt7W6IoWvozURTJ9vb20p+xPoZty896vW1kfY7bts74VG+tDXtra0sODw9ld3dXwjBc6TNhGMru7q4cHh7OfaB4m/JzKQgC2dvbW/oze3t7EgTLH+FqfQzblp/1etvI+hy3bZ3xqt51dsu15EVnkyfwZeYwg8wccpg88V8X6/m5MhqN9OjoaO6h8KOjIx2NRivHsj6GbcvPer1tZH2O27bONFCv7XPYk7rd7tJBGb+63W7ZX3Ut83Pl9PR0bsM+PT0tHMv6GLYtP+v1tpH1OW7bOlNzvX40bOvf3Kzn59K8veyie9eq9sewbflZr7eNrM9x29YZ9rDnWHVQmloZrOdXh9m97KJ719bHsG35Wa+3jazPcdvWmYbqtd2wX716pXEcrzwok4MTx7GmabresFyT/OoyuZdddO/a+hi2LT/r9baR9Tlu2zrTYL2F+26tV4lvbGws/NOh8dV5i67Si6LoyiuUy7KeX10mrxhf5crwSdbHsG35Wa+3jazPcdvWGa/qXafLa4lD4tbvoGM9v7qMRiN98eJF4XPXqvbHsG35Wa+3jazPcdvWGe50toT1e9Raz88H1sewbflZr7eNrM9x29YZ7iW+RL/f1yRJNI7jSyfuT05ONI5jTZKksZXAen4+sD6GbcvPer1tZH2O27bO1Fxv4b4bqOraR9PX/eBYnueiqnPvFJNlmQRBIJubm2V/zdqs5+cD62PYtvys19tG1ue4betMjfUWPvndaMMGAKClCjfsWq8SBwAA66FhAwDgARo2AAAeoGEDAOABGjYAAB6gYQMA4AEaNgAAHqBhAwDgARo2AAAeaLRh53kuWZbNXZamqeR5XnNG06zn10ZVz0nb5tj6+FmP54L1mq2PYZvqbaxhDwYD6XQ6kiSJ9Hq9qWW9Xk8ODg6k0+nIYDAgP4hI9XPStjm2Pn7W47lgvWbrY9i2enm8pof5tRGPDizH+vhZj+eC9Zqtj+E1qNf+4zWtPxjden6unJ+fa7/f19PT04Wvfr+v5+fntedW9Zy0bY6tj5/1eC5Yr9n6GF6Tem037CzLNEmSqcInB2DyfXZZkiSaZdl6w3JN8nPp7OxMHzx4cOXr7Oys1ryqnpO2zbH18bMejzmxN4bXqN7CfbfWc9iqKmmazl02HA6n3melaXrxDcMh6/m5tL29LVEULf2ZKIpke3u7powuVD0nbZtj6+NnPZ4L1mu2PoZtq3fKOl1eSxwSnzwXIDPfWOa9Zs8luGY9P5dOT0+X7l2fnp42klfVc9K2ObY+ftbjuWC9ZutjeE3qtX1IfGzVwWnqH0rr+bkyGo306OhobrM+OjrS0WjUWG5Vz0nb5tj6+FmP54L1mq2P4TWo14+Grara7XZX+ibT7XbL/qprmZ8ri/aym9q7nlT1nLRtjq2Pn/V4Lliv2foYel6vHw27bd/cfDJvL7vpvWvVa/FtulHWx896PBes12x9DK9BvfYbdtvOjfhodi+76b3ra3K+qjHWx896PBes12x9DK9JvbYb9qtXrzSO45UHZXJw4jjWNE3XG5Zrkl9dJveym967rnpO2jbH1sfPejzmxN4YXqN6C/fdWv+sa2NjY+GfDoVhOPU+K4oiCYLAWW4i9vOrSxAEsre3JyIie3t7jdZV9Zy0bY6tj5/1eC5Yr9n6GLat3inrdHktcUi8bXfQ8dVoNNIXL140fu5a9drc1agx1sfPejwXrNdsfQyvSb22D4mPte0etSjvGtw3uFHWx896PBes12x9DK9BvX40bNWLwUmSROM4vnTi/uTkROM41iRJGvuH0np+bVT1nLRtjq2Pn/V4Lliv2foYel5v4b4bqOraR9PX/eBYnueiqrK1tXVpWZZlEgSBbG5ulv01a7OeXxtVPSdtm2Pr42c9ngvWa7Y+hh7XW/jkd6MNGwCAlircsGu9ShwAAKyHhg0AgAdo2AAAeICGDQCAB2jYAAB4gIYNAIAHaNgAAHiAhg0AgAdo2AAAeICGDQCAB2jYcCrPc8mybO6yNE0lz/OaM0KVqp7ftsXzIUfilYtXJRo2nBkMBtLpdCRJEun1elPLer2eHBwcSKfTkcFg0FCGKKPq+W1bPB9yJF65eJVb5xFfetXjNT/66OLJnbOvn/s51V5P9cd/XPUP/3D6M0dHqmGo+pd/efHf3/qW6vb2xf/+mZ+ZH2/8+vKXV3uYGWpj/Vm6KMf6s4itx/MhR+K15XnYH32k+vM/r/rd706/vv/9i+V/+qeqb72l+umnF//9gx+ofuUrqr/2a29iTDbs733vTYxu9yLt73znzf+3wsCNRiM9OzvT8/PzK392FcRbbHLFl4unur3eALrd7usVf3IZTdsfVc9v2+L5kCPxavk3y1DD/oVfWJ7q176m+tM/rXp+rvqbv6l6+7bqy5dvlk827En/9E8XaT96tDz+D41GIz09PdWjoyN98OBB6aZAvOXxsizTJEmmVu7JlXzyfXZZkiSaZVmpfOFW1fPbtng+5Ei82v7NKtx3Q2nKH/+xyE/+pMiv/IrIn/+5yF/9lcgXvlBZeFWVfr8vT58+lTRNX///o9GIeA7jqerUz08aDodT77PSNL34Fgmzqp7ftsXzIUfilYvnkruLzv7iLy4a8OTrd3/3zfIbNy7++8/+TORXf1Xkq1+t5Neqqjx//ly63a48efJk4UQQz028ra0tOTw8lN3dXQnD1b4PhmEou7u7cnh4KFtbW+ukjZpUPb9ti+dDjsQrF88ldw37Z39W5G//dvr1G7/xZvn5ucif/InIW2+JHB2JLPgGsyprjavN8XZ2duThw4crbQDjFf/hw4eys7Oz9u9Efaqe37bF8yFH4pWL54q7hv1jPybyEz8x/friF98s/+Y3RT77TOSv/1rkn/9Z5Pd/v9Sve/nyZSWNi3jVxNvZ2ZH79+8vPJQ0NhwO5f79+zRrz1Q9v22L50OOxCsXz4Vm/g77H/5B5Hd+R+SP/kgkSS7OZ//e74n83d+tHfLtt9+W/f19iaKokhSJV06v15N79+6t9G313r17l/7mEbZVPb9ti+dDjsQrF88Fdw07y0ROT6df//IvF4ew8tNIAAAHEElEQVS+P/pI5GtfE/n61y9+9hd/UeSXfknk44/XPjQeBIHcvHlT7ty5U0njId768Xq9nty9e1eOj49X+rZ6fHwsd+/epWl7our5bVs8H3IkXrl4rgQlrnBb/MGPP744Pz3rK18R+eVfvtiz/vu/F/nSl94s+/73RQ4ORH7910W+8Q2Rb39b5Ld+S+Tzz6djPH0qcvu2yKNHIj/1U4uTW3CV8/7+vty8eXO1ColXOF6apnJwcCDPnj27csWfFIah3Lp1Sx4/fsyFZ4ZVPb9ti+dDjsQrF6+AoOgH3PxZ17e/ffFa5BvfuPz/ffGLIt/97pv//vjji9esvT2RFb5kjPcYb9y4MdV4NjbWO6hAvNXibWxsLNw7D8NQhsPh6/dZURRJEBReh1Gjque3bfF8yJF45eI5tc4fb+tVN04x6DrdScx6PO50dr1Zv8uU9Xg+5Ei8Nt3pDK3HvcSvN+v3cbYez4ccideWe4kDerEBJEmicRy/XvHHTk5ONI5jTZKEZu2pque3bfF8yJF45eJdoXDfdXPRGfBDeZ6Lqs69KCPLMgmCQDY3NxvIDFWoen7bFs+HHIlXLt4ShU9+07ABAKhf4YbdzI1TAABAITRsAAA8QMMGAMADNGwAADxAwwYAwAM0bAAAPEDDBgDAAzRsAAA8QMMGAMADjTbsPM8ly7K5y9I0lTzPa87IL4xfeVWPofU5aVu9QFGW1+nGGvZgMJBOpyNJkkiv15ta1uv15ODgQDqdjgwGg4YytI3xK6/qMbQ+J22rFyjK/Dq9zhNDtOTTunj0YjmMX3nX4NF8hbStXqAoHq85R0MPCr82GL/yqh5D63PStnqBohpap2037CzLNEmSqcInB2DyfXZZkiSaZdl6w3JNMH7lVT2G1uekbfUCRTW4Thfuu7Wew1ZVSdN07rLhcDj1PitN04tvGC3G+JVX9Rhan5O21QsU5dM6XWvD3traksPDQ9nd3ZUwDFf6TBiGsru7K4eHh3MfKN4mjF95VY+h9TlpW71AUV6t0+vslmvJi84mT+DLzGEGmTnkMHniHxcYv/KqHkPrc9K2eoGiGlinbZ/DntTtdpcOyvjV7XbL/qprifErr+oxtD4nbasXKKrmddqPhs2383IYv/LatsfZtnqBotjDnmPVQWGDn4/xK6/qMbQ+J22rFyiqoXW6cN8NdP0r3Ap/ME1TOTg4kGfPni286m6eMAzl1q1b8vjx41ZftML4lVf1GFqfk7bVCxTV4DodFP1ArVeJb2xsSBRFc5eNr85bdJVeFEUSBIXru1YYv/KqHkPrc9K2eoGivFqn19kt1xKHxLlLUjmMX3ltu/NX2+oFiuJOZ0twH+JyGL/y2nZv7bbVCxTFvcSX6Pf7miSJxnF86cT9ycmJxnGsSZKwoS/A+JVX9Rhan5O21QsUVfM6bfuis1l5nouqzj1hn2WZBEEgm5ubZX/NtcX4lVf1GFqfk7bVCxRV4zpd+OR3ow0bAICWsn2VOAAAWA8NGwAAD9CwAQDwAA0bAAAP0LABAPAADRsAAA/QsAEA8AANGwAAD9CwAQDwQKMNO89zybJs7rI0TSXPc+J5HM+HHIlHvCbj+ZAj8crFq9Q6NyBXgw//IJ6teD7kSDzisY0Qz2W8K/jxtC7rj/ojXvnHylnPkXjEYxshnst4K7DfsKt+UDjxbMXzIUfiEY9thHiu53gFtht2lmWaJMlU4ZMDMPk+uyxJEs2yjHiG4/mQI/GIxzZCPNdzvKLCfbfWi85UVdI0nbtsOBxOvc9K0/TiGwbxzMbzIUfiEY9thHgu4zm1TpfXEofEJ88FyMw3lnmv8WGJ2QsAiGczng85Eo94bCPEcz3HK7B9SHxs1cFZdVCIZyueDzkSj3hsI8RzGW8FfjRsVdVut7t0UMavbrdLPA/j+ZAj8YjHNkI8l/Gu4EfDtv7NiHjl4vmQI/GIxzZCPJfxVmC/YVs/90C8cvF8yJF4xGMbIZ7rOV6B7Yb96tUrjeN45UGZHJw4jjVNU+IZjudDjsQjHtsI8VzP8YoK991a/6xrY2NDoiiauywMw6n3WVEUSRAExDMcz4cciUc8thHiuYzn1DpdXkscErd+hxrilYvnQ47EIx7bCPFcz/EKbB8SH7N+D1jicZ9k4hHPZTwfciQe9xJ/rd+3/ZQV4pWL50OOxCMe2wjxXMa7QuG+G6jq6sfPp639wbE8z0VVZWtr69KyLMskCALZ3NwknqfxfMiReMRjGyGey3hLFD753WjDBgCgpQo37FqvEgcAAOuhYQMA4AEaNgAAHqBhAwDgARo2AAAemH+/tdXUeD82AADajT1sAAA8QMMGAMADNGwAADxAwwYAwAM0bAAAPEDDBgDAAzRsAAA8QMMGAMADNGwAADxAwwYAwAM0bAAAPEDDBgDAA/8fnR3xvk+vn3sAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 600x400 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#mazerunner yay!\n",
    "maze_viz(matrix,start,end,path_astar)"
   ]
  },
  {
   "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
}