project_notebook.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "source": [
    "# Implementing a Route Planner\n",
    "In this project you will use A\\* search to implement a \"Google-maps\" style route planning algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## The Map"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The autoreload extension is already loaded. To reload it, use:\n",
      "  %reload_ext autoreload\n"
     ]
    }
   ],
   "source": [
    "# Run this cell first!\n",
    "\n",
    "from helpers import Map, load_map_10, load_map_40, show_map\n",
    "import math\n",
    "\n",
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Map Basics\n",
    "The map below shows a disconnected network of 10 intersections. The two intersections on the left are connected to each other but they are not connected to the rest of the road network. This map is quite literal in its expression of distance and connectivity. On the graph above, the edge between 2 nodes(intersections) represents a literal straight road not just an abstract connection of 2 cities.\n",
    "\n",
    "These `Map` objects have two properties you will want to use to implement A\\* search: **`intersections`** and **`roads`**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "map_10 = load_map_10()\n",
    "show_map(map_10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "application/vnd.plotly.v1+json": {
       "data": [
        {
         "hoverinfo": "none",
         "line": {
          "color": "#888",
          "width": 0.5
         },
         "mode": "lines",
         "type": "scatter",
         "x": [
          0.7801603911549438,
          0.6435799740880603,
          null,
          0.7801603911549438,
          0.583993110207876,
          null,
          0.7801603911549438,
          0.740625863119245,
          null,
          0.7801603911549438,
          0.607698913404794,
          null,
          0.7801603911549438,
          0.640952694324525,
          null,
          0.5249831588690298,
          0.607698913404794,
          null,
          0.5249831588690298,
          0.719569201584275,
          null,
          0.5249831588690298,
          0.3073865727705063,
          null,
          0.5249831588690298,
          0.4238357358399233,
          null,
          0.5249831588690298,
          0.313999018186756,
          null,
          0.5249831588690298,
          0.4582523173083307,
          null,
          0.5249831588690298,
          0.6243437191127235,
          null,
          0.5249831588690298,
          0.5572917679006295,
          null,
          0.5249831588690298,
          0.7482655725962591,
          null,
          0.5249831588690298,
          0.640952694324525,
          null,
          0.8085335344099086,
          0.8860336256842246,
          null,
          0.8085335344099086,
          0.740625863119245,
          null,
          0.8085335344099086,
          0.8252497121120052,
          null,
          0.8085335344099086,
          0.6315322816286787,
          null,
          0.8085335344099086,
          0.8551947714242674,
          null,
          0.8085335344099086,
          0.6824813442515916,
          null,
          0.8085335344099086,
          0.7353838928272886,
          null,
          0.2599134798656856,
          0.25311953895059136,
          null,
          0.2599134798656856,
          0.3073865727705063,
          null,
          0.2599134798656856,
          0.4238357358399233,
          null,
          0.2599134798656856,
          0.313999018186756,
          null,
          0.2599134798656856,
          0.4582523173083307,
          null,
          0.7353838928272886,
          0.8860336256842246,
          null,
          0.7353838928272886,
          0.740625863119245,
          null,
          0.7353838928272886,
          0.8252497121120052,
          null,
          0.7353838928272886,
          0.6315322816286787,
          null,
          0.7353838928272886,
          0.8551947714242674,
          null,
          0.7353838928272886,
          0.6824813442515916,
          null,
          0.09088671576431506,
          0.17440205342790494,
          null,
          0.09088671576431506,
          0.12939557977525573,
          null,
          0.09088671576431506,
          0.04580558670435442,
          null,
          0.313999018186756,
          0.4238357358399233,
          null,
          0.313999018186756,
          0.3073865727705063,
          null,
          0.313999018186756,
          0.25311953895059136,
          null,
          0.313999018186756,
          0.4582523173083307,
          null,
          0.6824813442515916,
          0.8860336256842246,
          null,
          0.6824813442515916,
          0.740625863119245,
          null,
          0.6824813442515916,
          0.8252497121120052,
          null,
          0.6824813442515916,
          0.47415009287034726,
          null,
          0.6824813442515916,
          0.6315322816286787,
          null,
          0.6824813442515916,
          0.8551947714242674,
          null,
          0.20128789391122526,
          0.1332965908314021,
          null,
          0.20128789391122526,
          0.04580558670435442,
          null,
          0.20128789391122526,
          0.021423673670808885,
          null,
          0.8551947714242674,
          0.8860336256842246,
          null,
          0.8551947714242674,
          0.740625863119245,
          null,
          0.8551947714242674,
          0.8252497121120052,
          null,
          0.7581736589784409,
          0.607698913404794,
          null,
          0.7581736589784409,
          0.719569201584275,
          null,
          0.7581736589784409,
          0.9363713903322148,
          null,
          0.7581736589784409,
          0.6243437191127235,
          null,
          0.7581736589784409,
          0.5572917679006295,
          null,
          0.7581736589784409,
          0.7482655725962591,
          null,
          0.7581736589784409,
          0.9112422509614865,
          null,
          0.7581736589784409,
          0.640952694324525,
          null,
          0.25311953895059136,
          0.3073865727705063,
          null,
          0.25311953895059136,
          0.4238357358399233,
          null,
          0.25311953895059136,
          0.4582523173083307,
          null,
          0.4813859169876731,
          0.607698913404794,
          null,
          0.4813859169876731,
          0.583993110207876,
          null,
          0.4813859169876731,
          0.3345284735051981,
          null,
          0.4813859169876731,
          0.47415009287034726,
          null,
          0.4813859169876731,
          0.6435799740880603,
          null,
          0.4813859169876731,
          0.640952694324525,
          null,
          0.9112422509614865,
          0.9363713903322148,
          null,
          0.9112422509614865,
          0.7482655725962591,
          null,
          0.9112422509614865,
          0.719569201584275,
          null,
          0.04580558670435442,
          0.1332965908314021,
          null,
          0.04580558670435442,
          0.021423673670808885,
          null,
          0.04580558670435442,
          0.12939557977525573,
          null,
          0.4582523173083307,
          0.4238357358399233,
          null,
          0.4582523173083307,
          0.607698913404794,
          null,
          0.4582523173083307,
          0.640952694324525,
          null,
          0.4582523173083307,
          0.6243437191127235,
          null,
          0.4582523173083307,
          0.5572917679006295,
          null,
          0.4582523173083307,
          0.3073865727705063,
          null,
          0.12939557977525573,
          0.021423673670808885,
          null,
          0.12939557977525573,
          0.3345284735051981,
          null,
          0.607698913404794,
          0.583993110207876,
          null,
          0.607698913404794,
          0.6243437191127235,
          null,
          0.607698913404794,
          0.719569201584275,
          null,
          0.607698913404794,
          0.6435799740880603,
          null,
          0.607698913404794,
          0.640952694324525,
          null,
          0.607698913404794,
          0.5572917679006295,
          null,
          0.719569201584275,
          0.5572917679006295,
          null,
          0.719569201584275,
          0.9363713903322148,
          null,
          0.719569201584275,
          0.6243437191127235,
          null,
          0.719569201584275,
          0.7482655725962591,
          null,
          0.719569201584275,
          0.640952694324525,
          null,
          0.8860336256842246,
          0.8252497121120052,
          null,
          0.4238357358399233,
          0.5572917679006295,
          null,
          0.4238357358399233,
          0.3073865727705063,
          null,
          0.47415009287034726,
          0.34509802713919313,
          null,
          0.47415009287034726,
          0.6315322816286787,
          null,
          0.47415009287034726,
          0.3345284735051981,
          null,
          0.26253385360950576,
          0.17440205342790494,
          null,
          0.26253385360950576,
          0.34509802713919313,
          null,
          0.26253385360950576,
          0.17972981733780147,
          null,
          0.9363713903322148,
          0.7482655725962591,
          null,
          0.6243437191127235,
          0.7482655725962591,
          null,
          0.6243437191127235,
          0.5572917679006295,
          null,
          0.6243437191127235,
          0.640952694324525,
          null,
          0.6243437191127235,
          0.583993110207876,
          null,
          0.5572917679006295,
          0.7482655725962591,
          null,
          0.5572917679006295,
          0.640952694324525,
          null,
          0.5572917679006295,
          0.583993110207876,
          null,
          0.7482655725962591,
          0.640952694324525,
          null,
          0.6435799740880603,
          0.583993110207876,
          null,
          0.6435799740880603,
          0.740625863119245,
          null,
          0.6435799740880603,
          0.6315322816286787,
          null,
          0.6435799740880603,
          0.640952694324525,
          null,
          0.34509802713919313,
          0.17440205342790494,
          null,
          0.34509802713919313,
          0.3345284735051981,
          null,
          0.34509802713919313,
          0.17972981733780147,
          null,
          0.021423673670808885,
          0.1332965908314021,
          null,
          0.640952694324525,
          0.583993110207876,
          null,
          0.17440205342790494,
          0.17972981733780147,
          null,
          0.740625863119245,
          0.6315322816286787,
          null
         ],
         "y": [
          0.49474860768712914,
          0.5488515965193208,
          null,
          0.49474860768712914,
          0.42704536740474663,
          null,
          0.49474860768712914,
          0.68128520136847,
          null,
          0.49474860768712914,
          0.362322730884702,
          null,
          0.49474860768712914,
          0.3232711412508066,
          null,
          0.14953665513987202,
          0.362322730884702,
          null,
          0.14953665513987202,
          0.13985272363426526,
          null,
          0.14953665513987202,
          0.09186645974288632,
          null,
          0.14953665513987202,
          0.026771817842421997,
          null,
          0.14953665513987202,
          0.01876171413125327,
          null,
          0.14953665513987202,
          0.1735506267461867,
          null,
          0.14953665513987202,
          0.21665962402659544,
          null,
          0.14953665513987202,
          0.2083567880838434,
          null,
          0.14953665513987202,
          0.12631654071213483,
          null,
          0.14953665513987202,
          0.3232711412508066,
          null,
          0.7696330846542071,
          0.891868301175821,
          null,
          0.7696330846542071,
          0.68128520136847,
          null,
          0.7696330846542071,
          0.9532681441921305,
          null,
          0.7696330846542071,
          0.7311657634689946,
          null,
          0.7696330846542071,
          0.9011339078096633,
          null,
          0.7696330846542071,
          0.8016111783687677,
          null,
          0.7696330846542071,
          0.8089961609345658,
          null,
          0.14485659826020547,
          0.10321622277398101,
          null,
          0.14485659826020547,
          0.09186645974288632,
          null,
          0.14485659826020547,
          0.026771817842421997,
          null,
          0.14485659826020547,
          0.01876171413125327,
          null,
          0.14485659826020547,
          0.1735506267461867,
          null,
          0.8089961609345658,
          0.891868301175821,
          null,
          0.8089961609345658,
          0.68128520136847,
          null,
          0.8089961609345658,
          0.9532681441921305,
          null,
          0.8089961609345658,
          0.7311657634689946,
          null,
          0.8089961609345658,
          0.9011339078096633,
          null,
          0.8089961609345658,
          0.8016111783687677,
          null,
          0.7222846879290787,
          0.9528527425842739,
          null,
          0.7222846879290787,
          0.690016328140396,
          null,
          0.7222846879290787,
          0.5886703168399895,
          null,
          0.01876171413125327,
          0.026771817842421997,
          null,
          0.01876171413125327,
          0.09186645974288632,
          null,
          0.01876171413125327,
          0.10321622277398101,
          null,
          0.01876171413125327,
          0.1735506267461867,
          null,
          0.8016111783687677,
          0.891868301175821,
          null,
          0.8016111783687677,
          0.68128520136847,
          null,
          0.8016111783687677,
          0.9532681441921305,
          null,
          0.8016111783687677,
          0.7353428557575755,
          null,
          0.8016111783687677,
          0.7311657634689946,
          null,
          0.8016111783687677,
          0.9011339078096633,
          null,
          0.43196344222361227,
          0.3996510641743197,
          null,
          0.43196344222361227,
          0.5886703168399895,
          null,
          0.43196344222361227,
          0.4666482714834408,
          null,
          0.9011339078096633,
          0.891868301175821,
          null,
          0.9011339078096633,
          0.68128520136847,
          null,
          0.9011339078096633,
          0.9532681441921305,
          null,
          0.24026772497187532,
          0.362322730884702,
          null,
          0.24026772497187532,
          0.13985272363426526,
          null,
          0.24026772497187532,
          0.13022993020357043,
          null,
          0.24026772497187532,
          0.21665962402659544,
          null,
          0.24026772497187532,
          0.2083567880838434,
          null,
          0.24026772497187532,
          0.12631654071213483,
          null,
          0.24026772497187532,
          0.1839028760606296,
          null,
          0.24026772497187532,
          0.3232711412508066,
          null,
          0.10321622277398101,
          0.09186645974288632,
          null,
          0.10321622277398101,
          0.026771817842421997,
          null,
          0.10321622277398101,
          0.1735506267461867,
          null,
          0.5006237737207431,
          0.362322730884702,
          null,
          0.5006237737207431,
          0.42704536740474663,
          null,
          0.5006237737207431,
          0.6569436279895382,
          null,
          0.5006237737207431,
          0.7353428557575755,
          null,
          0.5006237737207431,
          0.5488515965193208,
          null,
          0.5006237737207431,
          0.3232711412508066,
          null,
          0.1839028760606296,
          0.13022993020357043,
          null,
          0.1839028760606296,
          0.12631654071213483,
          null,
          0.1839028760606296,
          0.13985272363426526,
          null,
          0.5886703168399895,
          0.3996510641743197,
          null,
          0.5886703168399895,
          0.4666482714834408,
          null,
          0.5886703168399895,
          0.690016328140396,
          null,
          0.1735506267461867,
          0.026771817842421997,
          null,
          0.1735506267461867,
          0.362322730884702,
          null,
          0.1735506267461867,
          0.3232711412508066,
          null,
          0.1735506267461867,
          0.21665962402659544,
          null,
          0.1735506267461867,
          0.2083567880838434,
          null,
          0.1735506267461867,
          0.09186645974288632,
          null,
          0.690016328140396,
          0.4666482714834408,
          null,
          0.690016328140396,
          0.6569436279895382,
          null,
          0.362322730884702,
          0.42704536740474663,
          null,
          0.362322730884702,
          0.21665962402659544,
          null,
          0.362322730884702,
          0.13985272363426526,
          null,
          0.362322730884702,
          0.5488515965193208,
          null,
          0.362322730884702,
          0.3232711412508066,
          null,
          0.362322730884702,
          0.2083567880838434,
          null,
          0.13985272363426526,
          0.2083567880838434,
          null,
          0.13985272363426526,
          0.13022993020357043,
          null,
          0.13985272363426526,
          0.21665962402659544,
          null,
          0.13985272363426526,
          0.12631654071213483,
          null,
          0.13985272363426526,
          0.3232711412508066,
          null,
          0.891868301175821,
          0.9532681441921305,
          null,
          0.026771817842421997,
          0.2083567880838434,
          null,
          0.026771817842421997,
          0.09186645974288632,
          null,
          0.7353428557575755,
          0.8800306496459869,
          null,
          0.7353428557575755,
          0.7311657634689946,
          null,
          0.7353428557575755,
          0.6569436279895382,
          null,
          0.9768234503830939,
          0.9528527425842739,
          null,
          0.9768234503830939,
          0.8800306496459869,
          null,
          0.9768234503830939,
          0.999395685828547,
          null,
          0.13022993020357043,
          0.12631654071213483,
          null,
          0.21665962402659544,
          0.12631654071213483,
          null,
          0.21665962402659544,
          0.2083567880838434,
          null,
          0.21665962402659544,
          0.3232711412508066,
          null,
          0.21665962402659544,
          0.42704536740474663,
          null,
          0.2083567880838434,
          0.12631654071213483,
          null,
          0.2083567880838434,
          0.3232711412508066,
          null,
          0.2083567880838434,
          0.42704536740474663,
          null,
          0.12631654071213483,
          0.3232711412508066,
          null,
          0.5488515965193208,
          0.42704536740474663,
          null,
          0.5488515965193208,
          0.68128520136847,
          null,
          0.5488515965193208,
          0.7311657634689946,
          null,
          0.5488515965193208,
          0.3232711412508066,
          null,
          0.8800306496459869,
          0.9528527425842739,
          null,
          0.8800306496459869,
          0.6569436279895382,
          null,
          0.8800306496459869,
          0.999395685828547,
          null,
          0.4666482714834408,
          0.3996510641743197,
          null,
          0.3232711412508066,
          0.42704536740474663,
          null,
          0.9528527425842739,
          0.999395685828547,
          null,
          0.68128520136847,
          0.7311657634689946,
          null
         ]
        },
        {
         "hoverinfo": "text",
         "marker": {
          "color": [
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0
          ],
          "colorbar": {
           "thickness": 15,
           "title": "Node Connections",
           "titleside": "right",
           "xanchor": "left"
          },
          "colorscale": "Hot",
          "line": {
           "width": 2
          },
          "reversescale": true,
          "showscale": false,
          "size": 10
         },
         "mode": "markers",
         "text": [
          "Intersection 0",
          "Intersection 1",
          "Intersection 2",
          "Intersection 3",
          "Intersection 4",
          "Intersection 5",
          "Intersection 6",
          "Intersection 7",
          "Intersection 8",
          "Intersection 9",
          "Intersection 10",
          "Intersection 11",
          "Intersection 12",
          "Intersection 13",
          "Intersection 14",
          "Intersection 15",
          "Intersection 16",
          "Intersection 17",
          "Intersection 18",
          "Intersection 19",
          "Intersection 20",
          "Intersection 21",
          "Intersection 22",
          "Intersection 23",
          "Intersection 24",
          "Intersection 25",
          "Intersection 26",
          "Intersection 27",
          "Intersection 28",
          "Intersection 29",
          "Intersection 30",
          "Intersection 31",
          "Intersection 32",
          "Intersection 33",
          "Intersection 34",
          "Intersection 35",
          "Intersection 36",
          "Intersection 37",
          "Intersection 38",
          "Intersection 39"
         ],
         "type": "scatter",
         "x": [
          0.7801603911549438,
          0.5249831588690298,
          0.8085335344099086,
          0.2599134798656856,
          0.7353838928272886,
          0.09088671576431506,
          0.313999018186756,
          0.6824813442515916,
          0.20128789391122526,
          0.8551947714242674,
          0.7581736589784409,
          0.25311953895059136,
          0.4813859169876731,
          0.9112422509614865,
          0.04580558670435442,
          0.4582523173083307,
          0.12939557977525573,
          0.607698913404794,
          0.719569201584275,
          0.8860336256842246,
          0.4238357358399233,
          0.8252497121120052,
          0.47415009287034726,
          0.26253385360950576,
          0.9363713903322148,
          0.6243437191127235,
          0.5572917679006295,
          0.7482655725962591,
          0.6435799740880603,
          0.34509802713919313,
          0.021423673670808885,
          0.640952694324525,
          0.17440205342790494,
          0.1332965908314021,
          0.583993110207876,
          0.3073865727705063,
          0.740625863119245,
          0.3345284735051981,
          0.17972981733780147,
          0.6315322816286787
         ],
         "y": [
          0.49474860768712914,
          0.14953665513987202,
          0.7696330846542071,
          0.14485659826020547,
          0.8089961609345658,
          0.7222846879290787,
          0.01876171413125327,
          0.8016111783687677,
          0.43196344222361227,
          0.9011339078096633,
          0.24026772497187532,
          0.10321622277398101,
          0.5006237737207431,
          0.1839028760606296,
          0.5886703168399895,
          0.1735506267461867,
          0.690016328140396,
          0.362322730884702,
          0.13985272363426526,
          0.891868301175821,
          0.026771817842421997,
          0.9532681441921305,
          0.7353428557575755,
          0.9768234503830939,
          0.13022993020357043,
          0.21665962402659544,
          0.2083567880838434,
          0.12631654071213483,
          0.5488515965193208,
          0.8800306496459869,
          0.4666482714834408,
          0.3232711412508066,
          0.9528527425842739,
          0.3996510641743197,
          0.42704536740474663,
          0.09186645974288632,
          0.68128520136847,
          0.6569436279895382,
          0.999395685828547,
          0.7311657634689946
         ]
        }
       ],
       "layout": {
        "hovermode": "closest",
        "margin": {
         "b": 20,
         "l": 5,
         "r": 5,
         "t": 40
        },
        "showlegend": false,
        "title": "<br>Network graph made with Python",
        "titlefont": {
         "size": 16
        },
        "xaxis": {
         "showgrid": false,
         "showticklabels": false,
         "zeroline": false
        },
        "yaxis": {
         "showgrid": false,
         "showticklabels": false,
         "zeroline": false
        }
       }
      },
      "text/html": [
       "<div id=\"3714f57a-0569-40c3-8dd8-ebf31443a415\" style=\"height: 525px; width: 100%;\" class=\"plotly-graph-div\"></div><script type=\"text/javascript\">require([\"plotly\"], function(Plotly) { window.PLOTLYENV=window.PLOTLYENV || {};window.PLOTLYENV.BASE_URL=\"https://plot.ly\";Plotly.newPlot(\"3714f57a-0569-40c3-8dd8-ebf31443a415\", [{\"mode\": \"lines\", \"x\": [0.7801603911549438, 0.6435799740880603, null, 0.7801603911549438, 0.583993110207876, null, 0.7801603911549438, 0.740625863119245, null, 0.7801603911549438, 0.607698913404794, null, 0.7801603911549438, 0.640952694324525, null, 0.5249831588690298, 0.607698913404794, null, 0.5249831588690298, 0.719569201584275, null, 0.5249831588690298, 0.3073865727705063, null, 0.5249831588690298, 0.4238357358399233, null, 0.5249831588690298, 0.313999018186756, null, 0.5249831588690298, 0.4582523173083307, null, 0.5249831588690298, 0.6243437191127235, null, 0.5249831588690298, 0.5572917679006295, null, 0.5249831588690298, 0.7482655725962591, null, 0.5249831588690298, 0.640952694324525, null, 0.8085335344099086, 0.8860336256842246, null, 0.8085335344099086, 0.740625863119245, null, 0.8085335344099086, 0.8252497121120052, null, 0.8085335344099086, 0.6315322816286787, null, 0.8085335344099086, 0.8551947714242674, null, 0.8085335344099086, 0.6824813442515916, null, 0.8085335344099086, 0.7353838928272886, null, 0.2599134798656856, 0.25311953895059136, null, 0.2599134798656856, 0.3073865727705063, null, 0.2599134798656856, 0.4238357358399233, null, 0.2599134798656856, 0.313999018186756, null, 0.2599134798656856, 0.4582523173083307, null, 0.7353838928272886, 0.8860336256842246, null, 0.7353838928272886, 0.740625863119245, null, 0.7353838928272886, 0.8252497121120052, null, 0.7353838928272886, 0.6315322816286787, null, 0.7353838928272886, 0.8551947714242674, null, 0.7353838928272886, 0.6824813442515916, null, 0.09088671576431506, 0.17440205342790494, null, 0.09088671576431506, 0.12939557977525573, null, 0.09088671576431506, 0.04580558670435442, null, 0.313999018186756, 0.4238357358399233, null, 0.313999018186756, 0.3073865727705063, null, 0.313999018186756, 0.25311953895059136, null, 0.313999018186756, 0.4582523173083307, null, 0.6824813442515916, 0.8860336256842246, null, 0.6824813442515916, 0.740625863119245, null, 0.6824813442515916, 0.8252497121120052, null, 0.6824813442515916, 0.47415009287034726, null, 0.6824813442515916, 0.6315322816286787, null, 0.6824813442515916, 0.8551947714242674, null, 0.20128789391122526, 0.1332965908314021, null, 0.20128789391122526, 0.04580558670435442, null, 0.20128789391122526, 0.021423673670808885, null, 0.8551947714242674, 0.8860336256842246, null, 0.8551947714242674, 0.740625863119245, null, 0.8551947714242674, 0.8252497121120052, null, 0.7581736589784409, 0.607698913404794, null, 0.7581736589784409, 0.719569201584275, null, 0.7581736589784409, 0.9363713903322148, null, 0.7581736589784409, 0.6243437191127235, null, 0.7581736589784409, 0.5572917679006295, null, 0.7581736589784409, 0.7482655725962591, null, 0.7581736589784409, 0.9112422509614865, null, 0.7581736589784409, 0.640952694324525, null, 0.25311953895059136, 0.3073865727705063, null, 0.25311953895059136, 0.4238357358399233, null, 0.25311953895059136, 0.4582523173083307, null, 0.4813859169876731, 0.607698913404794, null, 0.4813859169876731, 0.583993110207876, null, 0.4813859169876731, 0.3345284735051981, null, 0.4813859169876731, 0.47415009287034726, null, 0.4813859169876731, 0.6435799740880603, null, 0.4813859169876731, 0.640952694324525, null, 0.9112422509614865, 0.9363713903322148, null, 0.9112422509614865, 0.7482655725962591, null, 0.9112422509614865, 0.719569201584275, null, 0.04580558670435442, 0.1332965908314021, null, 0.04580558670435442, 0.021423673670808885, null, 0.04580558670435442, 0.12939557977525573, null, 0.4582523173083307, 0.4238357358399233, null, 0.4582523173083307, 0.607698913404794, null, 0.4582523173083307, 0.640952694324525, null, 0.4582523173083307, 0.6243437191127235, null, 0.4582523173083307, 0.5572917679006295, null, 0.4582523173083307, 0.3073865727705063, null, 0.12939557977525573, 0.021423673670808885, null, 0.12939557977525573, 0.3345284735051981, null, 0.607698913404794, 0.583993110207876, null, 0.607698913404794, 0.6243437191127235, null, 0.607698913404794, 0.719569201584275, null, 0.607698913404794, 0.6435799740880603, null, 0.607698913404794, 0.640952694324525, null, 0.607698913404794, 0.5572917679006295, null, 0.719569201584275, 0.5572917679006295, null, 0.719569201584275, 0.9363713903322148, null, 0.719569201584275, 0.6243437191127235, null, 0.719569201584275, 0.7482655725962591, null, 0.719569201584275, 0.640952694324525, null, 0.8860336256842246, 0.8252497121120052, null, 0.4238357358399233, 0.5572917679006295, null, 0.4238357358399233, 0.3073865727705063, null, 0.47415009287034726, 0.34509802713919313, null, 0.47415009287034726, 0.6315322816286787, null, 0.47415009287034726, 0.3345284735051981, null, 0.26253385360950576, 0.17440205342790494, null, 0.26253385360950576, 0.34509802713919313, null, 0.26253385360950576, 0.17972981733780147, null, 0.9363713903322148, 0.7482655725962591, null, 0.6243437191127235, 0.7482655725962591, null, 0.6243437191127235, 0.5572917679006295, null, 0.6243437191127235, 0.640952694324525, null, 0.6243437191127235, 0.583993110207876, null, 0.5572917679006295, 0.7482655725962591, null, 0.5572917679006295, 0.640952694324525, null, 0.5572917679006295, 0.583993110207876, null, 0.7482655725962591, 0.640952694324525, null, 0.6435799740880603, 0.583993110207876, null, 0.6435799740880603, 0.740625863119245, null, 0.6435799740880603, 0.6315322816286787, null, 0.6435799740880603, 0.640952694324525, null, 0.34509802713919313, 0.17440205342790494, null, 0.34509802713919313, 0.3345284735051981, null, 0.34509802713919313, 0.17972981733780147, null, 0.021423673670808885, 0.1332965908314021, null, 0.640952694324525, 0.583993110207876, null, 0.17440205342790494, 0.17972981733780147, null, 0.740625863119245, 0.6315322816286787, null], \"type\": \"scatter\", \"hoverinfo\": \"none\", \"y\": [0.49474860768712914, 0.5488515965193208, null, 0.49474860768712914, 0.42704536740474663, null, 0.49474860768712914, 0.68128520136847, null, 0.49474860768712914, 0.362322730884702, null, 0.49474860768712914, 0.3232711412508066, null, 0.14953665513987202, 0.362322730884702, null, 0.14953665513987202, 0.13985272363426526, null, 0.14953665513987202, 0.09186645974288632, null, 0.14953665513987202, 0.026771817842421997, null, 0.14953665513987202, 0.01876171413125327, null, 0.14953665513987202, 0.1735506267461867, null, 0.14953665513987202, 0.21665962402659544, null, 0.14953665513987202, 0.2083567880838434, null, 0.14953665513987202, 0.12631654071213483, null, 0.14953665513987202, 0.3232711412508066, null, 0.7696330846542071, 0.891868301175821, null, 0.7696330846542071, 0.68128520136847, null, 0.7696330846542071, 0.9532681441921305, null, 0.7696330846542071, 0.7311657634689946, null, 0.7696330846542071, 0.9011339078096633, null, 0.7696330846542071, 0.8016111783687677, null, 0.7696330846542071, 0.8089961609345658, null, 0.14485659826020547, 0.10321622277398101, null, 0.14485659826020547, 0.09186645974288632, null, 0.14485659826020547, 0.026771817842421997, null, 0.14485659826020547, 0.01876171413125327, null, 0.14485659826020547, 0.1735506267461867, null, 0.8089961609345658, 0.891868301175821, null, 0.8089961609345658, 0.68128520136847, null, 0.8089961609345658, 0.9532681441921305, null, 0.8089961609345658, 0.7311657634689946, null, 0.8089961609345658, 0.9011339078096633, null, 0.8089961609345658, 0.8016111783687677, null, 0.7222846879290787, 0.9528527425842739, null, 0.7222846879290787, 0.690016328140396, null, 0.7222846879290787, 0.5886703168399895, null, 0.01876171413125327, 0.026771817842421997, null, 0.01876171413125327, 0.09186645974288632, null, 0.01876171413125327, 0.10321622277398101, null, 0.01876171413125327, 0.1735506267461867, null, 0.8016111783687677, 0.891868301175821, null, 0.8016111783687677, 0.68128520136847, null, 0.8016111783687677, 0.9532681441921305, null, 0.8016111783687677, 0.7353428557575755, null, 0.8016111783687677, 0.7311657634689946, null, 0.8016111783687677, 0.9011339078096633, null, 0.43196344222361227, 0.3996510641743197, null, 0.43196344222361227, 0.5886703168399895, null, 0.43196344222361227, 0.4666482714834408, null, 0.9011339078096633, 0.891868301175821, null, 0.9011339078096633, 0.68128520136847, null, 0.9011339078096633, 0.9532681441921305, null, 0.24026772497187532, 0.362322730884702, null, 0.24026772497187532, 0.13985272363426526, null, 0.24026772497187532, 0.13022993020357043, null, 0.24026772497187532, 0.21665962402659544, null, 0.24026772497187532, 0.2083567880838434, null, 0.24026772497187532, 0.12631654071213483, null, 0.24026772497187532, 0.1839028760606296, null, 0.24026772497187532, 0.3232711412508066, null, 0.10321622277398101, 0.09186645974288632, null, 0.10321622277398101, 0.026771817842421997, null, 0.10321622277398101, 0.1735506267461867, null, 0.5006237737207431, 0.362322730884702, null, 0.5006237737207431, 0.42704536740474663, null, 0.5006237737207431, 0.6569436279895382, null, 0.5006237737207431, 0.7353428557575755, null, 0.5006237737207431, 0.5488515965193208, null, 0.5006237737207431, 0.3232711412508066, null, 0.1839028760606296, 0.13022993020357043, null, 0.1839028760606296, 0.12631654071213483, null, 0.1839028760606296, 0.13985272363426526, null, 0.5886703168399895, 0.3996510641743197, null, 0.5886703168399895, 0.4666482714834408, null, 0.5886703168399895, 0.690016328140396, null, 0.1735506267461867, 0.026771817842421997, null, 0.1735506267461867, 0.362322730884702, null, 0.1735506267461867, 0.3232711412508066, null, 0.1735506267461867, 0.21665962402659544, null, 0.1735506267461867, 0.2083567880838434, null, 0.1735506267461867, 0.09186645974288632, null, 0.690016328140396, 0.4666482714834408, null, 0.690016328140396, 0.6569436279895382, null, 0.362322730884702, 0.42704536740474663, null, 0.362322730884702, 0.21665962402659544, null, 0.362322730884702, 0.13985272363426526, null, 0.362322730884702, 0.5488515965193208, null, 0.362322730884702, 0.3232711412508066, null, 0.362322730884702, 0.2083567880838434, null, 0.13985272363426526, 0.2083567880838434, null, 0.13985272363426526, 0.13022993020357043, null, 0.13985272363426526, 0.21665962402659544, null, 0.13985272363426526, 0.12631654071213483, null, 0.13985272363426526, 0.3232711412508066, null, 0.891868301175821, 0.9532681441921305, null, 0.026771817842421997, 0.2083567880838434, null, 0.026771817842421997, 0.09186645974288632, null, 0.7353428557575755, 0.8800306496459869, null, 0.7353428557575755, 0.7311657634689946, null, 0.7353428557575755, 0.6569436279895382, null, 0.9768234503830939, 0.9528527425842739, null, 0.9768234503830939, 0.8800306496459869, null, 0.9768234503830939, 0.999395685828547, null, 0.13022993020357043, 0.12631654071213483, null, 0.21665962402659544, 0.12631654071213483, null, 0.21665962402659544, 0.2083567880838434, null, 0.21665962402659544, 0.3232711412508066, null, 0.21665962402659544, 0.42704536740474663, null, 0.2083567880838434, 0.12631654071213483, null, 0.2083567880838434, 0.3232711412508066, null, 0.2083567880838434, 0.42704536740474663, null, 0.12631654071213483, 0.3232711412508066, null, 0.5488515965193208, 0.42704536740474663, null, 0.5488515965193208, 0.68128520136847, null, 0.5488515965193208, 0.7311657634689946, null, 0.5488515965193208, 0.3232711412508066, null, 0.8800306496459869, 0.9528527425842739, null, 0.8800306496459869, 0.6569436279895382, null, 0.8800306496459869, 0.999395685828547, null, 0.4666482714834408, 0.3996510641743197, null, 0.3232711412508066, 0.42704536740474663, null, 0.9528527425842739, 0.999395685828547, null, 0.68128520136847, 0.7311657634689946, null], \"line\": {\"color\": \"#888\", \"width\": 0.5}}, {\"marker\": {\"colorscale\": \"Hot\", \"colorbar\": {\"title\": \"Node Connections\", \"thickness\": 15, \"titleside\": \"right\", \"xanchor\": \"left\"}, \"reversescale\": true, \"line\": {\"width\": 2}, \"size\": 10, \"showscale\": false, \"color\": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]}, \"mode\": \"markers\", \"x\": [0.7801603911549438, 0.5249831588690298, 0.8085335344099086, 0.2599134798656856, 0.7353838928272886, 0.09088671576431506, 0.313999018186756, 0.6824813442515916, 0.20128789391122526, 0.8551947714242674, 0.7581736589784409, 0.25311953895059136, 0.4813859169876731, 0.9112422509614865, 0.04580558670435442, 0.4582523173083307, 0.12939557977525573, 0.607698913404794, 0.719569201584275, 0.8860336256842246, 0.4238357358399233, 0.8252497121120052, 0.47415009287034726, 0.26253385360950576, 0.9363713903322148, 0.6243437191127235, 0.5572917679006295, 0.7482655725962591, 0.6435799740880603, 0.34509802713919313, 0.021423673670808885, 0.640952694324525, 0.17440205342790494, 0.1332965908314021, 0.583993110207876, 0.3073865727705063, 0.740625863119245, 0.3345284735051981, 0.17972981733780147, 0.6315322816286787], \"type\": \"scatter\", \"hoverinfo\": \"text\", \"y\": [0.49474860768712914, 0.14953665513987202, 0.7696330846542071, 0.14485659826020547, 0.8089961609345658, 0.7222846879290787, 0.01876171413125327, 0.8016111783687677, 0.43196344222361227, 0.9011339078096633, 0.24026772497187532, 0.10321622277398101, 0.5006237737207431, 0.1839028760606296, 0.5886703168399895, 0.1735506267461867, 0.690016328140396, 0.362322730884702, 0.13985272363426526, 0.891868301175821, 0.026771817842421997, 0.9532681441921305, 0.7353428557575755, 0.9768234503830939, 0.13022993020357043, 0.21665962402659544, 0.2083567880838434, 0.12631654071213483, 0.5488515965193208, 0.8800306496459869, 0.4666482714834408, 0.3232711412508066, 0.9528527425842739, 0.3996510641743197, 0.42704536740474663, 0.09186645974288632, 0.68128520136847, 0.6569436279895382, 0.999395685828547, 0.7311657634689946], \"text\": [\"Intersection 0\", \"Intersection 1\", \"Intersection 2\", \"Intersection 3\", \"Intersection 4\", \"Intersection 5\", \"Intersection 6\", \"Intersection 7\", \"Intersection 8\", \"Intersection 9\", \"Intersection 10\", \"Intersection 11\", \"Intersection 12\", \"Intersection 13\", \"Intersection 14\", \"Intersection 15\", \"Intersection 16\", \"Intersection 17\", \"Intersection 18\", \"Intersection 19\", \"Intersection 20\", \"Intersection 21\", \"Intersection 22\", \"Intersection 23\", \"Intersection 24\", \"Intersection 25\", \"Intersection 26\", \"Intersection 27\", \"Intersection 28\", \"Intersection 29\", \"Intersection 30\", \"Intersection 31\", \"Intersection 32\", \"Intersection 33\", \"Intersection 34\", \"Intersection 35\", \"Intersection 36\", \"Intersection 37\", \"Intersection 38\", \"Intersection 39\"]}], {\"hovermode\": \"closest\", \"titlefont\": {\"size\": 16}, \"margin\": {\"r\": 5, \"t\": 40, \"l\": 5, \"b\": 20}, \"xaxis\": {\"showgrid\": false, \"zeroline\": false, \"showticklabels\": false}, \"showlegend\": false, \"yaxis\": {\"showgrid\": false, \"zeroline\": false, \"showticklabels\": false}, \"title\": \"<br>Network graph made with Python\"}, {\"showLink\": true, \"linkText\": \"Export to plot.ly\"})});</script>"
      ],
      "text/vnd.plotly.v1+html": [
       "<div id=\"3714f57a-0569-40c3-8dd8-ebf31443a415\" style=\"height: 525px; width: 100%;\" class=\"plotly-graph-div\"></div><script type=\"text/javascript\">require([\"plotly\"], function(Plotly) { window.PLOTLYENV=window.PLOTLYENV || {};window.PLOTLYENV.BASE_URL=\"https://plot.ly\";Plotly.newPlot(\"3714f57a-0569-40c3-8dd8-ebf31443a415\", [{\"mode\": \"lines\", \"x\": [0.7801603911549438, 0.6435799740880603, null, 0.7801603911549438, 0.583993110207876, null, 0.7801603911549438, 0.740625863119245, null, 0.7801603911549438, 0.607698913404794, null, 0.7801603911549438, 0.640952694324525, null, 0.5249831588690298, 0.607698913404794, null, 0.5249831588690298, 0.719569201584275, null, 0.5249831588690298, 0.3073865727705063, null, 0.5249831588690298, 0.4238357358399233, null, 0.5249831588690298, 0.313999018186756, null, 0.5249831588690298, 0.4582523173083307, null, 0.5249831588690298, 0.6243437191127235, null, 0.5249831588690298, 0.5572917679006295, null, 0.5249831588690298, 0.7482655725962591, null, 0.5249831588690298, 0.640952694324525, null, 0.8085335344099086, 0.8860336256842246, null, 0.8085335344099086, 0.740625863119245, null, 0.8085335344099086, 0.8252497121120052, null, 0.8085335344099086, 0.6315322816286787, null, 0.8085335344099086, 0.8551947714242674, null, 0.8085335344099086, 0.6824813442515916, null, 0.8085335344099086, 0.7353838928272886, null, 0.2599134798656856, 0.25311953895059136, null, 0.2599134798656856, 0.3073865727705063, null, 0.2599134798656856, 0.4238357358399233, null, 0.2599134798656856, 0.313999018186756, null, 0.2599134798656856, 0.4582523173083307, null, 0.7353838928272886, 0.8860336256842246, null, 0.7353838928272886, 0.740625863119245, null, 0.7353838928272886, 0.8252497121120052, null, 0.7353838928272886, 0.6315322816286787, null, 0.7353838928272886, 0.8551947714242674, null, 0.7353838928272886, 0.6824813442515916, null, 0.09088671576431506, 0.17440205342790494, null, 0.09088671576431506, 0.12939557977525573, null, 0.09088671576431506, 0.04580558670435442, null, 0.313999018186756, 0.4238357358399233, null, 0.313999018186756, 0.3073865727705063, null, 0.313999018186756, 0.25311953895059136, null, 0.313999018186756, 0.4582523173083307, null, 0.6824813442515916, 0.8860336256842246, null, 0.6824813442515916, 0.740625863119245, null, 0.6824813442515916, 0.8252497121120052, null, 0.6824813442515916, 0.47415009287034726, null, 0.6824813442515916, 0.6315322816286787, null, 0.6824813442515916, 0.8551947714242674, null, 0.20128789391122526, 0.1332965908314021, null, 0.20128789391122526, 0.04580558670435442, null, 0.20128789391122526, 0.021423673670808885, null, 0.8551947714242674, 0.8860336256842246, null, 0.8551947714242674, 0.740625863119245, null, 0.8551947714242674, 0.8252497121120052, null, 0.7581736589784409, 0.607698913404794, null, 0.7581736589784409, 0.719569201584275, null, 0.7581736589784409, 0.9363713903322148, null, 0.7581736589784409, 0.6243437191127235, null, 0.7581736589784409, 0.5572917679006295, null, 0.7581736589784409, 0.7482655725962591, null, 0.7581736589784409, 0.9112422509614865, null, 0.7581736589784409, 0.640952694324525, null, 0.25311953895059136, 0.3073865727705063, null, 0.25311953895059136, 0.4238357358399233, null, 0.25311953895059136, 0.4582523173083307, null, 0.4813859169876731, 0.607698913404794, null, 0.4813859169876731, 0.583993110207876, null, 0.4813859169876731, 0.3345284735051981, null, 0.4813859169876731, 0.47415009287034726, null, 0.4813859169876731, 0.6435799740880603, null, 0.4813859169876731, 0.640952694324525, null, 0.9112422509614865, 0.9363713903322148, null, 0.9112422509614865, 0.7482655725962591, null, 0.9112422509614865, 0.719569201584275, null, 0.04580558670435442, 0.1332965908314021, null, 0.04580558670435442, 0.021423673670808885, null, 0.04580558670435442, 0.12939557977525573, null, 0.4582523173083307, 0.4238357358399233, null, 0.4582523173083307, 0.607698913404794, null, 0.4582523173083307, 0.640952694324525, null, 0.4582523173083307, 0.6243437191127235, null, 0.4582523173083307, 0.5572917679006295, null, 0.4582523173083307, 0.3073865727705063, null, 0.12939557977525573, 0.021423673670808885, null, 0.12939557977525573, 0.3345284735051981, null, 0.607698913404794, 0.583993110207876, null, 0.607698913404794, 0.6243437191127235, null, 0.607698913404794, 0.719569201584275, null, 0.607698913404794, 0.6435799740880603, null, 0.607698913404794, 0.640952694324525, null, 0.607698913404794, 0.5572917679006295, null, 0.719569201584275, 0.5572917679006295, null, 0.719569201584275, 0.9363713903322148, null, 0.719569201584275, 0.6243437191127235, null, 0.719569201584275, 0.7482655725962591, null, 0.719569201584275, 0.640952694324525, null, 0.8860336256842246, 0.8252497121120052, null, 0.4238357358399233, 0.5572917679006295, null, 0.4238357358399233, 0.3073865727705063, null, 0.47415009287034726, 0.34509802713919313, null, 0.47415009287034726, 0.6315322816286787, null, 0.47415009287034726, 0.3345284735051981, null, 0.26253385360950576, 0.17440205342790494, null, 0.26253385360950576, 0.34509802713919313, null, 0.26253385360950576, 0.17972981733780147, null, 0.9363713903322148, 0.7482655725962591, null, 0.6243437191127235, 0.7482655725962591, null, 0.6243437191127235, 0.5572917679006295, null, 0.6243437191127235, 0.640952694324525, null, 0.6243437191127235, 0.583993110207876, null, 0.5572917679006295, 0.7482655725962591, null, 0.5572917679006295, 0.640952694324525, null, 0.5572917679006295, 0.583993110207876, null, 0.7482655725962591, 0.640952694324525, null, 0.6435799740880603, 0.583993110207876, null, 0.6435799740880603, 0.740625863119245, null, 0.6435799740880603, 0.6315322816286787, null, 0.6435799740880603, 0.640952694324525, null, 0.34509802713919313, 0.17440205342790494, null, 0.34509802713919313, 0.3345284735051981, null, 0.34509802713919313, 0.17972981733780147, null, 0.021423673670808885, 0.1332965908314021, null, 0.640952694324525, 0.583993110207876, null, 0.17440205342790494, 0.17972981733780147, null, 0.740625863119245, 0.6315322816286787, null], \"type\": \"scatter\", \"hoverinfo\": \"none\", \"y\": [0.49474860768712914, 0.5488515965193208, null, 0.49474860768712914, 0.42704536740474663, null, 0.49474860768712914, 0.68128520136847, null, 0.49474860768712914, 0.362322730884702, null, 0.49474860768712914, 0.3232711412508066, null, 0.14953665513987202, 0.362322730884702, null, 0.14953665513987202, 0.13985272363426526, null, 0.14953665513987202, 0.09186645974288632, null, 0.14953665513987202, 0.026771817842421997, null, 0.14953665513987202, 0.01876171413125327, null, 0.14953665513987202, 0.1735506267461867, null, 0.14953665513987202, 0.21665962402659544, null, 0.14953665513987202, 0.2083567880838434, null, 0.14953665513987202, 0.12631654071213483, null, 0.14953665513987202, 0.3232711412508066, null, 0.7696330846542071, 0.891868301175821, null, 0.7696330846542071, 0.68128520136847, null, 0.7696330846542071, 0.9532681441921305, null, 0.7696330846542071, 0.7311657634689946, null, 0.7696330846542071, 0.9011339078096633, null, 0.7696330846542071, 0.8016111783687677, null, 0.7696330846542071, 0.8089961609345658, null, 0.14485659826020547, 0.10321622277398101, null, 0.14485659826020547, 0.09186645974288632, null, 0.14485659826020547, 0.026771817842421997, null, 0.14485659826020547, 0.01876171413125327, null, 0.14485659826020547, 0.1735506267461867, null, 0.8089961609345658, 0.891868301175821, null, 0.8089961609345658, 0.68128520136847, null, 0.8089961609345658, 0.9532681441921305, null, 0.8089961609345658, 0.7311657634689946, null, 0.8089961609345658, 0.9011339078096633, null, 0.8089961609345658, 0.8016111783687677, null, 0.7222846879290787, 0.9528527425842739, null, 0.7222846879290787, 0.690016328140396, null, 0.7222846879290787, 0.5886703168399895, null, 0.01876171413125327, 0.026771817842421997, null, 0.01876171413125327, 0.09186645974288632, null, 0.01876171413125327, 0.10321622277398101, null, 0.01876171413125327, 0.1735506267461867, null, 0.8016111783687677, 0.891868301175821, null, 0.8016111783687677, 0.68128520136847, null, 0.8016111783687677, 0.9532681441921305, null, 0.8016111783687677, 0.7353428557575755, null, 0.8016111783687677, 0.7311657634689946, null, 0.8016111783687677, 0.9011339078096633, null, 0.43196344222361227, 0.3996510641743197, null, 0.43196344222361227, 0.5886703168399895, null, 0.43196344222361227, 0.4666482714834408, null, 0.9011339078096633, 0.891868301175821, null, 0.9011339078096633, 0.68128520136847, null, 0.9011339078096633, 0.9532681441921305, null, 0.24026772497187532, 0.362322730884702, null, 0.24026772497187532, 0.13985272363426526, null, 0.24026772497187532, 0.13022993020357043, null, 0.24026772497187532, 0.21665962402659544, null, 0.24026772497187532, 0.2083567880838434, null, 0.24026772497187532, 0.12631654071213483, null, 0.24026772497187532, 0.1839028760606296, null, 0.24026772497187532, 0.3232711412508066, null, 0.10321622277398101, 0.09186645974288632, null, 0.10321622277398101, 0.026771817842421997, null, 0.10321622277398101, 0.1735506267461867, null, 0.5006237737207431, 0.362322730884702, null, 0.5006237737207431, 0.42704536740474663, null, 0.5006237737207431, 0.6569436279895382, null, 0.5006237737207431, 0.7353428557575755, null, 0.5006237737207431, 0.5488515965193208, null, 0.5006237737207431, 0.3232711412508066, null, 0.1839028760606296, 0.13022993020357043, null, 0.1839028760606296, 0.12631654071213483, null, 0.1839028760606296, 0.13985272363426526, null, 0.5886703168399895, 0.3996510641743197, null, 0.5886703168399895, 0.4666482714834408, null, 0.5886703168399895, 0.690016328140396, null, 0.1735506267461867, 0.026771817842421997, null, 0.1735506267461867, 0.362322730884702, null, 0.1735506267461867, 0.3232711412508066, null, 0.1735506267461867, 0.21665962402659544, null, 0.1735506267461867, 0.2083567880838434, null, 0.1735506267461867, 0.09186645974288632, null, 0.690016328140396, 0.4666482714834408, null, 0.690016328140396, 0.6569436279895382, null, 0.362322730884702, 0.42704536740474663, null, 0.362322730884702, 0.21665962402659544, null, 0.362322730884702, 0.13985272363426526, null, 0.362322730884702, 0.5488515965193208, null, 0.362322730884702, 0.3232711412508066, null, 0.362322730884702, 0.2083567880838434, null, 0.13985272363426526, 0.2083567880838434, null, 0.13985272363426526, 0.13022993020357043, null, 0.13985272363426526, 0.21665962402659544, null, 0.13985272363426526, 0.12631654071213483, null, 0.13985272363426526, 0.3232711412508066, null, 0.891868301175821, 0.9532681441921305, null, 0.026771817842421997, 0.2083567880838434, null, 0.026771817842421997, 0.09186645974288632, null, 0.7353428557575755, 0.8800306496459869, null, 0.7353428557575755, 0.7311657634689946, null, 0.7353428557575755, 0.6569436279895382, null, 0.9768234503830939, 0.9528527425842739, null, 0.9768234503830939, 0.8800306496459869, null, 0.9768234503830939, 0.999395685828547, null, 0.13022993020357043, 0.12631654071213483, null, 0.21665962402659544, 0.12631654071213483, null, 0.21665962402659544, 0.2083567880838434, null, 0.21665962402659544, 0.3232711412508066, null, 0.21665962402659544, 0.42704536740474663, null, 0.2083567880838434, 0.12631654071213483, null, 0.2083567880838434, 0.3232711412508066, null, 0.2083567880838434, 0.42704536740474663, null, 0.12631654071213483, 0.3232711412508066, null, 0.5488515965193208, 0.42704536740474663, null, 0.5488515965193208, 0.68128520136847, null, 0.5488515965193208, 0.7311657634689946, null, 0.5488515965193208, 0.3232711412508066, null, 0.8800306496459869, 0.9528527425842739, null, 0.8800306496459869, 0.6569436279895382, null, 0.8800306496459869, 0.999395685828547, null, 0.4666482714834408, 0.3996510641743197, null, 0.3232711412508066, 0.42704536740474663, null, 0.9528527425842739, 0.999395685828547, null, 0.68128520136847, 0.7311657634689946, null], \"line\": {\"color\": \"#888\", \"width\": 0.5}}, {\"marker\": {\"colorscale\": \"Hot\", \"colorbar\": {\"title\": \"Node Connections\", \"thickness\": 15, \"titleside\": \"right\", \"xanchor\": \"left\"}, \"reversescale\": true, \"line\": {\"width\": 2}, \"size\": 10, \"showscale\": false, \"color\": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]}, \"mode\": \"markers\", \"x\": [0.7801603911549438, 0.5249831588690298, 0.8085335344099086, 0.2599134798656856, 0.7353838928272886, 0.09088671576431506, 0.313999018186756, 0.6824813442515916, 0.20128789391122526, 0.8551947714242674, 0.7581736589784409, 0.25311953895059136, 0.4813859169876731, 0.9112422509614865, 0.04580558670435442, 0.4582523173083307, 0.12939557977525573, 0.607698913404794, 0.719569201584275, 0.8860336256842246, 0.4238357358399233, 0.8252497121120052, 0.47415009287034726, 0.26253385360950576, 0.9363713903322148, 0.6243437191127235, 0.5572917679006295, 0.7482655725962591, 0.6435799740880603, 0.34509802713919313, 0.021423673670808885, 0.640952694324525, 0.17440205342790494, 0.1332965908314021, 0.583993110207876, 0.3073865727705063, 0.740625863119245, 0.3345284735051981, 0.17972981733780147, 0.6315322816286787], \"type\": \"scatter\", \"hoverinfo\": \"text\", \"y\": [0.49474860768712914, 0.14953665513987202, 0.7696330846542071, 0.14485659826020547, 0.8089961609345658, 0.7222846879290787, 0.01876171413125327, 0.8016111783687677, 0.43196344222361227, 0.9011339078096633, 0.24026772497187532, 0.10321622277398101, 0.5006237737207431, 0.1839028760606296, 0.5886703168399895, 0.1735506267461867, 0.690016328140396, 0.362322730884702, 0.13985272363426526, 0.891868301175821, 0.026771817842421997, 0.9532681441921305, 0.7353428557575755, 0.9768234503830939, 0.13022993020357043, 0.21665962402659544, 0.2083567880838434, 0.12631654071213483, 0.5488515965193208, 0.8800306496459869, 0.4666482714834408, 0.3232711412508066, 0.9528527425842739, 0.3996510641743197, 0.42704536740474663, 0.09186645974288632, 0.68128520136847, 0.6569436279895382, 0.999395685828547, 0.7311657634689946], \"text\": [\"Intersection 0\", \"Intersection 1\", \"Intersection 2\", \"Intersection 3\", \"Intersection 4\", \"Intersection 5\", \"Intersection 6\", \"Intersection 7\", \"Intersection 8\", \"Intersection 9\", \"Intersection 10\", \"Intersection 11\", \"Intersection 12\", \"Intersection 13\", \"Intersection 14\", \"Intersection 15\", \"Intersection 16\", \"Intersection 17\", \"Intersection 18\", \"Intersection 19\", \"Intersection 20\", \"Intersection 21\", \"Intersection 22\", \"Intersection 23\", \"Intersection 24\", \"Intersection 25\", \"Intersection 26\", \"Intersection 27\", \"Intersection 28\", \"Intersection 29\", \"Intersection 30\", \"Intersection 31\", \"Intersection 32\", \"Intersection 33\", \"Intersection 34\", \"Intersection 35\", \"Intersection 36\", \"Intersection 37\", \"Intersection 38\", \"Intersection 39\"]}], {\"hovermode\": \"closest\", \"titlefont\": {\"size\": 16}, \"margin\": {\"r\": 5, \"t\": 40, \"l\": 5, \"b\": 20}, \"xaxis\": {\"showgrid\": false, \"zeroline\": false, \"showticklabels\": false}, \"showlegend\": false, \"yaxis\": {\"showgrid\": false, \"zeroline\": false, \"showticklabels\": false}, \"title\": \"<br>Network graph made with Python\"}, {\"showLink\": true, \"linkText\": \"Export to plot.ly\"})});</script>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "## Let's do the bigger one..\n",
    "\n",
    "map_40 = load_map_40()\n",
    "show_map(map_40)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "---\n",
    "# 1. Intersections(Nodes)\n",
    "\n",
    "The `intersections` are represented as a dictionary. \n",
    "\n",
    "In this example, there are 40 intersections, each identified by an x,y coordinate. The coordinates are listed below. You can hover over each dot in the map above to see the intersection number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "map_40.intersections # nodesssss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "map_40.intersections[5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "map_40.intersections[34]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "# 2. Roads(expanding paths)\n",
    "\n",
    "The `roads` property is a list where `roads[i]` contains a list of the intersections that intersection `i` connects to."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "len(map_40.roads)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "map_40.roads[5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "map_40.roads[34]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "# 3. Visualizations\n",
    "\n",
    "The map above shows a network of roads which spans 40 different intersections (labeled 0 through 39). \n",
    "\n",
    "The `show_map()` function which generated this map also takes a few optional parameters which might be useful for visualizaing the output of the search algorithm you will write.\n",
    "\n",
    "* `start` - The \"start\" node for the search algorithm.\n",
    "* `goal`  - The \"goal\" node.\n",
    "* `path`  - An array of integers which corresponds to a valid sequence of intersection visits on the map."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "application/vnd.plotly.v1+json": {
       "data": [
        {
         "hoverinfo": "none",
         "line": {
          "color": "#888",
          "width": 0.5
         },
         "mode": "lines",
         "type": "scatter",
         "x": [
          0.7801603911549438,
          0.6435799740880603,
          null,
          0.7801603911549438,
          0.583993110207876,
          null,
          0.7801603911549438,
          0.740625863119245,
          null,
          0.7801603911549438,
          0.607698913404794,
          null,
          0.7801603911549438,
          0.640952694324525,
          null,
          0.5249831588690298,
          0.607698913404794,
          null,
          0.5249831588690298,
          0.719569201584275,
          null,
          0.5249831588690298,
          0.3073865727705063,
          null,
          0.5249831588690298,
          0.4238357358399233,
          null,
          0.5249831588690298,
          0.313999018186756,
          null,
          0.5249831588690298,
          0.4582523173083307,
          null,
          0.5249831588690298,
          0.6243437191127235,
          null,
          0.5249831588690298,
          0.5572917679006295,
          null,
          0.5249831588690298,
          0.7482655725962591,
          null,
          0.5249831588690298,
          0.640952694324525,
          null,
          0.8085335344099086,
          0.8860336256842246,
          null,
          0.8085335344099086,
          0.740625863119245,
          null,
          0.8085335344099086,
          0.8252497121120052,
          null,
          0.8085335344099086,
          0.6315322816286787,
          null,
          0.8085335344099086,
          0.8551947714242674,
          null,
          0.8085335344099086,
          0.6824813442515916,
          null,
          0.8085335344099086,
          0.7353838928272886,
          null,
          0.2599134798656856,
          0.25311953895059136,
          null,
          0.2599134798656856,
          0.3073865727705063,
          null,
          0.2599134798656856,
          0.4238357358399233,
          null,
          0.2599134798656856,
          0.313999018186756,
          null,
          0.2599134798656856,
          0.4582523173083307,
          null,
          0.7353838928272886,
          0.8860336256842246,
          null,
          0.7353838928272886,
          0.740625863119245,
          null,
          0.7353838928272886,
          0.8252497121120052,
          null,
          0.7353838928272886,
          0.6315322816286787,
          null,
          0.7353838928272886,
          0.8551947714242674,
          null,
          0.7353838928272886,
          0.6824813442515916,
          null,
          0.09088671576431506,
          0.17440205342790494,
          null,
          0.09088671576431506,
          0.12939557977525573,
          null,
          0.09088671576431506,
          0.04580558670435442,
          null,
          0.313999018186756,
          0.4238357358399233,
          null,
          0.313999018186756,
          0.3073865727705063,
          null,
          0.313999018186756,
          0.25311953895059136,
          null,
          0.313999018186756,
          0.4582523173083307,
          null,
          0.6824813442515916,
          0.8860336256842246,
          null,
          0.6824813442515916,
          0.740625863119245,
          null,
          0.6824813442515916,
          0.8252497121120052,
          null,
          0.6824813442515916,
          0.47415009287034726,
          null,
          0.6824813442515916,
          0.6315322816286787,
          null,
          0.6824813442515916,
          0.8551947714242674,
          null,
          0.20128789391122526,
          0.1332965908314021,
          null,
          0.20128789391122526,
          0.04580558670435442,
          null,
          0.20128789391122526,
          0.021423673670808885,
          null,
          0.8551947714242674,
          0.8860336256842246,
          null,
          0.8551947714242674,
          0.740625863119245,
          null,
          0.8551947714242674,
          0.8252497121120052,
          null,
          0.7581736589784409,
          0.607698913404794,
          null,
          0.7581736589784409,
          0.719569201584275,
          null,
          0.7581736589784409,
          0.9363713903322148,
          null,
          0.7581736589784409,
          0.6243437191127235,
          null,
          0.7581736589784409,
          0.5572917679006295,
          null,
          0.7581736589784409,
          0.7482655725962591,
          null,
          0.7581736589784409,
          0.9112422509614865,
          null,
          0.7581736589784409,
          0.640952694324525,
          null,
          0.25311953895059136,
          0.3073865727705063,
          null,
          0.25311953895059136,
          0.4238357358399233,
          null,
          0.25311953895059136,
          0.4582523173083307,
          null,
          0.4813859169876731,
          0.607698913404794,
          null,
          0.4813859169876731,
          0.583993110207876,
          null,
          0.4813859169876731,
          0.3345284735051981,
          null,
          0.4813859169876731,
          0.47415009287034726,
          null,
          0.4813859169876731,
          0.6435799740880603,
          null,
          0.4813859169876731,
          0.640952694324525,
          null,
          0.9112422509614865,
          0.9363713903322148,
          null,
          0.9112422509614865,
          0.7482655725962591,
          null,
          0.9112422509614865,
          0.719569201584275,
          null,
          0.04580558670435442,
          0.1332965908314021,
          null,
          0.04580558670435442,
          0.021423673670808885,
          null,
          0.04580558670435442,
          0.12939557977525573,
          null,
          0.4582523173083307,
          0.4238357358399233,
          null,
          0.4582523173083307,
          0.607698913404794,
          null,
          0.4582523173083307,
          0.640952694324525,
          null,
          0.4582523173083307,
          0.6243437191127235,
          null,
          0.4582523173083307,
          0.5572917679006295,
          null,
          0.4582523173083307,
          0.3073865727705063,
          null,
          0.12939557977525573,
          0.021423673670808885,
          null,
          0.12939557977525573,
          0.3345284735051981,
          null,
          0.607698913404794,
          0.583993110207876,
          null,
          0.607698913404794,
          0.6243437191127235,
          null,
          0.607698913404794,
          0.719569201584275,
          null,
          0.607698913404794,
          0.6435799740880603,
          null,
          0.607698913404794,
          0.640952694324525,
          null,
          0.607698913404794,
          0.5572917679006295,
          null,
          0.719569201584275,
          0.5572917679006295,
          null,
          0.719569201584275,
          0.9363713903322148,
          null,
          0.719569201584275,
          0.6243437191127235,
          null,
          0.719569201584275,
          0.7482655725962591,
          null,
          0.719569201584275,
          0.640952694324525,
          null,
          0.8860336256842246,
          0.8252497121120052,
          null,
          0.4238357358399233,
          0.5572917679006295,
          null,
          0.4238357358399233,
          0.3073865727705063,
          null,
          0.47415009287034726,
          0.34509802713919313,
          null,
          0.47415009287034726,
          0.6315322816286787,
          null,
          0.47415009287034726,
          0.3345284735051981,
          null,
          0.26253385360950576,
          0.17440205342790494,
          null,
          0.26253385360950576,
          0.34509802713919313,
          null,
          0.26253385360950576,
          0.17972981733780147,
          null,
          0.9363713903322148,
          0.7482655725962591,
          null,
          0.6243437191127235,
          0.7482655725962591,
          null,
          0.6243437191127235,
          0.5572917679006295,
          null,
          0.6243437191127235,
          0.640952694324525,
          null,
          0.6243437191127235,
          0.583993110207876,
          null,
          0.5572917679006295,
          0.7482655725962591,
          null,
          0.5572917679006295,
          0.640952694324525,
          null,
          0.5572917679006295,
          0.583993110207876,
          null,
          0.7482655725962591,
          0.640952694324525,
          null,
          0.6435799740880603,
          0.583993110207876,
          null,
          0.6435799740880603,
          0.740625863119245,
          null,
          0.6435799740880603,
          0.6315322816286787,
          null,
          0.6435799740880603,
          0.640952694324525,
          null,
          0.34509802713919313,
          0.17440205342790494,
          null,
          0.34509802713919313,
          0.3345284735051981,
          null,
          0.34509802713919313,
          0.17972981733780147,
          null,
          0.021423673670808885,
          0.1332965908314021,
          null,
          0.640952694324525,
          0.583993110207876,
          null,
          0.17440205342790494,
          0.17972981733780147,
          null,
          0.740625863119245,
          0.6315322816286787,
          null
         ],
         "y": [
          0.49474860768712914,
          0.5488515965193208,
          null,
          0.49474860768712914,
          0.42704536740474663,
          null,
          0.49474860768712914,
          0.68128520136847,
          null,
          0.49474860768712914,
          0.362322730884702,
          null,
          0.49474860768712914,
          0.3232711412508066,
          null,
          0.14953665513987202,
          0.362322730884702,
          null,
          0.14953665513987202,
          0.13985272363426526,
          null,
          0.14953665513987202,
          0.09186645974288632,
          null,
          0.14953665513987202,
          0.026771817842421997,
          null,
          0.14953665513987202,
          0.01876171413125327,
          null,
          0.14953665513987202,
          0.1735506267461867,
          null,
          0.14953665513987202,
          0.21665962402659544,
          null,
          0.14953665513987202,
          0.2083567880838434,
          null,
          0.14953665513987202,
          0.12631654071213483,
          null,
          0.14953665513987202,
          0.3232711412508066,
          null,
          0.7696330846542071,
          0.891868301175821,
          null,
          0.7696330846542071,
          0.68128520136847,
          null,
          0.7696330846542071,
          0.9532681441921305,
          null,
          0.7696330846542071,
          0.7311657634689946,
          null,
          0.7696330846542071,
          0.9011339078096633,
          null,
          0.7696330846542071,
          0.8016111783687677,
          null,
          0.7696330846542071,
          0.8089961609345658,
          null,
          0.14485659826020547,
          0.10321622277398101,
          null,
          0.14485659826020547,
          0.09186645974288632,
          null,
          0.14485659826020547,
          0.026771817842421997,
          null,
          0.14485659826020547,
          0.01876171413125327,
          null,
          0.14485659826020547,
          0.1735506267461867,
          null,
          0.8089961609345658,
          0.891868301175821,
          null,
          0.8089961609345658,
          0.68128520136847,
          null,
          0.8089961609345658,
          0.9532681441921305,
          null,
          0.8089961609345658,
          0.7311657634689946,
          null,
          0.8089961609345658,
          0.9011339078096633,
          null,
          0.8089961609345658,
          0.8016111783687677,
          null,
          0.7222846879290787,
          0.9528527425842739,
          null,
          0.7222846879290787,
          0.690016328140396,
          null,
          0.7222846879290787,
          0.5886703168399895,
          null,
          0.01876171413125327,
          0.026771817842421997,
          null,
          0.01876171413125327,
          0.09186645974288632,
          null,
          0.01876171413125327,
          0.10321622277398101,
          null,
          0.01876171413125327,
          0.1735506267461867,
          null,
          0.8016111783687677,
          0.891868301175821,
          null,
          0.8016111783687677,
          0.68128520136847,
          null,
          0.8016111783687677,
          0.9532681441921305,
          null,
          0.8016111783687677,
          0.7353428557575755,
          null,
          0.8016111783687677,
          0.7311657634689946,
          null,
          0.8016111783687677,
          0.9011339078096633,
          null,
          0.43196344222361227,
          0.3996510641743197,
          null,
          0.43196344222361227,
          0.5886703168399895,
          null,
          0.43196344222361227,
          0.4666482714834408,
          null,
          0.9011339078096633,
          0.891868301175821,
          null,
          0.9011339078096633,
          0.68128520136847,
          null,
          0.9011339078096633,
          0.9532681441921305,
          null,
          0.24026772497187532,
          0.362322730884702,
          null,
          0.24026772497187532,
          0.13985272363426526,
          null,
          0.24026772497187532,
          0.13022993020357043,
          null,
          0.24026772497187532,
          0.21665962402659544,
          null,
          0.24026772497187532,
          0.2083567880838434,
          null,
          0.24026772497187532,
          0.12631654071213483,
          null,
          0.24026772497187532,
          0.1839028760606296,
          null,
          0.24026772497187532,
          0.3232711412508066,
          null,
          0.10321622277398101,
          0.09186645974288632,
          null,
          0.10321622277398101,
          0.026771817842421997,
          null,
          0.10321622277398101,
          0.1735506267461867,
          null,
          0.5006237737207431,
          0.362322730884702,
          null,
          0.5006237737207431,
          0.42704536740474663,
          null,
          0.5006237737207431,
          0.6569436279895382,
          null,
          0.5006237737207431,
          0.7353428557575755,
          null,
          0.5006237737207431,
          0.5488515965193208,
          null,
          0.5006237737207431,
          0.3232711412508066,
          null,
          0.1839028760606296,
          0.13022993020357043,
          null,
          0.1839028760606296,
          0.12631654071213483,
          null,
          0.1839028760606296,
          0.13985272363426526,
          null,
          0.5886703168399895,
          0.3996510641743197,
          null,
          0.5886703168399895,
          0.4666482714834408,
          null,
          0.5886703168399895,
          0.690016328140396,
          null,
          0.1735506267461867,
          0.026771817842421997,
          null,
          0.1735506267461867,
          0.362322730884702,
          null,
          0.1735506267461867,
          0.3232711412508066,
          null,
          0.1735506267461867,
          0.21665962402659544,
          null,
          0.1735506267461867,
          0.2083567880838434,
          null,
          0.1735506267461867,
          0.09186645974288632,
          null,
          0.690016328140396,
          0.4666482714834408,
          null,
          0.690016328140396,
          0.6569436279895382,
          null,
          0.362322730884702,
          0.42704536740474663,
          null,
          0.362322730884702,
          0.21665962402659544,
          null,
          0.362322730884702,
          0.13985272363426526,
          null,
          0.362322730884702,
          0.5488515965193208,
          null,
          0.362322730884702,
          0.3232711412508066,
          null,
          0.362322730884702,
          0.2083567880838434,
          null,
          0.13985272363426526,
          0.2083567880838434,
          null,
          0.13985272363426526,
          0.13022993020357043,
          null,
          0.13985272363426526,
          0.21665962402659544,
          null,
          0.13985272363426526,
          0.12631654071213483,
          null,
          0.13985272363426526,
          0.3232711412508066,
          null,
          0.891868301175821,
          0.9532681441921305,
          null,
          0.026771817842421997,
          0.2083567880838434,
          null,
          0.026771817842421997,
          0.09186645974288632,
          null,
          0.7353428557575755,
          0.8800306496459869,
          null,
          0.7353428557575755,
          0.7311657634689946,
          null,
          0.7353428557575755,
          0.6569436279895382,
          null,
          0.9768234503830939,
          0.9528527425842739,
          null,
          0.9768234503830939,
          0.8800306496459869,
          null,
          0.9768234503830939,
          0.999395685828547,
          null,
          0.13022993020357043,
          0.12631654071213483,
          null,
          0.21665962402659544,
          0.12631654071213483,
          null,
          0.21665962402659544,
          0.2083567880838434,
          null,
          0.21665962402659544,
          0.3232711412508066,
          null,
          0.21665962402659544,
          0.42704536740474663,
          null,
          0.2083567880838434,
          0.12631654071213483,
          null,
          0.2083567880838434,
          0.3232711412508066,
          null,
          0.2083567880838434,
          0.42704536740474663,
          null,
          0.12631654071213483,
          0.3232711412508066,
          null,
          0.5488515965193208,
          0.42704536740474663,
          null,
          0.5488515965193208,
          0.68128520136847,
          null,
          0.5488515965193208,
          0.7311657634689946,
          null,
          0.5488515965193208,
          0.3232711412508066,
          null,
          0.8800306496459869,
          0.9528527425842739,
          null,
          0.8800306496459869,
          0.6569436279895382,
          null,
          0.8800306496459869,
          0.999395685828547,
          null,
          0.4666482714834408,
          0.3996510641743197,
          null,
          0.3232711412508066,
          0.42704536740474663,
          null,
          0.9528527425842739,
          0.999395685828547,
          null,
          0.68128520136847,
          0.7311657634689946,
          null
         ]
        },
        {
         "hoverinfo": "text",
         "marker": {
          "color": [
           0,
           0,
           0,
           0,
           0,
           3,
           0,
           0,
           0,
           0,
           0,
           0,
           2,
           0,
           0,
           0,
           2,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           1,
           0,
           0,
           2,
           0,
           0
          ],
          "colorbar": {
           "thickness": 15,
           "title": "Node Connections",
           "titleside": "right",
           "xanchor": "left"
          },
          "colorscale": "Hot",
          "line": {
           "width": 2
          },
          "reversescale": true,
          "showscale": false,
          "size": 10
         },
         "mode": "markers",
         "text": [
          "Intersection 0",
          "Intersection 1",
          "Intersection 2",
          "Intersection 3",
          "Intersection 4",
          "Intersection 5",
          "Intersection 6",
          "Intersection 7",
          "Intersection 8",
          "Intersection 9",
          "Intersection 10",
          "Intersection 11",
          "Intersection 12",
          "Intersection 13",
          "Intersection 14",
          "Intersection 15",
          "Intersection 16",
          "Intersection 17",
          "Intersection 18",
          "Intersection 19",
          "Intersection 20",
          "Intersection 21",
          "Intersection 22",
          "Intersection 23",
          "Intersection 24",
          "Intersection 25",
          "Intersection 26",
          "Intersection 27",
          "Intersection 28",
          "Intersection 29",
          "Intersection 30",
          "Intersection 31",
          "Intersection 32",
          "Intersection 33",
          "Intersection 34",
          "Intersection 35",
          "Intersection 36",
          "Intersection 37",
          "Intersection 38",
          "Intersection 39"
         ],
         "type": "scatter",
         "x": [
          0.7801603911549438,
          0.5249831588690298,
          0.8085335344099086,
          0.2599134798656856,
          0.7353838928272886,
          0.09088671576431506,
          0.313999018186756,
          0.6824813442515916,
          0.20128789391122526,
          0.8551947714242674,
          0.7581736589784409,
          0.25311953895059136,
          0.4813859169876731,
          0.9112422509614865,
          0.04580558670435442,
          0.4582523173083307,
          0.12939557977525573,
          0.607698913404794,
          0.719569201584275,
          0.8860336256842246,
          0.4238357358399233,
          0.8252497121120052,
          0.47415009287034726,
          0.26253385360950576,
          0.9363713903322148,
          0.6243437191127235,
          0.5572917679006295,
          0.7482655725962591,
          0.6435799740880603,
          0.34509802713919313,
          0.021423673670808885,
          0.640952694324525,
          0.17440205342790494,
          0.1332965908314021,
          0.583993110207876,
          0.3073865727705063,
          0.740625863119245,
          0.3345284735051981,
          0.17972981733780147,
          0.6315322816286787
         ],
         "y": [
          0.49474860768712914,
          0.14953665513987202,
          0.7696330846542071,
          0.14485659826020547,
          0.8089961609345658,
          0.7222846879290787,
          0.01876171413125327,
          0.8016111783687677,
          0.43196344222361227,
          0.9011339078096633,
          0.24026772497187532,
          0.10321622277398101,
          0.5006237737207431,
          0.1839028760606296,
          0.5886703168399895,
          0.1735506267461867,
          0.690016328140396,
          0.362322730884702,
          0.13985272363426526,
          0.891868301175821,
          0.026771817842421997,
          0.9532681441921305,
          0.7353428557575755,
          0.9768234503830939,
          0.13022993020357043,
          0.21665962402659544,
          0.2083567880838434,
          0.12631654071213483,
          0.5488515965193208,
          0.8800306496459869,
          0.4666482714834408,
          0.3232711412508066,
          0.9528527425842739,
          0.3996510641743197,
          0.42704536740474663,
          0.09186645974288632,
          0.68128520136847,
          0.6569436279895382,
          0.999395685828547,
          0.7311657634689946
         ]
        }
       ],
       "layout": {
        "hovermode": "closest",
        "margin": {
         "b": 20,
         "l": 5,
         "r": 5,
         "t": 40
        },
        "showlegend": false,
        "title": "<br>Network graph made with Python",
        "titlefont": {
         "size": 16
        },
        "xaxis": {
         "showgrid": false,
         "showticklabels": false,
         "zeroline": false
        },
        "yaxis": {
         "showgrid": false,
         "showticklabels": false,
         "zeroline": false
        }
       }
      },
      "text/html": [
       "<div id=\"92e89391-e00d-4669-b607-0e2ad0eaf968\" style=\"height: 525px; width: 100%;\" class=\"plotly-graph-div\"></div><script type=\"text/javascript\">require([\"plotly\"], function(Plotly) { window.PLOTLYENV=window.PLOTLYENV || {};window.PLOTLYENV.BASE_URL=\"https://plot.ly\";Plotly.newPlot(\"92e89391-e00d-4669-b607-0e2ad0eaf968\", [{\"mode\": \"lines\", \"x\": [0.7801603911549438, 0.6435799740880603, null, 0.7801603911549438, 0.583993110207876, null, 0.7801603911549438, 0.740625863119245, null, 0.7801603911549438, 0.607698913404794, null, 0.7801603911549438, 0.640952694324525, null, 0.5249831588690298, 0.607698913404794, null, 0.5249831588690298, 0.719569201584275, null, 0.5249831588690298, 0.3073865727705063, null, 0.5249831588690298, 0.4238357358399233, null, 0.5249831588690298, 0.313999018186756, null, 0.5249831588690298, 0.4582523173083307, null, 0.5249831588690298, 0.6243437191127235, null, 0.5249831588690298, 0.5572917679006295, null, 0.5249831588690298, 0.7482655725962591, null, 0.5249831588690298, 0.640952694324525, null, 0.8085335344099086, 0.8860336256842246, null, 0.8085335344099086, 0.740625863119245, null, 0.8085335344099086, 0.8252497121120052, null, 0.8085335344099086, 0.6315322816286787, null, 0.8085335344099086, 0.8551947714242674, null, 0.8085335344099086, 0.6824813442515916, null, 0.8085335344099086, 0.7353838928272886, null, 0.2599134798656856, 0.25311953895059136, null, 0.2599134798656856, 0.3073865727705063, null, 0.2599134798656856, 0.4238357358399233, null, 0.2599134798656856, 0.313999018186756, null, 0.2599134798656856, 0.4582523173083307, null, 0.7353838928272886, 0.8860336256842246, null, 0.7353838928272886, 0.740625863119245, null, 0.7353838928272886, 0.8252497121120052, null, 0.7353838928272886, 0.6315322816286787, null, 0.7353838928272886, 0.8551947714242674, null, 0.7353838928272886, 0.6824813442515916, null, 0.09088671576431506, 0.17440205342790494, null, 0.09088671576431506, 0.12939557977525573, null, 0.09088671576431506, 0.04580558670435442, null, 0.313999018186756, 0.4238357358399233, null, 0.313999018186756, 0.3073865727705063, null, 0.313999018186756, 0.25311953895059136, null, 0.313999018186756, 0.4582523173083307, null, 0.6824813442515916, 0.8860336256842246, null, 0.6824813442515916, 0.740625863119245, null, 0.6824813442515916, 0.8252497121120052, null, 0.6824813442515916, 0.47415009287034726, null, 0.6824813442515916, 0.6315322816286787, null, 0.6824813442515916, 0.8551947714242674, null, 0.20128789391122526, 0.1332965908314021, null, 0.20128789391122526, 0.04580558670435442, null, 0.20128789391122526, 0.021423673670808885, null, 0.8551947714242674, 0.8860336256842246, null, 0.8551947714242674, 0.740625863119245, null, 0.8551947714242674, 0.8252497121120052, null, 0.7581736589784409, 0.607698913404794, null, 0.7581736589784409, 0.719569201584275, null, 0.7581736589784409, 0.9363713903322148, null, 0.7581736589784409, 0.6243437191127235, null, 0.7581736589784409, 0.5572917679006295, null, 0.7581736589784409, 0.7482655725962591, null, 0.7581736589784409, 0.9112422509614865, null, 0.7581736589784409, 0.640952694324525, null, 0.25311953895059136, 0.3073865727705063, null, 0.25311953895059136, 0.4238357358399233, null, 0.25311953895059136, 0.4582523173083307, null, 0.4813859169876731, 0.607698913404794, null, 0.4813859169876731, 0.583993110207876, null, 0.4813859169876731, 0.3345284735051981, null, 0.4813859169876731, 0.47415009287034726, null, 0.4813859169876731, 0.6435799740880603, null, 0.4813859169876731, 0.640952694324525, null, 0.9112422509614865, 0.9363713903322148, null, 0.9112422509614865, 0.7482655725962591, null, 0.9112422509614865, 0.719569201584275, null, 0.04580558670435442, 0.1332965908314021, null, 0.04580558670435442, 0.021423673670808885, null, 0.04580558670435442, 0.12939557977525573, null, 0.4582523173083307, 0.4238357358399233, null, 0.4582523173083307, 0.607698913404794, null, 0.4582523173083307, 0.640952694324525, null, 0.4582523173083307, 0.6243437191127235, null, 0.4582523173083307, 0.5572917679006295, null, 0.4582523173083307, 0.3073865727705063, null, 0.12939557977525573, 0.021423673670808885, null, 0.12939557977525573, 0.3345284735051981, null, 0.607698913404794, 0.583993110207876, null, 0.607698913404794, 0.6243437191127235, null, 0.607698913404794, 0.719569201584275, null, 0.607698913404794, 0.6435799740880603, null, 0.607698913404794, 0.640952694324525, null, 0.607698913404794, 0.5572917679006295, null, 0.719569201584275, 0.5572917679006295, null, 0.719569201584275, 0.9363713903322148, null, 0.719569201584275, 0.6243437191127235, null, 0.719569201584275, 0.7482655725962591, null, 0.719569201584275, 0.640952694324525, null, 0.8860336256842246, 0.8252497121120052, null, 0.4238357358399233, 0.5572917679006295, null, 0.4238357358399233, 0.3073865727705063, null, 0.47415009287034726, 0.34509802713919313, null, 0.47415009287034726, 0.6315322816286787, null, 0.47415009287034726, 0.3345284735051981, null, 0.26253385360950576, 0.17440205342790494, null, 0.26253385360950576, 0.34509802713919313, null, 0.26253385360950576, 0.17972981733780147, null, 0.9363713903322148, 0.7482655725962591, null, 0.6243437191127235, 0.7482655725962591, null, 0.6243437191127235, 0.5572917679006295, null, 0.6243437191127235, 0.640952694324525, null, 0.6243437191127235, 0.583993110207876, null, 0.5572917679006295, 0.7482655725962591, null, 0.5572917679006295, 0.640952694324525, null, 0.5572917679006295, 0.583993110207876, null, 0.7482655725962591, 0.640952694324525, null, 0.6435799740880603, 0.583993110207876, null, 0.6435799740880603, 0.740625863119245, null, 0.6435799740880603, 0.6315322816286787, null, 0.6435799740880603, 0.640952694324525, null, 0.34509802713919313, 0.17440205342790494, null, 0.34509802713919313, 0.3345284735051981, null, 0.34509802713919313, 0.17972981733780147, null, 0.021423673670808885, 0.1332965908314021, null, 0.640952694324525, 0.583993110207876, null, 0.17440205342790494, 0.17972981733780147, null, 0.740625863119245, 0.6315322816286787, null], \"type\": \"scatter\", \"hoverinfo\": \"none\", \"y\": [0.49474860768712914, 0.5488515965193208, null, 0.49474860768712914, 0.42704536740474663, null, 0.49474860768712914, 0.68128520136847, null, 0.49474860768712914, 0.362322730884702, null, 0.49474860768712914, 0.3232711412508066, null, 0.14953665513987202, 0.362322730884702, null, 0.14953665513987202, 0.13985272363426526, null, 0.14953665513987202, 0.09186645974288632, null, 0.14953665513987202, 0.026771817842421997, null, 0.14953665513987202, 0.01876171413125327, null, 0.14953665513987202, 0.1735506267461867, null, 0.14953665513987202, 0.21665962402659544, null, 0.14953665513987202, 0.2083567880838434, null, 0.14953665513987202, 0.12631654071213483, null, 0.14953665513987202, 0.3232711412508066, null, 0.7696330846542071, 0.891868301175821, null, 0.7696330846542071, 0.68128520136847, null, 0.7696330846542071, 0.9532681441921305, null, 0.7696330846542071, 0.7311657634689946, null, 0.7696330846542071, 0.9011339078096633, null, 0.7696330846542071, 0.8016111783687677, null, 0.7696330846542071, 0.8089961609345658, null, 0.14485659826020547, 0.10321622277398101, null, 0.14485659826020547, 0.09186645974288632, null, 0.14485659826020547, 0.026771817842421997, null, 0.14485659826020547, 0.01876171413125327, null, 0.14485659826020547, 0.1735506267461867, null, 0.8089961609345658, 0.891868301175821, null, 0.8089961609345658, 0.68128520136847, null, 0.8089961609345658, 0.9532681441921305, null, 0.8089961609345658, 0.7311657634689946, null, 0.8089961609345658, 0.9011339078096633, null, 0.8089961609345658, 0.8016111783687677, null, 0.7222846879290787, 0.9528527425842739, null, 0.7222846879290787, 0.690016328140396, null, 0.7222846879290787, 0.5886703168399895, null, 0.01876171413125327, 0.026771817842421997, null, 0.01876171413125327, 0.09186645974288632, null, 0.01876171413125327, 0.10321622277398101, null, 0.01876171413125327, 0.1735506267461867, null, 0.8016111783687677, 0.891868301175821, null, 0.8016111783687677, 0.68128520136847, null, 0.8016111783687677, 0.9532681441921305, null, 0.8016111783687677, 0.7353428557575755, null, 0.8016111783687677, 0.7311657634689946, null, 0.8016111783687677, 0.9011339078096633, null, 0.43196344222361227, 0.3996510641743197, null, 0.43196344222361227, 0.5886703168399895, null, 0.43196344222361227, 0.4666482714834408, null, 0.9011339078096633, 0.891868301175821, null, 0.9011339078096633, 0.68128520136847, null, 0.9011339078096633, 0.9532681441921305, null, 0.24026772497187532, 0.362322730884702, null, 0.24026772497187532, 0.13985272363426526, null, 0.24026772497187532, 0.13022993020357043, null, 0.24026772497187532, 0.21665962402659544, null, 0.24026772497187532, 0.2083567880838434, null, 0.24026772497187532, 0.12631654071213483, null, 0.24026772497187532, 0.1839028760606296, null, 0.24026772497187532, 0.3232711412508066, null, 0.10321622277398101, 0.09186645974288632, null, 0.10321622277398101, 0.026771817842421997, null, 0.10321622277398101, 0.1735506267461867, null, 0.5006237737207431, 0.362322730884702, null, 0.5006237737207431, 0.42704536740474663, null, 0.5006237737207431, 0.6569436279895382, null, 0.5006237737207431, 0.7353428557575755, null, 0.5006237737207431, 0.5488515965193208, null, 0.5006237737207431, 0.3232711412508066, null, 0.1839028760606296, 0.13022993020357043, null, 0.1839028760606296, 0.12631654071213483, null, 0.1839028760606296, 0.13985272363426526, null, 0.5886703168399895, 0.3996510641743197, null, 0.5886703168399895, 0.4666482714834408, null, 0.5886703168399895, 0.690016328140396, null, 0.1735506267461867, 0.026771817842421997, null, 0.1735506267461867, 0.362322730884702, null, 0.1735506267461867, 0.3232711412508066, null, 0.1735506267461867, 0.21665962402659544, null, 0.1735506267461867, 0.2083567880838434, null, 0.1735506267461867, 0.09186645974288632, null, 0.690016328140396, 0.4666482714834408, null, 0.690016328140396, 0.6569436279895382, null, 0.362322730884702, 0.42704536740474663, null, 0.362322730884702, 0.21665962402659544, null, 0.362322730884702, 0.13985272363426526, null, 0.362322730884702, 0.5488515965193208, null, 0.362322730884702, 0.3232711412508066, null, 0.362322730884702, 0.2083567880838434, null, 0.13985272363426526, 0.2083567880838434, null, 0.13985272363426526, 0.13022993020357043, null, 0.13985272363426526, 0.21665962402659544, null, 0.13985272363426526, 0.12631654071213483, null, 0.13985272363426526, 0.3232711412508066, null, 0.891868301175821, 0.9532681441921305, null, 0.026771817842421997, 0.2083567880838434, null, 0.026771817842421997, 0.09186645974288632, null, 0.7353428557575755, 0.8800306496459869, null, 0.7353428557575755, 0.7311657634689946, null, 0.7353428557575755, 0.6569436279895382, null, 0.9768234503830939, 0.9528527425842739, null, 0.9768234503830939, 0.8800306496459869, null, 0.9768234503830939, 0.999395685828547, null, 0.13022993020357043, 0.12631654071213483, null, 0.21665962402659544, 0.12631654071213483, null, 0.21665962402659544, 0.2083567880838434, null, 0.21665962402659544, 0.3232711412508066, null, 0.21665962402659544, 0.42704536740474663, null, 0.2083567880838434, 0.12631654071213483, null, 0.2083567880838434, 0.3232711412508066, null, 0.2083567880838434, 0.42704536740474663, null, 0.12631654071213483, 0.3232711412508066, null, 0.5488515965193208, 0.42704536740474663, null, 0.5488515965193208, 0.68128520136847, null, 0.5488515965193208, 0.7311657634689946, null, 0.5488515965193208, 0.3232711412508066, null, 0.8800306496459869, 0.9528527425842739, null, 0.8800306496459869, 0.6569436279895382, null, 0.8800306496459869, 0.999395685828547, null, 0.4666482714834408, 0.3996510641743197, null, 0.3232711412508066, 0.42704536740474663, null, 0.9528527425842739, 0.999395685828547, null, 0.68128520136847, 0.7311657634689946, null], \"line\": {\"color\": \"#888\", \"width\": 0.5}}, {\"marker\": {\"colorscale\": \"Hot\", \"colorbar\": {\"title\": \"Node Connections\", \"thickness\": 15, \"titleside\": \"right\", \"xanchor\": \"left\"}, \"reversescale\": true, \"line\": {\"width\": 2}, \"size\": 10, \"showscale\": false, \"color\": [0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0]}, \"mode\": \"markers\", \"x\": [0.7801603911549438, 0.5249831588690298, 0.8085335344099086, 0.2599134798656856, 0.7353838928272886, 0.09088671576431506, 0.313999018186756, 0.6824813442515916, 0.20128789391122526, 0.8551947714242674, 0.7581736589784409, 0.25311953895059136, 0.4813859169876731, 0.9112422509614865, 0.04580558670435442, 0.4582523173083307, 0.12939557977525573, 0.607698913404794, 0.719569201584275, 0.8860336256842246, 0.4238357358399233, 0.8252497121120052, 0.47415009287034726, 0.26253385360950576, 0.9363713903322148, 0.6243437191127235, 0.5572917679006295, 0.7482655725962591, 0.6435799740880603, 0.34509802713919313, 0.021423673670808885, 0.640952694324525, 0.17440205342790494, 0.1332965908314021, 0.583993110207876, 0.3073865727705063, 0.740625863119245, 0.3345284735051981, 0.17972981733780147, 0.6315322816286787], \"type\": \"scatter\", \"hoverinfo\": \"text\", \"y\": [0.49474860768712914, 0.14953665513987202, 0.7696330846542071, 0.14485659826020547, 0.8089961609345658, 0.7222846879290787, 0.01876171413125327, 0.8016111783687677, 0.43196344222361227, 0.9011339078096633, 0.24026772497187532, 0.10321622277398101, 0.5006237737207431, 0.1839028760606296, 0.5886703168399895, 0.1735506267461867, 0.690016328140396, 0.362322730884702, 0.13985272363426526, 0.891868301175821, 0.026771817842421997, 0.9532681441921305, 0.7353428557575755, 0.9768234503830939, 0.13022993020357043, 0.21665962402659544, 0.2083567880838434, 0.12631654071213483, 0.5488515965193208, 0.8800306496459869, 0.4666482714834408, 0.3232711412508066, 0.9528527425842739, 0.3996510641743197, 0.42704536740474663, 0.09186645974288632, 0.68128520136847, 0.6569436279895382, 0.999395685828547, 0.7311657634689946], \"text\": [\"Intersection 0\", \"Intersection 1\", \"Intersection 2\", \"Intersection 3\", \"Intersection 4\", \"Intersection 5\", \"Intersection 6\", \"Intersection 7\", \"Intersection 8\", \"Intersection 9\", \"Intersection 10\", \"Intersection 11\", \"Intersection 12\", \"Intersection 13\", \"Intersection 14\", \"Intersection 15\", \"Intersection 16\", \"Intersection 17\", \"Intersection 18\", \"Intersection 19\", \"Intersection 20\", \"Intersection 21\", \"Intersection 22\", \"Intersection 23\", \"Intersection 24\", \"Intersection 25\", \"Intersection 26\", \"Intersection 27\", \"Intersection 28\", \"Intersection 29\", \"Intersection 30\", \"Intersection 31\", \"Intersection 32\", \"Intersection 33\", \"Intersection 34\", \"Intersection 35\", \"Intersection 36\", \"Intersection 37\", \"Intersection 38\", \"Intersection 39\"]}], {\"hovermode\": \"closest\", \"titlefont\": {\"size\": 16}, \"margin\": {\"r\": 5, \"t\": 40, \"l\": 5, \"b\": 20}, \"xaxis\": {\"showgrid\": false, \"zeroline\": false, \"showticklabels\": false}, \"showlegend\": false, \"yaxis\": {\"showgrid\": false, \"zeroline\": false, \"showticklabels\": false}, \"title\": \"<br>Network graph made with Python\"}, {\"showLink\": true, \"linkText\": \"Export to plot.ly\"})});</script>"
      ],
      "text/vnd.plotly.v1+html": [
       "<div id=\"92e89391-e00d-4669-b607-0e2ad0eaf968\" style=\"height: 525px; width: 100%;\" class=\"plotly-graph-div\"></div><script type=\"text/javascript\">require([\"plotly\"], function(Plotly) { window.PLOTLYENV=window.PLOTLYENV || {};window.PLOTLYENV.BASE_URL=\"https://plot.ly\";Plotly.newPlot(\"92e89391-e00d-4669-b607-0e2ad0eaf968\", [{\"mode\": \"lines\", \"x\": [0.7801603911549438, 0.6435799740880603, null, 0.7801603911549438, 0.583993110207876, null, 0.7801603911549438, 0.740625863119245, null, 0.7801603911549438, 0.607698913404794, null, 0.7801603911549438, 0.640952694324525, null, 0.5249831588690298, 0.607698913404794, null, 0.5249831588690298, 0.719569201584275, null, 0.5249831588690298, 0.3073865727705063, null, 0.5249831588690298, 0.4238357358399233, null, 0.5249831588690298, 0.313999018186756, null, 0.5249831588690298, 0.4582523173083307, null, 0.5249831588690298, 0.6243437191127235, null, 0.5249831588690298, 0.5572917679006295, null, 0.5249831588690298, 0.7482655725962591, null, 0.5249831588690298, 0.640952694324525, null, 0.8085335344099086, 0.8860336256842246, null, 0.8085335344099086, 0.740625863119245, null, 0.8085335344099086, 0.8252497121120052, null, 0.8085335344099086, 0.6315322816286787, null, 0.8085335344099086, 0.8551947714242674, null, 0.8085335344099086, 0.6824813442515916, null, 0.8085335344099086, 0.7353838928272886, null, 0.2599134798656856, 0.25311953895059136, null, 0.2599134798656856, 0.3073865727705063, null, 0.2599134798656856, 0.4238357358399233, null, 0.2599134798656856, 0.313999018186756, null, 0.2599134798656856, 0.4582523173083307, null, 0.7353838928272886, 0.8860336256842246, null, 0.7353838928272886, 0.740625863119245, null, 0.7353838928272886, 0.8252497121120052, null, 0.7353838928272886, 0.6315322816286787, null, 0.7353838928272886, 0.8551947714242674, null, 0.7353838928272886, 0.6824813442515916, null, 0.09088671576431506, 0.17440205342790494, null, 0.09088671576431506, 0.12939557977525573, null, 0.09088671576431506, 0.04580558670435442, null, 0.313999018186756, 0.4238357358399233, null, 0.313999018186756, 0.3073865727705063, null, 0.313999018186756, 0.25311953895059136, null, 0.313999018186756, 0.4582523173083307, null, 0.6824813442515916, 0.8860336256842246, null, 0.6824813442515916, 0.740625863119245, null, 0.6824813442515916, 0.8252497121120052, null, 0.6824813442515916, 0.47415009287034726, null, 0.6824813442515916, 0.6315322816286787, null, 0.6824813442515916, 0.8551947714242674, null, 0.20128789391122526, 0.1332965908314021, null, 0.20128789391122526, 0.04580558670435442, null, 0.20128789391122526, 0.021423673670808885, null, 0.8551947714242674, 0.8860336256842246, null, 0.8551947714242674, 0.740625863119245, null, 0.8551947714242674, 0.8252497121120052, null, 0.7581736589784409, 0.607698913404794, null, 0.7581736589784409, 0.719569201584275, null, 0.7581736589784409, 0.9363713903322148, null, 0.7581736589784409, 0.6243437191127235, null, 0.7581736589784409, 0.5572917679006295, null, 0.7581736589784409, 0.7482655725962591, null, 0.7581736589784409, 0.9112422509614865, null, 0.7581736589784409, 0.640952694324525, null, 0.25311953895059136, 0.3073865727705063, null, 0.25311953895059136, 0.4238357358399233, null, 0.25311953895059136, 0.4582523173083307, null, 0.4813859169876731, 0.607698913404794, null, 0.4813859169876731, 0.583993110207876, null, 0.4813859169876731, 0.3345284735051981, null, 0.4813859169876731, 0.47415009287034726, null, 0.4813859169876731, 0.6435799740880603, null, 0.4813859169876731, 0.640952694324525, null, 0.9112422509614865, 0.9363713903322148, null, 0.9112422509614865, 0.7482655725962591, null, 0.9112422509614865, 0.719569201584275, null, 0.04580558670435442, 0.1332965908314021, null, 0.04580558670435442, 0.021423673670808885, null, 0.04580558670435442, 0.12939557977525573, null, 0.4582523173083307, 0.4238357358399233, null, 0.4582523173083307, 0.607698913404794, null, 0.4582523173083307, 0.640952694324525, null, 0.4582523173083307, 0.6243437191127235, null, 0.4582523173083307, 0.5572917679006295, null, 0.4582523173083307, 0.3073865727705063, null, 0.12939557977525573, 0.021423673670808885, null, 0.12939557977525573, 0.3345284735051981, null, 0.607698913404794, 0.583993110207876, null, 0.607698913404794, 0.6243437191127235, null, 0.607698913404794, 0.719569201584275, null, 0.607698913404794, 0.6435799740880603, null, 0.607698913404794, 0.640952694324525, null, 0.607698913404794, 0.5572917679006295, null, 0.719569201584275, 0.5572917679006295, null, 0.719569201584275, 0.9363713903322148, null, 0.719569201584275, 0.6243437191127235, null, 0.719569201584275, 0.7482655725962591, null, 0.719569201584275, 0.640952694324525, null, 0.8860336256842246, 0.8252497121120052, null, 0.4238357358399233, 0.5572917679006295, null, 0.4238357358399233, 0.3073865727705063, null, 0.47415009287034726, 0.34509802713919313, null, 0.47415009287034726, 0.6315322816286787, null, 0.47415009287034726, 0.3345284735051981, null, 0.26253385360950576, 0.17440205342790494, null, 0.26253385360950576, 0.34509802713919313, null, 0.26253385360950576, 0.17972981733780147, null, 0.9363713903322148, 0.7482655725962591, null, 0.6243437191127235, 0.7482655725962591, null, 0.6243437191127235, 0.5572917679006295, null, 0.6243437191127235, 0.640952694324525, null, 0.6243437191127235, 0.583993110207876, null, 0.5572917679006295, 0.7482655725962591, null, 0.5572917679006295, 0.640952694324525, null, 0.5572917679006295, 0.583993110207876, null, 0.7482655725962591, 0.640952694324525, null, 0.6435799740880603, 0.583993110207876, null, 0.6435799740880603, 0.740625863119245, null, 0.6435799740880603, 0.6315322816286787, null, 0.6435799740880603, 0.640952694324525, null, 0.34509802713919313, 0.17440205342790494, null, 0.34509802713919313, 0.3345284735051981, null, 0.34509802713919313, 0.17972981733780147, null, 0.021423673670808885, 0.1332965908314021, null, 0.640952694324525, 0.583993110207876, null, 0.17440205342790494, 0.17972981733780147, null, 0.740625863119245, 0.6315322816286787, null], \"type\": \"scatter\", \"hoverinfo\": \"none\", \"y\": [0.49474860768712914, 0.5488515965193208, null, 0.49474860768712914, 0.42704536740474663, null, 0.49474860768712914, 0.68128520136847, null, 0.49474860768712914, 0.362322730884702, null, 0.49474860768712914, 0.3232711412508066, null, 0.14953665513987202, 0.362322730884702, null, 0.14953665513987202, 0.13985272363426526, null, 0.14953665513987202, 0.09186645974288632, null, 0.14953665513987202, 0.026771817842421997, null, 0.14953665513987202, 0.01876171413125327, null, 0.14953665513987202, 0.1735506267461867, null, 0.14953665513987202, 0.21665962402659544, null, 0.14953665513987202, 0.2083567880838434, null, 0.14953665513987202, 0.12631654071213483, null, 0.14953665513987202, 0.3232711412508066, null, 0.7696330846542071, 0.891868301175821, null, 0.7696330846542071, 0.68128520136847, null, 0.7696330846542071, 0.9532681441921305, null, 0.7696330846542071, 0.7311657634689946, null, 0.7696330846542071, 0.9011339078096633, null, 0.7696330846542071, 0.8016111783687677, null, 0.7696330846542071, 0.8089961609345658, null, 0.14485659826020547, 0.10321622277398101, null, 0.14485659826020547, 0.09186645974288632, null, 0.14485659826020547, 0.026771817842421997, null, 0.14485659826020547, 0.01876171413125327, null, 0.14485659826020547, 0.1735506267461867, null, 0.8089961609345658, 0.891868301175821, null, 0.8089961609345658, 0.68128520136847, null, 0.8089961609345658, 0.9532681441921305, null, 0.8089961609345658, 0.7311657634689946, null, 0.8089961609345658, 0.9011339078096633, null, 0.8089961609345658, 0.8016111783687677, null, 0.7222846879290787, 0.9528527425842739, null, 0.7222846879290787, 0.690016328140396, null, 0.7222846879290787, 0.5886703168399895, null, 0.01876171413125327, 0.026771817842421997, null, 0.01876171413125327, 0.09186645974288632, null, 0.01876171413125327, 0.10321622277398101, null, 0.01876171413125327, 0.1735506267461867, null, 0.8016111783687677, 0.891868301175821, null, 0.8016111783687677, 0.68128520136847, null, 0.8016111783687677, 0.9532681441921305, null, 0.8016111783687677, 0.7353428557575755, null, 0.8016111783687677, 0.7311657634689946, null, 0.8016111783687677, 0.9011339078096633, null, 0.43196344222361227, 0.3996510641743197, null, 0.43196344222361227, 0.5886703168399895, null, 0.43196344222361227, 0.4666482714834408, null, 0.9011339078096633, 0.891868301175821, null, 0.9011339078096633, 0.68128520136847, null, 0.9011339078096633, 0.9532681441921305, null, 0.24026772497187532, 0.362322730884702, null, 0.24026772497187532, 0.13985272363426526, null, 0.24026772497187532, 0.13022993020357043, null, 0.24026772497187532, 0.21665962402659544, null, 0.24026772497187532, 0.2083567880838434, null, 0.24026772497187532, 0.12631654071213483, null, 0.24026772497187532, 0.1839028760606296, null, 0.24026772497187532, 0.3232711412508066, null, 0.10321622277398101, 0.09186645974288632, null, 0.10321622277398101, 0.026771817842421997, null, 0.10321622277398101, 0.1735506267461867, null, 0.5006237737207431, 0.362322730884702, null, 0.5006237737207431, 0.42704536740474663, null, 0.5006237737207431, 0.6569436279895382, null, 0.5006237737207431, 0.7353428557575755, null, 0.5006237737207431, 0.5488515965193208, null, 0.5006237737207431, 0.3232711412508066, null, 0.1839028760606296, 0.13022993020357043, null, 0.1839028760606296, 0.12631654071213483, null, 0.1839028760606296, 0.13985272363426526, null, 0.5886703168399895, 0.3996510641743197, null, 0.5886703168399895, 0.4666482714834408, null, 0.5886703168399895, 0.690016328140396, null, 0.1735506267461867, 0.026771817842421997, null, 0.1735506267461867, 0.362322730884702, null, 0.1735506267461867, 0.3232711412508066, null, 0.1735506267461867, 0.21665962402659544, null, 0.1735506267461867, 0.2083567880838434, null, 0.1735506267461867, 0.09186645974288632, null, 0.690016328140396, 0.4666482714834408, null, 0.690016328140396, 0.6569436279895382, null, 0.362322730884702, 0.42704536740474663, null, 0.362322730884702, 0.21665962402659544, null, 0.362322730884702, 0.13985272363426526, null, 0.362322730884702, 0.5488515965193208, null, 0.362322730884702, 0.3232711412508066, null, 0.362322730884702, 0.2083567880838434, null, 0.13985272363426526, 0.2083567880838434, null, 0.13985272363426526, 0.13022993020357043, null, 0.13985272363426526, 0.21665962402659544, null, 0.13985272363426526, 0.12631654071213483, null, 0.13985272363426526, 0.3232711412508066, null, 0.891868301175821, 0.9532681441921305, null, 0.026771817842421997, 0.2083567880838434, null, 0.026771817842421997, 0.09186645974288632, null, 0.7353428557575755, 0.8800306496459869, null, 0.7353428557575755, 0.7311657634689946, null, 0.7353428557575755, 0.6569436279895382, null, 0.9768234503830939, 0.9528527425842739, null, 0.9768234503830939, 0.8800306496459869, null, 0.9768234503830939, 0.999395685828547, null, 0.13022993020357043, 0.12631654071213483, null, 0.21665962402659544, 0.12631654071213483, null, 0.21665962402659544, 0.2083567880838434, null, 0.21665962402659544, 0.3232711412508066, null, 0.21665962402659544, 0.42704536740474663, null, 0.2083567880838434, 0.12631654071213483, null, 0.2083567880838434, 0.3232711412508066, null, 0.2083567880838434, 0.42704536740474663, null, 0.12631654071213483, 0.3232711412508066, null, 0.5488515965193208, 0.42704536740474663, null, 0.5488515965193208, 0.68128520136847, null, 0.5488515965193208, 0.7311657634689946, null, 0.5488515965193208, 0.3232711412508066, null, 0.8800306496459869, 0.9528527425842739, null, 0.8800306496459869, 0.6569436279895382, null, 0.8800306496459869, 0.999395685828547, null, 0.4666482714834408, 0.3996510641743197, null, 0.3232711412508066, 0.42704536740474663, null, 0.9528527425842739, 0.999395685828547, null, 0.68128520136847, 0.7311657634689946, null], \"line\": {\"color\": \"#888\", \"width\": 0.5}}, {\"marker\": {\"colorscale\": \"Hot\", \"colorbar\": {\"title\": \"Node Connections\", \"thickness\": 15, \"titleside\": \"right\", \"xanchor\": \"left\"}, \"reversescale\": true, \"line\": {\"width\": 2}, \"size\": 10, \"showscale\": false, \"color\": [0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0]}, \"mode\": \"markers\", \"x\": [0.7801603911549438, 0.5249831588690298, 0.8085335344099086, 0.2599134798656856, 0.7353838928272886, 0.09088671576431506, 0.313999018186756, 0.6824813442515916, 0.20128789391122526, 0.8551947714242674, 0.7581736589784409, 0.25311953895059136, 0.4813859169876731, 0.9112422509614865, 0.04580558670435442, 0.4582523173083307, 0.12939557977525573, 0.607698913404794, 0.719569201584275, 0.8860336256842246, 0.4238357358399233, 0.8252497121120052, 0.47415009287034726, 0.26253385360950576, 0.9363713903322148, 0.6243437191127235, 0.5572917679006295, 0.7482655725962591, 0.6435799740880603, 0.34509802713919313, 0.021423673670808885, 0.640952694324525, 0.17440205342790494, 0.1332965908314021, 0.583993110207876, 0.3073865727705063, 0.740625863119245, 0.3345284735051981, 0.17972981733780147, 0.6315322816286787], \"type\": \"scatter\", \"hoverinfo\": \"text\", \"y\": [0.49474860768712914, 0.14953665513987202, 0.7696330846542071, 0.14485659826020547, 0.8089961609345658, 0.7222846879290787, 0.01876171413125327, 0.8016111783687677, 0.43196344222361227, 0.9011339078096633, 0.24026772497187532, 0.10321622277398101, 0.5006237737207431, 0.1839028760606296, 0.5886703168399895, 0.1735506267461867, 0.690016328140396, 0.362322730884702, 0.13985272363426526, 0.891868301175821, 0.026771817842421997, 0.9532681441921305, 0.7353428557575755, 0.9768234503830939, 0.13022993020357043, 0.21665962402659544, 0.2083567880838434, 0.12631654071213483, 0.5488515965193208, 0.8800306496459869, 0.4666482714834408, 0.3232711412508066, 0.9528527425842739, 0.3996510641743197, 0.42704536740474663, 0.09186645974288632, 0.68128520136847, 0.6569436279895382, 0.999395685828547, 0.7311657634689946], \"text\": [\"Intersection 0\", \"Intersection 1\", \"Intersection 2\", \"Intersection 3\", \"Intersection 4\", \"Intersection 5\", \"Intersection 6\", \"Intersection 7\", \"Intersection 8\", \"Intersection 9\", \"Intersection 10\", \"Intersection 11\", \"Intersection 12\", \"Intersection 13\", \"Intersection 14\", \"Intersection 15\", \"Intersection 16\", \"Intersection 17\", \"Intersection 18\", \"Intersection 19\", \"Intersection 20\", \"Intersection 21\", \"Intersection 22\", \"Intersection 23\", \"Intersection 24\", \"Intersection 25\", \"Intersection 26\", \"Intersection 27\", \"Intersection 28\", \"Intersection 29\", \"Intersection 30\", \"Intersection 31\", \"Intersection 32\", \"Intersection 33\", \"Intersection 34\", \"Intersection 35\", \"Intersection 36\", \"Intersection 37\", \"Intersection 38\", \"Intersection 39\"]}], {\"hovermode\": \"closest\", \"titlefont\": {\"size\": 16}, \"margin\": {\"r\": 5, \"t\": 40, \"l\": 5, \"b\": 20}, \"xaxis\": {\"showgrid\": false, \"zeroline\": false, \"showticklabels\": false}, \"showlegend\": false, \"yaxis\": {\"showgrid\": false, \"zeroline\": false, \"showticklabels\": false}, \"title\": \"<br>Network graph made with Python\"}, {\"showLink\": true, \"linkText\": \"Export to plot.ly\"})});</script>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# run this code, note the effect of including the optional parameters in the function call.\n",
    "show_map(map_40, start=5, goal=34, path=[5, 16,37,12, 34])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "---\n",
    "# The Algorithm\n",
    "### Writing your algorithm\n",
    "The algorithm written will be responsible for **generating a `path`** like the one passed into `show_map` above. In fact, when called with the same **map, start and goal**, as above your algorithm should produce the path `[5, 16, 37, 12, 34]`. However you must complete several methods before it will work.\n",
    "\n",
    "```bash\n",
    "> PathPlanner(map_40, 5, 34).path\n",
    "[5, 16, 37, 12, 34]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "'''# A* search Implementation.\n",
    "\n",
    "from math import sqrt\n",
    "\n",
    "def shortest_path(M, start, goal):\n",
    "    \"\"\"Returns the lowest cost path from start to goal.\"\"\"\n",
    "    \n",
    "    pos = M.intersections\n",
    "    M = M.roads\n",
    "    \n",
    "    closed = set()\n",
    "    opened = set([start])\n",
    "    came_from = {}\n",
    "    num_nodes = len(M)\n",
    "    g_scores = [99999 for _ in range(num_nodes)]\n",
    "    f_scores = [99999 for _ in range(num_nodes)]\n",
    "    g_scores[start] = 0.0\n",
    "    f_scores[start] = heuristic(start, goal, pos)\n",
    "    \n",
    "    while opened:\n",
    "        current = get_next_node(opened, f_scores)\n",
    "        if current == goal:\n",
    "            print(\"f_score:\", f_scores[current])\n",
    "            print(\"g_score:\", g_scores[current])\n",
    "            return reconstruct_path(came_from, current, start)\n",
    "        opened.remove(current)\n",
    "        closed.add(current)\n",
    "        neighbors = M[current]\n",
    "        for neighbor in neighbors:\n",
    "            if neighbor in closed:\n",
    "                continue\n",
    "            if neighbor not in opened:\n",
    "                opened.add(neighbor)\n",
    "            \n",
    "            tentative_g = g_scores[current] + distance(current, neighbor, pos)\n",
    "            if tentative_g >= g_scores[neighbor]:\n",
    "                continue\n",
    "            came_from[neighbor] = current\n",
    "            g_scores[neighbor] = tentative_g\n",
    "            f_scores[neighbor] = g_scores[neighbor] + heuristic(neighbor, goal, pos)\n",
    "    return None\n",
    "    \n",
    "    \n",
    "\n",
    "def get_next_node(opened, f_scores):\n",
    "    best_idx = None\n",
    "    lowest_f = 9999999                         ######float('inf') ??\n",
    "    for node in opened:\n",
    "        f = f_scores[node]\n",
    "        if f < lowest_f:\n",
    "            best_idx = node\n",
    "            lowest_f = f\n",
    "    return best_idx\n",
    "\n",
    "def reconstruct_path(came_from, current, start):\n",
    "    path = []\n",
    "    while current != start:\n",
    "        path.append(current)\n",
    "        current = came_from[current]\n",
    "    path.append(start)\n",
    "    path.reverse()\n",
    "    return path\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "def distance(start, goal, pos):\n",
    "    x1, y1 = pos[start]\n",
    "    x2, y2 = pos[goal]\n",
    "    return sqrt( (x2-x1)**2 + (y2-y1)**2 )\n",
    "\n",
    "def heuristic(start,goal,pos):\n",
    "    return distance(start, goal, pos)\n",
    "\n",
    "\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# Do not change this cell\n",
    "# When you write your methods correctly, this cell will execute without problems\n",
    "class PathPlanner():\n",
    "    \"\"\"Construct a PathPlanner Object\"\"\"\n",
    "    def __init__(self, M, start=None, goal=None):\n",
    "        self.map = M\n",
    "        self.start= start\n",
    "        self.goal = goal\n",
    "        \n",
    "        self.closedSet = self.create_closedSet() if goal != None and start != None else None\n",
    "        self.openSet = self.create_openSet() if goal != None and start != None else None\n",
    "        self.cameFrom = self.create_cameFrom() if goal != None and start != None else None\n",
    "        self.gScore = self.create_gScore() if goal != None and start != None else None\n",
    "        self.fScore = self.create_fScore() if goal != None and start != None else None\n",
    "        \n",
    "        self.path = self.run_search() if self.map and self.start != None and self.goal != None else None #####\n",
    "\n",
    "        \n",
    "    def run_search(self):\n",
    "        if self.map == None:\n",
    "            raise(ValueError, \"Must create map before running search. Try running: PathPlanner.set_map(start_node)\") ###########\n",
    "        if self.start == None:\n",
    "            raise(ValueError, \"Must create start node before running search. Try running: PathPlanner.set_start(start_node)\") ##\n",
    "        if self.goal == None:\n",
    "            raise(ValueError, \"Must create goal node before running search. Try running: PathPlanner.set_goal(start_node)\") ####\n",
    "        self.closedSet = self.closedSet if self.closedSet != None else self.create_closedSet() \n",
    "        self.openSet = self.openSet if self.openSet != None else  self.create_openSet()\n",
    "        self.cameFrom = self.cameFrom if self.cameFrom != None else  self.create_cameFrom()\n",
    "        self.gScore = self.gScore if self.gScore != None else  self.create_gScore()\n",
    "        self.fScore = self.fScore if self.fScore != None else  self.create_fScore()\n",
    "        \n",
    "        \n",
    "        while not self.is_open_empty(): # run 'if the openSet is NOT empty'. \n",
    "            current = self.get_current_node() #Returns the node in the openSet with the \"lowest value of f(node)\"\n",
    "\n",
    "            if current == self.goal:\n",
    "                self.path = [x for x in reversed(self.reconstruct_path(current))] #\n",
    "                return self.path\n",
    "            else:\n",
    "                self.openSet.remove(current) # goal?\n",
    "                self.closedSet.add(current) # frontier?\n",
    "                \n",
    "            for neighbor in self.get_neighbors(current): ###\n",
    "                if neighbor in self.closedSet:\n",
    "                    continue    # Ignore the neighbor which is already evaluated.\n",
    "                if not neighbor in self.openSet:    # Discover a new node\n",
    "                    self.openSet.add(neighbor)\n",
    "                # The distance from start to a neighbor; the \"dist_between\" function may vary as per the solution requirements.\n",
    "                if self.get_tenative_gScore(current, neighbor) >= self.get_gScore(neighbor):\n",
    "                    continue        # This is not a better path.\n",
    "                self.record_best_path_to(current, neighbor) # This path is the best until now. Record it!\n",
    "                \n",
    "                \n",
    "        print(\"No Path Found\")\n",
    "        self.path = None\n",
    "        return(False)        \n",
    "    \n",
    "    def reconstruct_path(self, current):\n",
    "        \"\"\" Reconstructs path after search \"\"\"\n",
    "        total_path = [current] ##a list?\n",
    "        while current in self.cameFrom.keys():\n",
    "            current = self.cameFrom[current] ##it's gonna be a list of possible connectivity? \n",
    "            total_path.append(current)\n",
    "        return total_path    \n",
    "        \n",
    "    def get_path(self):\n",
    "        \"\"\" Reconstructs path after search \"\"\"\n",
    "        if self.path:\n",
    "            return self.path \n",
    "        else :\n",
    "            self.run_search() ##########\n",
    "            return self.path\n",
    "    \n",
    "    \n",
    "################################################################################################################################\n",
    "    def _reset(self):\n",
    "        \"\"\"Private method used to reset the closedSet, openSet, cameFrom, gScore, fScore, and path attributes\"\"\"\n",
    "        self.closedSet = None\n",
    "        self.openSet = None\n",
    "        self.cameFrom = None\n",
    "        self.gScore = None\n",
    "        self.fScore = None\n",
    "        \n",
    "        self.path = self.run_search() if self.map and self.start and self.goal else None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Create the following methods:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# no.1\n",
    "\n",
    "def is_open_empty(self):\n",
    "    \"\"\"returns True if the open set is empty. False otherwise. \"\"\"\n",
    "    # TODO: Return True if the \"open set\" is empty. False otherwise.\n",
    "    if len(self.openSet)==0:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## [note]\n",
    "max() or min() function using 'key' and lambda expression?\n",
    "\n",
    "#### Lambda\n",
    "- It is used for creating small, one-time and anonymous function objects: \n",
    "  - `lambda (arguments) : (expression)`\n",
    "  - lambda operator can have any number of arguments, but it can have only one expression. It cannot contain any statements and it returns a **function object** which can be assigned to any variable.\n",
    "- Let's say function name is **add()**, it expects 2 arguments x and y and returns their sum.\n",
    "- In this case the **function object** is assigned to the **add** variable.\n",
    "\n",
    "```\n",
    "def add(x, y): \n",
    "    return x + y\n",
    "  \n",
    "add(2, 3)  # Output: 5\n",
    "----------------------------\n",
    "add = lambda x, y : x + y \n",
    "print(add(2, 3)) # Output: 5\n",
    "```\n",
    "> Mostly lambda functions are passed as parameters to a function which expects a **function objects** as parameter like..\n",
    "- map(), reduce(), filter()\n",
    "  \n",
    "\n",
    "**`map(function_object, iterable1, iterable2,...)`**\n",
    "- It executes the **function_object** for each element in the sequence and returns a **list** of the elements modified by the function object. In Python3, map function returns an iterator or map object. We can force convert the map-output such as `list(map object)` \n",
    "\n",
    "```\n",
    "ex1>###################################################\n",
    "def multiply2(x):\n",
    "  return x*2\n",
    "map(multiply2, [1, 2, 3, 4])  # Output [2, 4, 6, 8]\n",
    "-------------------------------------------------------\n",
    "map(lambda x : x*2, [1, 2, 3, 4]) #Output [2, 4, 6, 8]\n",
    "\n",
    "ex2>#################\n",
    "list_a = [1, 2, 3]\n",
    "list_b = [10, 20, 30]\n",
    "---------------------------------------------------------------  \n",
    "map(lambda x, y: x + y, list_a, list_b) # Output: [11, 22, 33]\n",
    "\n",
    "ex3>######################################################################\n",
    "two_dict = [{'name': 'python', 'points': 10}, {'name': 'java', 'points': 8}]\n",
    "-------------------------------------------------  \n",
    "map(lambda x : x['name'], two_dict) \n",
    "map(lambda x : x['points']*10,  two_dict) \n",
    "map(lambda x : x['name'] == \"python\", two_dict) # Output: ['python', 'java'], Output: [100, 80], Output: [True, False]\n",
    "```\n",
    "\n",
    "**`filter(function_object, iterable)`**\n",
    "- filter function expects two arguments, function_object and an iterable(only one). **function_object returns a boolean value**. function_object is called for each element of the iterable and filter returns only those element for which the function_object returns true. filter function in Python3 returns a filter object or the iterator which gets lazily evaluated, so Converts the filter obj to a list..\n",
    "\n",
    "```\n",
    "a = [1, 2, 3, 4, 5, 6]\n",
    "filter(lambda x : x % 2 == 0, a)      # Output: [2, 4, 6]\n",
    "\n",
    "two_dict = [{'name': 'python', 'points': 10}, {'name': 'java', 'points': 8}]\n",
    "filter(lambda x : x['name'] == 'python', two_dict)      # Output: [{'name': 'python', 'points': 10}]\n",
    "\n",
    "list_a = [1, 2, 3, 4, 5]\n",
    "filter_obj = filter(lambda x: x % 2 == 0, list_a) \n",
    "even_num = list(filter_obj) \n",
    "print(even_num)      # Output: [2, 4]\n",
    "```\n",
    "\n",
    "#### min(), max() function using 'key'\n",
    "- like a filtering ???\n",
    "- To modify the object before comparing based on a particular attribute/index you've to use the **key** argument.\n",
    "- For example, suppose you've a list of numbers in **string** form, but you want to compare those items by their **integer** value.\n",
    "\n",
    "```\n",
    "lis = ['1','100','111','2']\n",
    "max(lis, key=lambda x: int(x))      # Output: '111'\n",
    "```\n",
    "- By default max will will compare the items by the first index, if the first index is same then it'd compare the second index. But, what if you wanted to compare each item by the value at index 1?\n",
    "\n",
    "```\n",
    "lis = [(1,'a'),(3,'c'), (4,'e'), (-1,'z')]\n",
    "max(lis, key = lambda x: x[1])     # Output: (-1,'z')\n",
    "```\n",
    "- Strongly simplified version of `max()` \n",
    "\n",
    "What is max()??\n",
    "```\n",
    "def max(items, key=lambda x: x):\n",
    "    current = item[0]\n",
    "    for i in items:\n",
    "        if key(i) > key(current):\n",
    "            current = i\n",
    "    return current\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "k={'g':1,'h':6,'i':8}; k.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# no.2\n",
    "# Basically 'current' is the node with the minimum f-score in this iteration.\n",
    "# the search will stop when current is the goal node.\n",
    "def get_current_node(self):\n",
    "    \"\"\" Returns the node in the open set with the lowest value of f(node).\"\"\"\n",
    "    # TODO: Return the node in the \"open set\" with the lowest value of f(node).\n",
    "    #low_f = sorted(self.fScore.keys())\n",
    "    #low_f_value = self.fScore[low_f[0]]\n",
    "    #if low_f_value in self.openSet:\n",
    "    #    return low_f_value\n",
    "    box ={} #hold the result of fScore function for each node in openSet\n",
    "    for i in self.openSet:\n",
    "        box[i] = self.calculate_fscore(i)\n",
    "    current_node = min(box, key=box.get)\n",
    "    return current_node\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "#no.3\n",
    "\n",
    "def get_neighbors(self, node):\n",
    "    \"\"\"Returns the neighbors of a node\"\"\"\n",
    "    # TODO: Return the neighbors of a node\n",
    "    return set(self.map.roads[node])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## [note]\n",
    "### Get() method for dictionaries\n",
    "- In python dictionaries, following is a conventional method to access a value for a key\n",
    "\n",
    "```\n",
    "dic = {\"A\":1, \"B\":2}\n",
    "print(dic[\"A\"])\n",
    "print(dic[\"C\"])\n",
    "```\n",
    "- The problem that arises here is that the 3rd line of the code returns a key error.\n",
    "- `get(key, default = None)` method is used to avoid such situations. This method returns the value for the given key, if present in the dictionary. If not, then **it will return None** (if get() is used with only one argument).\n",
    "\n",
    "```\n",
    "dic = {\"A\":1, \"B\":2}\n",
    "print(dic.get(\"A\"))\n",
    "print(dic.get(\"C\"))\n",
    "print(dic.get(\"C\",\"Not Found ! \"))  #Output: 1, #Output: None, #Output: Not Found !\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "#no.4\n",
    "\n",
    "def get_tenative_gScore(self, current, neighbor):\n",
    "    \"\"\"Returns the tenative g Score of a node\"\"\"\n",
    "    # TODO: Return the g Score of the current node plus distance from the current node to it's neighbors\n",
    "    return(self.get_gScore(current) + self.distance(current, neighbor))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "#///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////\n",
    "#no.5\n",
    "\n",
    "def get_gScore(self, node):\n",
    "    \"\"\"Returns the g Score of a node\"\"\"\n",
    "    # TODO: Return the g Score of a node\n",
    "    gg = self.gScore.get(node)\n",
    "    if gg == None:\n",
    "        return float('inf')\n",
    "    else:\n",
    "        return gg\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "#no.6\n",
    "\n",
    "def record_best_path_to(self, current, neighbor):\n",
    "    \"\"\"Record the best path to a node \"\"\"\n",
    "    # TODO: Record the best path to a node, by updating cameFrom, gScore, and fScore\n",
    "    self.cameFrom[neighbor] = current \n",
    "    # current is the node with the minimum f-score in this iteration. If the implementation is correct and the heuristic \n",
    "    # used is consistent, this means that at this point it is guaranteed that we already found the shortest path from \n",
    "    # the start to current. This is why current is added to the closed set and ignored if it shows up again during \n",
    "    # the execution. This is also the reason why the search stops when current is the goal node.\n",
    "    # So, after finding current, the algorithm evaluates all its neighbors that are not already in the closed set. \n",
    "    # The record_best_path function is called when the neighbor being evaluated appears for the first time during the execution,\n",
    "    # or if, at this iteration, it is reached from a path that is shorter than the best one found before.\n",
    "    \n",
    "    self.gScore[neighbor] = self.get_tenative_gScore(current, neighbor) \n",
    "    self.fScore[current] = self.calculate_fscore(current)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "#no.0-1\n",
    "\n",
    "def create_closedSet(self):\n",
    "    \"\"\" Creates and returns a data structure suitable to hold the set of nodes already evaluated\"\"\"\n",
    "    return(set())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "#no.0-2\n",
    "\n",
    "def create_openSet(self):\n",
    "    \"\"\" Creates and returns a data structure suitable to hold the set of currently discovered nodes \n",
    "    that are not evaluated yet. Initially, only the start node is known.\"\"\"\n",
    "    if self.start != None:\n",
    "        # TODO: return a data structure suitable to hold the set of currently discovered nodes \n",
    "        # that are not evaluated yet. Make sure to include the start node.\n",
    "        init_node = set()\n",
    "        init_node.add(self.start)\n",
    "        return(init_node)\n",
    "    \n",
    "    raise(ValueError, \"Must create start node before creating an open set. Try running PathPlanner.set_start(start_node)\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "#no.0-3\n",
    "\n",
    "def create_cameFrom(self):\n",
    "    \"\"\"Creates and returns a data structure that shows which node can most efficiently be reached from another,\n",
    "    for each node.\"\"\"\n",
    "    # TODO: return a data structure that shows which node can most efficiently be reached from another, for each node.\n",
    "    return({})    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## [note]\n",
    "what is the point of having a variable store an infinite value in a program? \n",
    "\n",
    "It acts as an unbounded upper value for comparison. This is useful for finding lowest values for something. For example, calculating path route costs when traversing trees(Finding the \"cheapest\" path in a list of options:)\n",
    "```\n",
    "lowest_path_cost = float('inf')\n",
    "path_costs = [1, 100, 2000000000000, 50]\n",
    "for path in path_costs:\n",
    "    if path < lowest_path_cost:\n",
    "        lowest_path_cost = path\n",
    "lowest_path_cost\n",
    "```\n",
    "\n",
    "if you didn't have `float('Inf')` available to you, what value would you use for **the initial lowest_path_cost**? Would 9999999 be enough -- `float('Inf')` removes this guesswork."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "#no.0-4\n",
    "\n",
    "def create_fScore(self):\n",
    "    \"\"\"Creates and returns a data structure that holds the total cost of getting from the start node to the goal\n",
    "    by passing by that node, for each node. That value is partly known, partly heuristic.\n",
    "    For the first node, that value is completely heuristic.\"\"\"\n",
    "    # TODO:  a data structure that holds the total cost of getting from the start node to the goal\n",
    "    # by passing by that node, for each node. That value is partly known, partly heuristic.\n",
    "    # For the first node, that value is completely heuristic. The rest of the node's value should be set to infinity.\n",
    "    fscore = {}\n",
    "    #f_score[self.calculate_fscore(self.start) + 1.0] = self.start\n",
    "    #return f_score  \n",
    "\n",
    "    for i in range(len(self.map.intersections)):\n",
    "        fscore[i] = float('inf')\n",
    "    fscore[self.start] = self.heuristic_cost_estimate(self.start)\n",
    "    return fscore\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "#no.0-5\n",
    "\n",
    "def create_gScore(self):\n",
    "    \"\"\"Creates and returns a data structure that holds the cost of getting from the start node to that node, for each node.\n",
    "    The cost of going from start to start is zero.\"\"\"\n",
    "    # TODO: a data structure that holds the cost of getting from the start node to that node, for each node.\n",
    "    # for each node. The cost of going from start to start is zero. The rest of the node's values should be set to infinity.\n",
    "    gscore = {}\n",
    "    for i in range(len(self.map.intersections)):\n",
    "        gscore[i] = float('inf')\n",
    "    gscore[self.start] = 0\n",
    "    return gscore\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "###############################################################################################################################"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "#no.0-6 # for run_search() value error...saying...[if self.map == None]\n",
    "#\"Must create map before running search. Try running:::::::::::::::::::: PathPlanner.set_map(start_node)\"\n",
    "\n",
    "def set_map(self, M):\n",
    "    \"\"\"Method used to set map attribute \"\"\"\n",
    "    self._reset(self)\n",
    "    self.start = None\n",
    "    self.goal = None\n",
    "    # TODO: Set map to new value.\n",
    "    self.map = M\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "#no.0-6 # for run_search() value error...saying...[if self.start == None]\n",
    "#\"Must create map before running search. Try running:::::::::::::::::::::: PathPlanner.set_start(start_node)\"\n",
    "\n",
    "def set_start(self, start):\n",
    "    \"\"\"Method used to set start attribute \"\"\"\n",
    "    self._reset(self)\n",
    "    # TODO: Set start value. Remember to remove goal, closedSet, openSet, cameFrom, gScore, fScore, \n",
    "    # and path attributes' values.\n",
    "    self.goal = None\n",
    "    self.closedSet = None\n",
    "    self.openSet = None\n",
    "    self.cameFrom = None\n",
    "    self.gScore = None\n",
    "    self.fScore = None\n",
    "    self.path = None\n",
    "    self.start = start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "#no.0-6 # for run_search() value error...saying...[if self.goal == None]\n",
    "#\"Must create map before running search. Try running::::::::::::::::::::: PathPlanner.set_goal(start_node)\"\n",
    "\n",
    "def set_goal(self, goal):\n",
    "    \"\"\"Method used to set goal attribute \"\"\"\n",
    "    self._reset(self)\n",
    "    # TODO: Set goal value.\n",
    "    self.goal = goal\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "###############################################################################################################################"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# calculation-01\n",
    "\n",
    "def distance(self, node_1, node_2):\n",
    "    \"\"\" Computes the Euclidean L2 Distance\"\"\"\n",
    "    # TODO: Compute and return the Euclidean L2 Distance\n",
    "    (x1, y1) = self.map.intersections[node_1]\n",
    "    (x2, y2) = self.map.intersections[node_2]\n",
    "    dist = math.sqrt((x2-x1)**2 + (y2-y1)**2)\n",
    "    return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# calculation-02\n",
    "\n",
    "def heuristic_cost_estimate(self, node):\n",
    "    \"\"\" Returns the heuristic cost estimate of a node \"\"\"\n",
    "    # TODO: Return the heuristic cost estimate of a node\n",
    "    (x1, y1) = self.map.intersections[node]\n",
    "    (x2, y2) = self.map.intersections[self.goal]\n",
    "    dist = math.sqrt((x2-x2)**2 + (y2-y1)**2)\n",
    "    return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# calculation-03\n",
    "\n",
    "def calculate_fscore(self, node):\n",
    "    \"\"\"Calculate the f score of a node. \"\"\"\n",
    "    # TODO: Calculate and returns the f score of a node. \n",
    "    # REMEMBER F = G + H\n",
    "    f = self.get_gScore(node) + self.heuristic_cost_estimate(node)\n",
    "    return f\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "PathPlanner.create_closedSet = create_closedSet\n",
    "PathPlanner.create_openSet = create_openSet\n",
    "PathPlanner.create_cameFrom = create_cameFrom\n",
    "PathPlanner.create_gScore = create_gScore\n",
    "PathPlanner.create_fScore = create_fScore\n",
    "#PathPlanner._reset = _reset ??????????????????????????????????????????? in the class definition\n",
    "PathPlanner.set_map = set_map\n",
    "PathPlanner.set_start = set_start\n",
    "PathPlanner.set_goal = set_goal\n",
    "PathPlanner.get_current_node = get_current_node\n",
    "PathPlanner.get_neighbors = get_neighbors\n",
    "PathPlanner.get_gScore = get_gScore\n",
    "PathPlanner.get_tenative_gScore = get_tenative_gScore\n",
    "PathPlanner.is_open_empty = is_open_empty\n",
    "PathPlanner.distance = distance\n",
    "PathPlanner.heuristic_cost_estimate = heuristic_cost_estimate\n",
    "PathPlanner.calculate_fscore = calculate_fscore\n",
    "PathPlanner.record_best_path_to = record_best_path_to"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "great! Your code works for these inputs!\n"
     ]
    }
   ],
   "source": [
    "planner = PathPlanner(map_40, 5, 34)\n",
    "path = planner.path\n",
    "if path == [5, 16, 37, 12, 34]:\n",
    "    print(\"great! Your code works for these inputs!\")\n",
    "else:\n",
    "    print(\"something is off, your code produced the following:\")\n",
    "    print(path)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Testing your Code\n",
    "If the code below produces no errors, your algorithm is behaving correctly. You are almost ready to submit! Before you submit, go through the following submission checklist:\n",
    "\n",
    "**Submission Checklist**\n",
    "\n",
    "1. Does my code pass all tests?\n",
    "2. Does my code implement `A*` search and not some other search algorithm?\n",
    "3. Do I use an **admissible heuristic** to direct search efforts towards the goal?\n",
    "4. Do I use data structures which avoid unnecessarily slow lookups?\n",
    "\n",
    "When you can answer \"yes\" to all of these questions, submit by pressing the Submit button in the lower right!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "All tests pass! Congratulations!\n"
     ]
    }
   ],
   "source": [
    "from test import test\n",
    "\n",
    "test(PathPlanner)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Questions\n",
    "\n",
    "**Instructions**  Answer the following questions in your own words. We do not you expect you to know all of this knowledge on the top of your head. We expect you to do research and ask question. However do not merely copy and paste the answer from a google or stackoverflow. Read the information and understand it first. Then use your own words to explain the answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "- How would you explain A-Star to a family member(layman)?\n",
    "\n",
    "** ANSWER **: When taking a route, we can have multiple options and each might have upsides and downsides. Some routes might have shorter distance to travel but cost more time and money due to heavy traffic and other routes might be longer path but faster. We want to choose the best route and this is where A-Star search comes in. A-Star does not actually know or care about how these costs or distances are decided, but A-Star already receives the cost (or distance) between every pair of neighbor nodes, and tries to find the minimum cost path from the start to the goal.\n",
    "\n",
    "> In this particular problem that involves a road map, it can be the fuel cost, the physical distance, the time that takes to go from one node to its neighbor, a combination of all or some of these costs, or any other thing. The **heuristic cost estimation** is used to orient the search: i.e. to avoid exploring as many nodes as possible, **reducing computational costs**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "- How does A-Star search algorithm differ from Uniform cost search? What about Best First search?\n",
    "\n",
    "** ANSWER **: Both **Best First Search**, and **Uniform cost Search** tries to get the cheapest path, but the difference is in heuristic function. The **best First Search** is informed search(with heuristic function: estimating how close to goal each of the next states will be from the current state) while **Uniform cost Search** is uninformed search so does not use the heuristic function. However, **Best First Search** differ from **A-Star Search** as **A-Star** visits next state based on heristics **f(n) = h + g** where h component is same heuristics applied in Best first search but **g component is path from the initial state to the particular state**; therefore, it doesn't chooses next state only with lowest heuristics value but one that gives lowest value when considering it's heuristics and cost of getting to that state.\n",
    "\n",
    "> The main differences among all three algorithms are about **what kind of information is used** during the search, and the guarantees about finding the optimal solution:\n",
    "- https://stackoverflow.com/questions/44151713/what-is-the-difference-between-uniform-cost-search-and-best-first-search-methods\n",
    "- https://stackoverflow.com/questions/34244452/whats-the-difference-between-best-first-search-and-a-search\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "- What is a heuristic?\n",
    "\n",
    "** ANSWER **: It's the distance estimation to our destination "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "- What is a consistent heuristic?\n",
    "\n",
    "** ANSWER **: **h_distance(current, goal)** <= g_cost(current, neighbor) + h_distance(neighbor, goal)\n",
    "- The estimated distance (from current state to the destination) is less than or equal to the cost (from current state to a neighbor node) plus the estimated distance (from its neighbor node to the destination)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "- What is a admissible heuristic? \n",
    "\n",
    "** ANSWER **: h(current, goal) <= Cost-to-goal \n",
    "- Some heuristic functions are admissible when it never overestimates the cost of reaching the destination. Its estimated cost is never more than the actual cost(from current state to the goal). If it overestimate the cost, the algorithm  would not explore the path and try to find another path to the goal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "- ___ admissible heuristic are consistent.\n",
    "*CHOOSE ONE*\n",
    "    - All\n",
    "    - Some\n",
    "    - None\n",
    "    \n",
    "** ANSWER **: Some"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "- ___ Consistent heuristic are admissible.\n",
    "*CHOOSE ONE*\n",
    "    - All\n",
    "    - Some\n",
    "    - None\n",
    "    \n",
    "** ANSWER **: All"
   ]
  }
 ],
 "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.5.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}