print_search_path.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "# -----------\n",
    "# User Instructions:\n",
    "#\n",
    "# Modify the the search function so that it returns\n",
    "# a shortest path as follows:\n",
    "# \n",
    "# [['>', 'v', ' ', ' ', ' ', ' '],\n",
    "#  [' ', '>', '>', '>', '>', 'v'],\n",
    "#  [' ', ' ', ' ', ' ', ' ', 'v'],\n",
    "#  [' ', ' ', ' ', ' ', ' ', 'v'],\n",
    "#  [' ', ' ', ' ', ' ', ' ', '*']]\n",
    "#\n",
    "# Where '>', '<', '^', and 'v' refer to right, left, \n",
    "# up, and down motions. Note that the 'v' should be \n",
    "# lowercase. '*' should mark the goal cell.\n",
    "#\n",
    "# You may assume that all test cases for this function\n",
    "# will have a path from init to goal.\n",
    "# ----------\n",
    "\n",
    "grid = [[0, 0, 1, 0, 0, 0],\n",
    "        [0, 0, 0, 0, 0, 0],\n",
    "        [0, 0, 1, 0, 1, 0],\n",
    "        [0, 0, 1, 0, 1, 0],\n",
    "        [0, 0, 1, 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\n",
    "    expand = [[-1 for row in range(len(grid[0]))] for col in range(len(grid))]\n",
    "    action = [[-1 for row in range(len(grid[0]))] for col in range(len(grid))]\n",
    "    \n",
    "    x = init[0]\n",
    "    y = init[1]\n",
    "    g = 0\n",
    "    \n",
    "    open = [[g, x, y]]\n",
    "    found = False\n",
    "    resign = False\n",
    "    count = 0\n",
    "    \n",
    "    while not found and not resign:\n",
    "        if len(open) == 0:\n",
    "            resign = True\n",
    "        else:\n",
    "            open.sort()\n",
    "            open.reverse()\n",
    "            next = open.pop()\n",
    "            x = next[1]\n",
    "            y = next[2]\n",
    "            g = next[0]\n",
    "            expand[x][y] = count\n",
    "            count += 1\n",
    "\n",
    "            \n",
    "            if x == goal[0] and y == goal[1]:\n",
    "                found = True\n",
    "            else:\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",
    "                            closed[x2][y2] = 1         \n",
    "                            action[x2][y2] = i      \n",
    "                            \n",
    "    policy = [[' ' for row in range(len(grid[0]))] for col in range(len(grid))]\n",
    "    x = goal[0]\n",
    "    y = goal[1]\n",
    "    policy[x][y] = \"*\"\n",
    "    \n",
    "    while x != init[0] or y != init[1]:\n",
    "        x2 = x - delta[action[x][y]][0]\n",
    "        y2 = y - delta[action[x][y]][1]\n",
    "        policy[x2][y2] = delta_name[action[x][y]]\n",
    "        if x == x2 and y == y2:\n",
    "            return policy\n",
    "        x = x2\n",
    "        y = y2\n",
    "    \n",
    "    return policy\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected:\n",
      "[['>', 'v', ' ', ' ', ' ', ' '],\n",
      "[' ', '>', '>', '>', '>', 'v'],\n",
      "[' ', ' ', ' ', ' ', ' ', 'v'],\n",
      "[' ', ' ', ' ', ' ', ' ', 'v'],\n",
      "[' ', ' ', ' ', ' ', ' ', '*']]\n"
     ]
    }
   ],
   "source": [
    "# Expected:\n",
    "expected = \\\n",
    "\"\"\"[['>', 'v', ' ', ' ', ' ', ' '],\n",
    "[' ', '>', '>', '>', '>', 'v'],\n",
    "[' ', ' ', ' ', ' ', ' ', 'v'],\n",
    "[' ', ' ', ' ', ' ', ' ', 'v'],\n",
    "[' ', ' ', ' ', ' ', ' ', '*']]\"\"\"\n",
    "print(\"Expected:\\n{}\".format(expected))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Actual:\n",
      "['>', 'v', ' ', ' ', ' ', ' ']\n",
      "[' ', '>', '>', '>', '>', 'v']\n",
      "[' ', ' ', ' ', ' ', ' ', 'v']\n",
      "[' ', ' ', ' ', ' ', ' ', 'v']\n",
      "[' ', ' ', ' ', ' ', ' ', '*']\n"
     ]
    }
   ],
   "source": [
    "# Actual:\n",
    "print(\"Actual:\")\n",
    "result = search(grid, init, goal, cost)\n",
    "for row in result:\n",
    "    print(row)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}