First-Search-Program.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[11, 4, 5]"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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",
    "    # ----------------------------------------\n",
    "    closed = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]\n",
    "    closed[init[0]][init[1]] = 1    #reserved cell\n",
    "    path = [[' ' for row in range(len(grid[0]))] for col in range(len(grid))]\n",
    "    x = init[0]\n",
    "    y = init[1]\n",
    "    op = 0\n",
    "    open = [[op,x,y]]\n",
    "    \n",
    "    found = False    #goal is found \n",
    "    resign = False   #cant reach goal\n",
    "    while found is False and resign is False:\n",
    "        if len(open) == 0:\n",
    "            resign = True\n",
    "            return 'fail'\n",
    "        else:\n",
    "            open.sort()\n",
    "            open.reverse()\n",
    "            next = open.pop()\n",
    "            x = next[1]\n",
    "            y = next[2]\n",
    "            op = next[0]\n",
    "            if x ==goal[0] and y ==goal[1]:\n",
    "                found = True\n",
    "                path = next\n",
    "            else:\n",
    "                for i in range(len(delta)):\n",
    "                    a = x + delta[i][0]\n",
    "                    b = y + delta[i][1]  \n",
    "                    if (a>=0 and b>=0 and a<len(grid) and b<len(grid[0])):\n",
    "                        if closed[a][b] == 0 and grid[a][b] == 0:   #cell is not yet checked and there is no obstale\n",
    "                            op2 = op + cost\n",
    "                            open.append([op2,a,b])\n",
    "                            closed[a][b] = 1\n",
    "  \n",
    "    return path\n",
    "\n",
    "search(grid,init,goal,cost)\n",
    "\n",
    "\n",
    " \n",
    "          \n",
    "    # ----------------------------------------\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.12 ('base')",
   "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.9.12"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "e572caa66b9d49951af5480c4e65bd874b4d163b9e077ed4369f2912d83d117b"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}