AlgoVisualizer.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ooooooooooooo######################s\n",
      "ooooooooooooo#######################\n",
      "ooooooooooooo#######################\n",
      "########################o###########\n",
      "########################o###########\n",
      "############o######o####oooooooooooo\n",
      "############o######o####oooooooooooo\n",
      "######o#####o######o####oooooooooooo\n",
      "######o#####o######o################\n",
      "######o#####o#####ooooooooooooo#####\n",
      "######o###########ooooooooooooo#####\n",
      "######o###########ooooooooooooo#####\n",
      "#####oooo#########ooooooooooooo#####\n",
      "######o#############################\n",
      "p###################################\n",
      "\n",
      "\n",
      "length graph : 36\n",
      "height graph : 15\n",
      "Total Nodes : 540\n"
     ]
    }
   ],
   "source": [
    "# from pprint import pprint\n",
    "from IPython.display import display, clear_output\n",
    "# arr holds letters or input s,p,# etc\n",
    "arr = []\n",
    "# visual_arr wil be used for display of animation\n",
    "visual_arr = []\n",
    "\n",
    "total_elements = 0\n",
    "height_graph = 0\n",
    "# Taking Input From File\n",
    "with open('input_file.txt','r') as f:\n",
    "        for line in f:\n",
    "            height_graph += 1\n",
    "            arr.append([])\n",
    "            visual_arr.append([])\n",
    "            for block in line :\n",
    "                if not block.isspace():\n",
    "                    arr[height_graph-1].append(block)\n",
    "                    if block == 'o':\n",
    "                        visual_arr[height_graph-1].append( \"<span style='color:black'>\" + block+ \"</span>\" )\n",
    "                    elif block == 's':\n",
    "                        visual_arr[height_graph-1].append( \"<span style='color:purple'>\" + block+ \"</span>\" )\n",
    "                    elif block == 'p':\n",
    "                        visual_arr[height_graph-1].append( \"<span style='color:pink'>\" + block+ \"</span>\" )\n",
    "                    elif block == '#':\n",
    "                        visual_arr[height_graph-1].append( \"<span style='color:orange'>\" + block+ \"</span>\" )\n",
    "                        \n",
    "                    total_elements+=1\n",
    "length_graph = int(total_elements / height_graph)\n",
    "        \n",
    "# with open('input_file.txt','w') as f:\n",
    "#     for x in range(0, 50):\n",
    "#         for y in range(0,50):\n",
    "#             f.write(str('*'))\n",
    "#         f.write(str('\\n'))\n",
    "\n",
    "        \n",
    "# Display the initial Grid\n",
    "for x in arr:\n",
    "    for y in x:\n",
    "        print(y,end='')\n",
    "    print()\n",
    "print()\n",
    "\n",
    "print()\n",
    "print('length graph : ' + str(length_graph))\n",
    "print('height graph : ' + str(height_graph))\n",
    "print( 'Total Nodes : '+ str(total_elements))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "starting point : [35, 0]\n",
      "ending point : [0, 14]\n"
     ]
    }
   ],
   "source": [
    "starting_point = []\n",
    "end_point = []\n",
    "# Find the Starting and Endpoint\n",
    "for x in arr:\n",
    "    for block in x:\n",
    "        if block == 's':\n",
    "            starting_point = [x.index(block), arr.index(x)]\n",
    "        if block == 'p':\n",
    "            end_point = [x.index(block),arr.index(x)]\n",
    "            \n",
    "if(starting_point == [] or end_point == []):\n",
    "    print('Given Input Does not contain starting or endpoint')\n",
    "print('starting point : ' + str(starting_point))\n",
    "print('ending point : ' + str(end_point))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "from IPython.display import display, clear_output, Markdown"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def find_neighbours(graph_arr,node):\n",
    "    neighbours = []\n",
    "    if(node[0]-1 >= 0):\n",
    "        if graph_arr[node[1]][node[0]-1]!= 'o':\n",
    "            nnode1 = [node[0]-1, node[1]]\n",
    "            neighbours.append(nnode1)\n",
    "    if(node[0]+1 < length_graph):\n",
    "        if graph_arr[node[1]][node[0]+1]!= 'o':\n",
    "            nnode2 = [node[0]+1, node[1]]\n",
    "            neighbours.append(nnode2)\n",
    "    if(node[1]-1 >= 0):\n",
    "        if graph_arr[node[1]-1][node[0]]!= 'o':\n",
    "            nnode3 = [node[0], node[1]-1]\n",
    "            neighbours.append(nnode3)\n",
    "    if(node[1]+1 < height_graph):\n",
    "        if graph_arr[node[1]+1][node[0]]!= 'o':\n",
    "            nnode4 = [node[0], node[1]+1]\n",
    "            neighbours.append(nnode4)\n",
    "    return neighbours\n",
    "\n",
    "def bfs(graph_arr,visual_arr , starting_point):\n",
    "    explored = []\n",
    "    end_point_found = None\n",
    "    queue = [starting_point]\n",
    "    total_nodes_visited = 0\n",
    "    while queue or end_point_found:\n",
    "        clear_output(wait=True) # Clear Output of each loop\n",
    "        node = queue.pop(0)\n",
    "        if graph_arr[node[1]][node[0]] == 'p':\n",
    "            return [node[0], node[1]]\n",
    "        if node not in explored and graph_arr[node[1]][node[0]] != 'e':\n",
    "            total_nodes_visited += 1\n",
    "            #print(node)\n",
    "            #print(graph_arr[node[1]][node[0]])\n",
    "            if graph_arr[node[1]][node[0]] != 's' and graph_arr[node[1]][node[0]] != 'p':\n",
    "                graph_arr[node[1]][node[0]] = 'e'\n",
    "#             display('\\n'.join(''.join(block for block in line) for line in arr))\n",
    "            \n",
    "            temp_color = visual_arr[node[1]][node[0]]\n",
    "            visual_arr[node[1]][node[0]] = \"<span style='color:red'>\" + graph_arr[node[1]][node[0]] + \"</span>\"\n",
    "            display(Markdown('<br>'.join(''.join(block for block in line) for line in visual_arr)))\n",
    "#             print('\\n'.join(''.join(block for block in line) for line in visual_arr))\n",
    "    \n",
    "            time.sleep(0.15)\n",
    "            visual_arr[node[1]][node[0]] = \"<span style='color:green'>\" + graph_arr[node[1]][node[0]] + \"</span>\"\n",
    "            explored.append(node)\n",
    "            neighbours = find_neighbours(graph_arr ,node)\n",
    "            \n",
    "            for neighbour in neighbours:\n",
    "                queue.append(neighbour)\n",
    "    print('Total Nodes Visited : ' + str(total_nodes_visited))\n",
    "    return None\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "<span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>s</span><br><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><br><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:green'>e</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:green'>e</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:pink'>p</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:red'>e</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span>"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-8-3f9e34df5902>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;32mimport\u001b[0m \u001b[0mcopy\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[0me\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mbfs\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mcopy\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mdeepcopy\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0marr\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mcopy\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mdeepcopy\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mvisual_arr\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstarting_point\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      3\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mx\u001b[0m \u001b[1;32min\u001b[0m \u001b[0marr\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m     \u001b[0mheight_graph\u001b[0m \u001b[1;33m+=\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m     \u001b[1;32mfor\u001b[0m \u001b[0my\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-5-bca5df664ebc>\u001b[0m in \u001b[0;36mbfs\u001b[1;34m(graph_arr, visual_arr, starting_point)\u001b[0m\n\u001b[0;32m     45\u001b[0m             \u001b[0mvisual_arr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mnode\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mnode\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;34m\"<span style='color:green'>\"\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mgraph_arr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mnode\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mnode\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;34m\"</span>\"\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     46\u001b[0m             \u001b[0mexplored\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnode\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 47\u001b[1;33m             \u001b[0mneighbours\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mfind_neighbours\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mgraph_arr\u001b[0m \u001b[1;33m,\u001b[0m\u001b[0mnode\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     48\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     49\u001b[0m             \u001b[1;32mfor\u001b[0m \u001b[0mneighbour\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mneighbours\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-5-bca5df664ebc>\u001b[0m in \u001b[0;36mfind_neighbours\u001b[1;34m(graph_arr, node)\u001b[0m\n\u001b[0;32m     14\u001b[0m             \u001b[0mneighbours\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnnode3\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     15\u001b[0m     \u001b[1;32mif\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnode\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m1\u001b[0m \u001b[1;33m<\u001b[0m \u001b[0mheight_graph\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 16\u001b[1;33m         \u001b[1;32mif\u001b[0m \u001b[0mgraph_arr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mnode\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mnode\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m!=\u001b[0m \u001b[1;34m'o'\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     17\u001b[0m             \u001b[0mnnode4\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m[\u001b[0m\u001b[0mnode\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mnode\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     18\u001b[0m             \u001b[0mneighbours\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnnode4\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mIndexError\u001b[0m: list index out of range"
     ]
    }
   ],
   "source": [
    "import copy\n",
    "e = bfs(copy.deepcopy(arr), copy.deepcopy(visual_arr), starting_point)\n",
    "for x in arr:\n",
    "    height_graph += 1\n",
    "    for y in x:\n",
    "        total_elements+=1\n",
    "if e:\n",
    "    print('End Point Found At : ' + str(e))\n",
    "else:\n",
    "    print('Given Graph has no end point')\n",
    "for x in arr:\n",
    "    for y in x:\n",
    "        print(y,end='')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A* Algo\n",
    "# Reference : https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_grid(arr):\n",
    "    for line in arr:\n",
    "        for block in line:\n",
    "            if block == math.inf:\n",
    "                print('*', end='')\n",
    "            else:\n",
    "                print(block, end='')\n",
    "        print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "111111111111100000000000000000000000\n",
      "111111111111100000000000000000000000\n",
      "111111111111100000000000000000000000\n",
      "000000000000000000000000100000000000\n",
      "000000000000000000000000100000000000\n",
      "000000000000100000010000111111111111\n",
      "000000000000100000010000111111111111\n",
      "000000100000100000010000111111111111\n",
      "000000100000100000010000000000000000\n",
      "000000100000100000111111111111100000\n",
      "000000100000000000111111111111100000\n",
      "000000100000000000111111111111100000\n",
      "000001111000000000111111111111100000\n",
      "000000100000000000000000000000000000\n",
      "000000000000000000000000000000000000\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "maze = []\n",
    "visit_count = []\n",
    "# Convert to a maze for easy handling\n",
    "for line in arr:\n",
    "    row = []\n",
    "    visit_row = []\n",
    "    for block in line:\n",
    "        if block == 'o':\n",
    "            row.append(1)\n",
    "            visit_row.append(math.inf)\n",
    "        elif block == 's' or block == 'p' or block == '#':\n",
    "            row.append(0)\n",
    "            visit_row.append(0)\n",
    "    maze.append(row)        \n",
    "    visit_count.append(visit_row)\n",
    "# Display \n",
    "for line in maze:\n",
    "    for block in line:\n",
    "        if block == math.inf:\n",
    "            print('*', end='')\n",
    "        else:\n",
    "            print(block, end='')\n",
    "    print()\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    \"\"\"A node class for A* Pathfinding\"\"\"\n",
    "    def __init__(self, parent=None, position=None):\n",
    "        self.parent = parent\n",
    "        self.position = position\n",
    "        self.edges = {}\n",
    "\n",
    "        self.g = 0\n",
    "        self.h = 0\n",
    "        self.f = 0\n",
    "        self.visit_count = 0\n",
    "\n",
    "    def visit(self):\n",
    "        self.visit_count += 1\n",
    "    def __eq__(self, other):\n",
    "        return self.position == other.position  \n",
    "    def neighbors(self, id):\n",
    "        return self.edges[id]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def astar(maze, graph_arr, visual_maze, visit_count,start, end):\n",
    "    \"\"\"Returns a list of tuples as a path from the given start to the given end in the given maze\"\"\"\n",
    "\n",
    "    # Create start and end node\n",
    "    start_node = Node(None, start)\n",
    "    start_node.g = start_node.h = start_node.f = 0\n",
    "    end_node = Node(None, end)\n",
    "    end_node.g = end_node.h = end_node.f = 0\n",
    "\n",
    "    # Initialize both open and closed list\n",
    "    open_list = []\n",
    "    closed_list = []\n",
    "\n",
    "    # Add the start node\n",
    "    open_list.append(start_node)\n",
    "\n",
    "    # Loop until you find the end\n",
    "    while len(open_list) > 0:\n",
    "        \n",
    "        # Get the current node\n",
    "        current_node = open_list[0]\n",
    "        current_index = 0\n",
    "        for index, item in enumerate(open_list):\n",
    "            if item.f < current_node.f:\n",
    "                current_node = item\n",
    "                current_index = index\n",
    "\n",
    "        # Pop current off open list, add to closed list\n",
    "        open_list.pop(current_index)\n",
    "        closed_list.append(current_node)\n",
    "\n",
    "        # Found the goal\n",
    "        if current_node == end_node:\n",
    "            path = []\n",
    "            current = current_node\n",
    "            while current is not None:\n",
    "                # Clear Output of each loop\n",
    "                clear_output(wait=True) \n",
    "                visual_maze[current.position[0]][current.position[1]] = \"<span style='color:blue'>\" + graph_arr[current.position[0]][current.position[1]] + \"</span>\"\n",
    "                display(Markdown('<br>'.join(''.join(block for block in line) for line in visual_maze)))\n",
    "                time.sleep(0.05)\n",
    "                path.append(current.position)\n",
    "                current = current.parent\n",
    "            return (path[::-1], visit_count) # Return reversed path\n",
    "\n",
    "        # Generate children\n",
    "        children = []\n",
    "        for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]: # Adjacent squares\n",
    "            # Clear Output of each loop\n",
    "            \n",
    "        \n",
    "            # Get node position\n",
    "            node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])\n",
    "\n",
    "            # Make sure within range\n",
    "            if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (len(maze[len(maze)-1]) -1) or node_position[1] < 0:\n",
    "                continue\n",
    "\n",
    "            # Make sure walkable terrain\n",
    "            if maze[node_position[0]][node_position[1]] != 0:\n",
    "                continue\n",
    "\n",
    "            # Create new node\n",
    "            new_node = Node(current_node, node_position)\n",
    "            visit_count[new_node.position[0]][new_node.position[1]] += 1\n",
    "            \n",
    "            \n",
    "            clear_output(wait=True) \n",
    "            \n",
    "            # Visualiztion \n",
    "            print(new_node.position)\n",
    "            print(visit_count[new_node.position[0]][new_node.position[1]])\n",
    "            visual_maze[new_node.position[0]][new_node.position[1]] = \"<span style='color:red'>\" + graph_arr[new_node.position[0]][new_node.position[1]] + \"</span>\"\n",
    "            display(Markdown('<br>'.join(''.join(block for block in line) for line in visual_maze)))\n",
    "            time.sleep(0.05)\n",
    "            visual_maze[new_node.position[0]][new_node.position[1]] = \"<span style='color:green'>\" + graph_arr[new_node.position[0]][new_node.position[1]] + \"</span>\"\n",
    "#            display(str(open_list))\n",
    "            \n",
    "            \n",
    "            # Append\n",
    "            children.append(new_node)\n",
    "#         for i in range(0, len(children)):\n",
    "#             for j in range(0, len(children)-1):\n",
    "#                 if children[j].f < children[j+1].f:\n",
    "#                     temp = children[j]\n",
    "#                     children[j] = children[j+1]\n",
    "#                     children[j+1] = temp\n",
    "                    \n",
    "        # Loop through children\n",
    "        for child in children:\n",
    "            \n",
    "            clear_output(wait=True) \n",
    "            \n",
    "#             # Visualiztion \n",
    "#             print(new_node.position)\n",
    "#             print(visit_count[new_node.position[0]][new_node.position[1]])\n",
    "#             visual_maze[child.position[0]][child.position[1]] = \"<span style='color:yellow'>\" + graph_arr[child.position[0]][child.position[1]] + \"</span>\"\n",
    "#             display(Markdown('<br>'.join(''.join(block for block in line) for line in visual_maze)))\n",
    "#             time.sleep(0.05)\n",
    "#             visual_maze[new_node.position[0]][new_node.position[1]] = \"<span style='color:green'>\" + graph_arr[child.position[0]][child.position[1]] + \"</span>\"\n",
    "# #            display(str(open_list))\n",
    "            \n",
    "            \n",
    "            # Child is on the closed list\n",
    "            for closed_child in closed_list:\n",
    "                if child == closed_child:\n",
    "                    continue\n",
    "            child.visit()\n",
    "            # Create the f, g, and h values\n",
    "            child.g = (current_node.g + 1) \n",
    "            # \n",
    "            child.h = ((child.position[0] - end_node.position[0]) **2 ) + ((child.position[1] - end_node.position[1]) **2 )\n",
    "            # Using 8-way Diagonal Distance\n",
    "            dx = abs(child.position[0] - end_node.position[0])\n",
    "            dy = abs(child.position[1] - end_node.position[1])\n",
    "            D = 1\n",
    "            D2 = 1.414 # root(2)\n",
    "#             child.h = D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)\n",
    "            child.f = child.g + child.h + (visit_count[child.position[0]][child.position[1]] ** 2)\n",
    "#             Child is already in the open list\n",
    "            for open_node in open_list:\n",
    "#                 display('BOMB1 ')\n",
    "                if child == open_node and child.g < open_node.g:\n",
    "#                     display('BOMB2')\n",
    "                    continue\n",
    "\n",
    "            # Add the child to the open list\n",
    "            open_list.append(child)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "<span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>s</span><br><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><br><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:black'>o</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:black'>o</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:blue'>p</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span>"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0, 35), (1, 34), (2, 33), (3, 32), (4, 31), (4, 30), (4, 29), (4, 28), (4, 27), (4, 26), (3, 25), (2, 24), (3, 23), (4, 22), (5, 21), (5, 20), (4, 19), (5, 18), (6, 17), (7, 16), (8, 15), (9, 14), (10, 13), (11, 12), (12, 11), (13, 10), (14, 9), (14, 8), (14, 7), (14, 6), (14, 5), (14, 4), (14, 3), (14, 2), (14, 1), (14, 0)]\n",
      "Distance : 36\n"
     ]
    }
   ],
   "source": [
    "start = (starting_point[1],starting_point[0])\n",
    "end = (end_point[1],end_point[0])\n",
    "print(start)\n",
    "print(end)\n",
    "path, cnt_grid = astar(copy.deepcopy(maze),copy.deepcopy(arr),copy.deepcopy(visual_arr),copy.deepcopy(visit_count), start, end)\n",
    "print(path)\n",
    "print('Distance : '+str(len(path)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Optimized A* Algorithm:\n",
    "References: [Stanford Dijkstra and A* Implementation](https://www.redblobgames.com/pathfinding/a-star/implementation.html)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SquareGrid:\n",
    "    def __init__(self, graph_arr, visual_arr):\n",
    "        self.graph_arr = graph_arr\n",
    "        self.visual_arr = visual_arr\n",
    "        self.width = len(graph_arr[0])\n",
    "        self.height = len(graph_arr)\n",
    "        self.weights = {}\n",
    "    \n",
    "    def cost(self, from_node, to_node):\n",
    "        return self.weights.get(to_node, 1)\n",
    "    \n",
    "    def in_bounds(self, id):\n",
    "        (x, y) = id\n",
    "#         print('Checking Bound')\n",
    "        return 0 <= x < self.width and 0 <= y < self.height\n",
    "    \n",
    "    def passable(self, id):\n",
    "        (y,x) = id\n",
    "#         print('checking passabliity : ' + str(self.graph_arr[x][y]))\n",
    "        if self.graph_arr[x][y] != 'o':\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def neighbors(self, id):\n",
    "        (x, y) = id\n",
    "        results = [(x+1, y), (x, y-1), (x-1, y), (x, y+1),(x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1)]\n",
    "        if (x + y) % 2 == 0: results.reverse() # aesthetics\n",
    "#         print('options : ' + str(results))\n",
    "        results2 = [point for point in results if self.in_bounds(point)]\n",
    "#         print('options in bound: ' + str([n for n in results2]))\n",
    "        results3 = [point for point in results2 if self.passable(point)]\n",
    "#         print('options passable: ' + str([n for n in results3]))\n",
    "        return list(results3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "\n",
    "class PriorityQueue:\n",
    "    def __init__(self):\n",
    "        self.elements = []\n",
    "    \n",
    "    def empty(self):\n",
    "        return len(self.elements) == 0\n",
    "    \n",
    "    def put(self, item, priority):\n",
    "        heapq.heappush(self.elements, (priority, item))\n",
    "    \n",
    "    def get(self):\n",
    "        return heapq.heappop(self.elements)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def heuristic(end_node, child):\n",
    "    (x1, y1) = end_node\n",
    "    (x2, y2) = child\n",
    "    h = ((x2 - x1) **2 ) + ((y2 - y1) **2 )\n",
    "# Using 8-way Diagonal Distance\n",
    "#     dx = abs(child[1] - end_node[1])\n",
    "#     dy = abs(child[0] - end_node[0])\n",
    "#     D = 1\n",
    "#     D2 = 1.414 # root(2)\n",
    "#     h = D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)\n",
    "    return h*(1.0 + 1/1000)\n",
    "\n",
    "def a_star_search(graph, start, goal):\n",
    "    frontier = PriorityQueue()\n",
    "    frontier.put(start, 0)\n",
    "    came_from = {}\n",
    "    cost_so_far = {}\n",
    "    came_from[start] = None\n",
    "    cost_so_far[start] = 0\n",
    "    print('Here')\n",
    "    while not frontier.empty():\n",
    "        current = frontier.get()\n",
    "        \n",
    "        if current == goal:\n",
    "            break\n",
    "        print(current)\n",
    "        for next in graph.neighbors(current):\n",
    "            new_cost = cost_so_far[current] + graph.cost(current, next)\n",
    "            # Visualiztion\n",
    "            clear_output(wait=True) \n",
    "            new_node = (next[1],next[0])\n",
    "            print(new_node)\n",
    "            print(new_cost)\n",
    "#             print(graph.graph_arr[new_node[0]][new_node[1]])\n",
    "            graph.visual_arr[new_node[0]][new_node[1]] = \"<span style='color:red'>\" + graph.graph_arr[new_node[0]][new_node[1]] + \"</span>\"\n",
    "            display(Markdown('<br>'.join(''.join(block for block in line) for line in graph.visual_arr)))\n",
    "            time.sleep(0.05)\n",
    "            graph.visual_arr[new_node[0]][new_node[1]] = \"<span style='color:green'>\" + graph.graph_arr[new_node[0]][new_node[1]] + \"</span>\"\n",
    "            \n",
    "            if next not in cost_so_far or new_cost < cost_so_far[next]:\n",
    "                cost_so_far[next] = new_cost\n",
    "                priority = new_cost + heuristic(goal, next)\n",
    "                frontier.put(next, priority)\n",
    "                came_from[next] = current\n",
    "    \n",
    "    traverser = goal\n",
    "    while traverser != None:\n",
    "        # Clear Output of each loop\n",
    "#         print(traverser)\n",
    "        clear_output(wait=True) \n",
    "        graph.visual_arr[traverser[1]][traverser[0]] = \"<span style='color:blue'>\" + graph.graph_arr[traverser[1]][traverser[0]] + \"</span>\"\n",
    "        display(Markdown('<br>'.join(''.join(block for block in line) for line in graph.visual_arr)))\n",
    "        time.sleep(0.05)\n",
    "        traverser = came_from[traverser]\n",
    "    \n",
    "    return came_from, cost_so_far"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "<span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>s</span><br><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><br><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:black'>o</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:black'>o</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:black'>o</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:black'>o</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><br><span style='color:blue'>p</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:green'>#</span><span style='color:green'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span><span style='color:orange'>#</span>"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "\n",
    "g = SquareGrid(copy.deepcopy(arr),copy.deepcopy(visual_arr))\n",
    "# print_grid(g.graph_arr)\n",
    "start = copy.deepcopy(tuple(starting_point))\n",
    "end = copy.deepcopy(tuple(end_point))\n",
    "# print('width : ' + str(g.width))\n",
    "# print('height : ' + str(g.height))\n",
    "came_from, cost_so_far = a_star_search(copy.deepcopy(g), start, end)\n",
    "# print(came_from)\n",
    "# print(cost_so_far)\n",
    "# print(len(came_from))\n",
    "# print(len(cost_so_far))\n",
    "\n",
    "visual_maze = copy.deepcopy(visual_arr)\n",
    "graph_arr = copy.deepcopy(arr)\n",
    "traverser = end\n",
    "# while traverser != None:\n",
    "#     # Clear Output of each loop\n",
    "#     print(traverser)\n",
    "#     clear_output(wait=True) \n",
    "#     visual_maze[traverser[1]][traverser[0]] = \"<span style='color:blue'>\" + graph_arr[traverser[1]][traverser[0]] + \"</span>\"\n",
    "#     display(Markdown('<br>'.join(''.join(block for block in line) for line in visual_maze)))\n",
    "#     time.sleep(0.05)\n",
    "#     traverser = came_from[traverser]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# BestFirstSearch\n",
    "\n",
    "References : [Very Similar to A* - Link](https://courses.cs.washington.edu/courses/cse326/03su/homework/hw3/bestfirstsearch.html)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BestFirstSearchSolver:\n",
    "    \n",
    "    def __init__(self, graph, visual_arr, start, goal, heuristic = 'manhattan'):\n",
    "        self.graph = copy.deepcopy(graph)\n",
    "        self.visual_arr = copy.deepcopy(graph)\n",
    "        self.start = start\n",
    "        self.goal = goal\n",
    "        self.heuristic_type = heuristic\n",
    "        self.width = len(graph[0])\n",
    "        self.height = len(graph)\n",
    "        self.node_graph = [[self.Node(True, (i,j)) for j in range(0, self.height)] for i in range(0, self.width)] \n",
    "        print('start : ' + str(start))\n",
    "        print('end : ' + str(end))\n",
    "        print('width : ' + str(self.width))\n",
    "        print('height : ' + str(self.height))\n",
    "    \n",
    "    \n",
    "    import heapq\n",
    "    import copy\n",
    "    \n",
    "    class PriorityQueue:\n",
    "        \n",
    "        def __init__(self):\n",
    "            self.elements = []\n",
    "    \n",
    "        def empty(self):\n",
    "            return len(self.elements) == 0\n",
    "\n",
    "        def put(self, item, priority):\n",
    "            return heapq.heappush(self.elements, (priority, item))\n",
    "\n",
    "        def get(self):\n",
    "            return heapq.heappop(self.elements)[1]\n",
    "    \n",
    "    class Node:\n",
    "        def __init__(self, parent=None, position=None):\n",
    "            self.parent = parent\n",
    "            self.position = position\n",
    "            self.edges = {}\n",
    "\n",
    "            self.g = 0\n",
    "            self.h = 0\n",
    "            self.f = 0\n",
    "            self.visit_count = 0\n",
    "            self.visited = False\n",
    "            self.examined = False\n",
    "\n",
    "        def visit(self):\n",
    "            self.visit_count += 1\n",
    "            self.visited = True\n",
    "\n",
    "        def mark_examined(self):\n",
    "            self.examined = True\n",
    "            \n",
    "        def __eq__(self, other):\n",
    "            return self.position == other.position  \n",
    "        \n",
    "        def __lt__(self, other):\n",
    "            return self.position < other.position\n",
    "#   \n",
    "\n",
    "    def get_node(self, position):\n",
    "        print(position)\n",
    "        (x,y) = position\n",
    "        return self.node_graph[x][y]\n",
    "        \n",
    "    def in_bounds(self, node_position):\n",
    "        (x, y) = node_position\n",
    "#         print('Checking Bound')\n",
    "        return 0 <= x < self.width and 0 <= y < self.height\n",
    "\n",
    "    def passable(self, node_position):\n",
    "        (y,x) = node_position\n",
    "#         print('checking passabliity : ' + str(self.graph_arr[x][y]))\n",
    "        if self.graph[x][y] != 'o':\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def neighbors(self, node):\n",
    "        (x, y) = node.position\n",
    "        results = [(x+1, y), (x, y-1), (x-1, y), (x, y+1),(x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1)]\n",
    "        if (x + y) % 2 == 0: results.reverse() # aesthetics\n",
    "#         print('options : ' + str(results))\n",
    "        results2 = [point for point in results if self.in_bounds(point)]\n",
    "#         print('options in bound: ' + str([n for n in results2]))\n",
    "        results3 = [ self.get_node(point) for point in results2 if self.passable(point)]\n",
    "#         print('options passable: ' + str([n for n in results3]))\n",
    "        return list(results3)\n",
    "    \n",
    "    def heuristic(self,child, end_node, child_visit_cnt):\n",
    "        (x1, y1) = end_node\n",
    "        (x2, y2) = child \n",
    "        h = ((x2 - x1) **2 ) + ((y2 - y1) **2 ) + child_visit_cnt**2\n",
    "    # Using 8-way Diagonal Distance\n",
    "    #     dx = abs(child[1] - end_node[1])\n",
    "    #     dy = abs(child[0] - end_node[0])\n",
    "    #     D = 1\n",
    "    #     D2 = 1.414 # root(2)\n",
    "    #     h = D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)\n",
    "        return h\n",
    "\n",
    "    \n",
    "    \n",
    "    def VisualizeBreadthFirstSolve(self):\n",
    "        pqueue = PriorityQueue()\n",
    "        start_node = self.get_node(self.start)\n",
    "        end_node = self.get_node(self.goal)\n",
    "        pqueue.put(start_node, 0) # Inititial point and priority\n",
    "        flag = False\n",
    "        while not pqueue.empty():\n",
    "            current = pqueue.get()\n",
    "            if current == end_node or flag:\n",
    "                path = []\n",
    "                current = current\n",
    "                while current is not None:\n",
    "                    clear_output(wait=True) \n",
    "                    self.visual_arr[current.position[1]][current.position[0]] = \"<span style='color:blue'>\" + self.graph[current.position[1]][current.position[0]] + \"</span>\"\n",
    "                    display(Markdown('<br>'.join(''.join(block for block in line) for line in self.visual_arr)))\n",
    "                    time.sleep(0.05)\n",
    "                    path.append(current.position)\n",
    "                    current = current.parent\n",
    "                return path\n",
    "                break\n",
    "            else:\n",
    "                for neighbor in self.neighbors(current):\n",
    "                    neighbor.parent = current\n",
    "                    if neighbor is not neighbor.visited:\n",
    "                        \n",
    "                        neighbor.visit()\n",
    "                        h = self.heuristic(neighbor.position, self.goal, neighbor.visit_count)\n",
    "                        \n",
    "                        if neighbor == end_node:\n",
    "                            flag= True\n",
    "                            break\n",
    "                        \n",
    "                        # Visualization\n",
    "                        clear_output(wait=True) \n",
    "#                         print(str(neighbor.position) + str(neighbor.visit_count))\n",
    "                        self.visual_arr[neighbor.position[1]][neighbor.position[0]] = \"<span style='color:red'>\" + self.graph[neighbor.position[1]][neighbor.position[0]] + \"</span>\"\n",
    "                        display(Markdown('<br>'.join(''.join(block for block in line) for line in self.visual_arr)))\n",
    "                        time.sleep(0.05)\n",
    "                        self.visual_arr[neighbor.position[1]][neighbor.position[0]] = \"<span style='color:yellow'>\" + self.graph[neighbor.position[1]][neighbor.position[0]] + \"</span>\"\n",
    "                         \n",
    "                        \n",
    "                        \n",
    "                        pqueue.put(neighbor, h)\n",
    "                        \n",
    "                        \n",
    "              \n",
    "                            \n",
    "                current.mark_examined()\n",
    "                  # Visualization\n",
    "                clear_output(wait=True) \n",
    "                self.visual_arr[current.position[1]][current.position[0]] = \"<span style='color:purple'>\" + self.graph[current.position[1]][current.position[0]] + \"</span>\"\n",
    "                display(Markdown('<br>'.join(''.join(block for block in line) for line in self.visual_arr)))\n",
    "                time.sleep(0.05)\n",
    "                self.visual_arr[current.position[1]][current.position[0]] = \"<span style='color:green'>\" + self.graph[current.position[1]][current.position[0]] + \"</span>\"\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "start : [35, 0]\n",
      "end : (0, 14)\n",
      "width : 36\n",
      "height : 15\n"
     ]
    }
   ],
   "source": [
    "bestfs = BestFirstSearchSolver(arr, visual_arr, starting_point, end_point)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "ooooooooooooo####################<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>s</span><br>ooooooooooooo##########<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>######<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><br>ooooooooooooo#########<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>####<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><br>##################<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>o<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>#<br>#################<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>o<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>##<br>############o###<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>o<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>oooooooooooo<br>############o##<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>o<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>#oooooooooooo<br>######o#####o#<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>o<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>#oooooooooooo<br>######o#####o<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>#o<span style='color:yellow'>#</span><span style='color:green'>#</span><span style='color:yellow'>#</span>#############<br>######o#####o<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>#ooooooooooooo#####<br>######o####<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>##ooooooooooooo#####<br>######o###<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>###ooooooooooooo#####<br>#####oooo<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>####ooooooooooooo#####<br>#<span style='color:blue'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>o<span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>#######################<br>p<span style='color:blue'>#</span><span style='color:blue'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span><span style='color:yellow'>#</span>########################"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "path = bestfs.VisualizeBreadthFirstSolve()\n",
    "print(path)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Reverse Path not Complete"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}