first_search.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[11, 4, 5]\n"
     ]
    }
   ],
   "source": [
    "# ----------\n",
    "# User Instructions:\n",
    "# \n",
    "# Define a function, search() that returns a list\n",
    "# in the form of [optimal path length, row, col]. For\n",
    "# the grid shown below, your function should output\n",
    "# [11, 4, 5].\n",
    "#\n",
    "# If there is no valid path from the start point\n",
    "# to the goal, your function should return the string\n",
    "# 'fail'\n",
    "# ----------\n",
    "\n",
    "# Grid format:\n",
    "#   0 = Navigable space\n",
    "#   1 = Occupied space\n",
    "\n",
    "\n",
    "grid = [[0, 0, 1, 0, 0, 0],\n",
    "        [0, 0, 1, 0, 0, 0],\n",
    "        [0, 0, 0, 0, 1, 0],\n",
    "        [0, 0, 1, 1, 1, 0],\n",
    "        [0, 0, 0, 0, 1, 0]]\n",
    "init = [0, 0]\n",
    "goal = [len(grid)-1, len(grid[0])-1]\n",
    "cost = 1\n",
    "\n",
    "delta = [[-1, 0], # go up\n",
    "         [ 0,-1], # go left\n",
    "         [ 1, 0], # go down\n",
    "         [ 0, 1]] # go right\n",
    "\n",
    "delta_name = ['^', '<', 'v', '>']\n",
    "\n",
    "def search(grid,init,goal,cost):\n",
    "    # open list elements are of the type:[g,x,y]\n",
    "    closed =  [[0 for row in range(len(grid[0]))] for col in range(len(grid[0]))]\n",
    "    closed[init[0]][init[1]] = 1\n",
    "    \n",
    "    x = init[0]\n",
    "    y = init[1]\n",
    "    g = 0\n",
    "    \n",
    "    open = [[g,x,y]]\n",
    "    \n",
    "    found  = False # flag thas is set when search complete\n",
    "    resign = False # flag set if we can't find expand\n",
    "    \n",
    "    #print 'initial open list:'\n",
    "    #for i in range(len(open)):\n",
    "    #  print '', open[i]\n",
    "    #print '---'\n",
    "    \n",
    "    while found is False and resign is False:\n",
    "        # check if we still have elements on the open list\n",
    "        if len(open)==0:\n",
    "            resign=True\n",
    "            print('fail')\n",
    "            #print '#### Search terminated without success'\n",
    "            \n",
    "        else:\n",
    "            # remove node from list\n",
    "            open.sort()\n",
    "            open.reverse()\n",
    "            next = open.pop()\n",
    "            #print 'take list item'\n",
    "            #print next\n",
    "            x = next[1]\n",
    "            y = next[2]\n",
    "            g = next[0]\n",
    "            \n",
    "            # check if we are done \n",
    "            if x == goal[0] and y == goal[1]:\n",
    "                found = True\n",
    "                print(next)\n",
    "                #print '#### Search successful'\n",
    "                \n",
    "            else:\n",
    "                # expand winnig element and add to new open list\n",
    "                for i in range(len(delta)):\n",
    "                    x2 = x+delta[i][0]\n",
    "                    y2 = y+delta[i][1]\n",
    "                    if x2>=0 and x2<len(grid) and y2>=0 and y2<len(grid[0]):\n",
    "                        if closed[x2][y2]==0 and grid[x2][y2]==0:\n",
    "                            g2=g+cost\n",
    "                            open.append([g2,x2,y2])\n",
    "                            #print 'append list item'\n",
    "                            #print [g2,x2,y2]\n",
    "                            closed[x2][y2]=1\n",
    "                            \n",
    "            #print 'new open list'\n",
    "            #for i in range(len(open)):\n",
    "            #  print ' ', open[i]\n",
    "            # print '...'\n",
    "                \n",
    "                \n",
    "search(grid,init,goal,cost)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 1, 1]\n",
      "search did not return anything for grid: [[0, 1], [0, 0]]\n"
     ]
    }
   ],
   "source": [
    "##### Do Not Modify ######\n",
    "\n",
    "import grader\n",
    "\n",
    "try:\n",
    "    response = grader.run_grader(search)\n",
    "    print(response)    \n",
    "    \n",
    "except Exception as err:\n",
    "    print(str(err))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe width=\"560\" height=\"315\" src=\"https://www.youtube.com/embed/cl8Kdkr4Gbg\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen></iframe>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "##### SOLUTION: Run this cell to watch the solution video ######\n",
    "from IPython.display import HTML\n",
    "HTML('<iframe width=\"560\" height=\"315\" src=\"https://www.youtube.com/embed/cl8Kdkr4Gbg\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen></iframe>')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}