Mau-A1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Assignment 1: Uninformed Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Josh Mau"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Breadth-first and depth-first are two algorithms for performing\n",
    "uninformed search---a search that does not use\n",
    "knowledge about the goal of the search."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Required Code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this jupyter notebook, I have implemented the following functions:\n",
    "\n",
    "  * `breadthFirstSearch(startState, goalState, successorsf, visited=None, queue=None, parentTree=None)` \n",
    "  * `depthFirstSearch(startState, goalState, successorsf, visited=None, path=None)`\n",
    "  * `getTree(parents, start, end, path=None)`\n",
    "  \n",
    "Each receives as arguments the starting state, the goal state, and a successors function.  `breadthFirstSearch` returns the breadth-first solution path as a list of states starting with the `startState` and ending with the `goalState`. `getTree` is used exclusively for the `breadthFirstSearch` function to find the path based on a reverse look up on a dictionary of node:parent called parentTree. `depthFirstSearch` returns the depth-first solution path using a recursive solution.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def breadthFirstSearch(start, end, successorsf, visited=None, queue=None, parentTree=None):\n",
    "\tif visited is None:\n",
    "\t\tvisited = []\n",
    "\tif queue is None:\n",
    "\t\tqueue = []\n",
    "\tif parentTree is None:\n",
    "\t\tparentTree = {}\n",
    "\t\t\n",
    "\tqueue.append(start)\n",
    "  \n",
    "\twhile queue:\n",
    "\t\t\n",
    "\t\t# Pop front of queue\n",
    "\t\tnode = queue.pop(0)\n",
    "\t\t\n",
    "\t\t# This node has now been visited\n",
    "\t\tvisited.append(node)\n",
    "\n",
    "\t\t# if node is target, we're done\n",
    "\t\tif node is end:\n",
    "\t\t\treturn getTree(parentTree, start, end)\n",
    "\n",
    "\t\t# if there are successors to this node, add each to the end of queue\n",
    "\t\tif successorsf(node):\n",
    "\t\t\tfor child in successorsf(node):\n",
    "\t\t\t\tif child not in visited:\n",
    "\t\t\t\t\tqueue.append(child)\n",
    "\t\t\t\tparentTree[child] = node\n",
    "\t\t\t\tif child is end:\n",
    "\t\t\t\t\treturn getTree(parentTree, start, end)\n",
    "\n",
    "def getTree(parents, start, end):\n",
    "\tpath = []\n",
    "\tcurr = end\n",
    "\twhile curr != start:\n",
    "\t\tpath.insert(0, curr)\n",
    "\t\tcurr = parents[curr]\n",
    "\tpath.insert(0,curr)\n",
    "\treturn path\n",
    "\n",
    "def depthFirstSearch(start, end, successorsf, visited=None, path=None):\n",
    "\tif visited is None:\n",
    "\t\tvisited = [start]\n",
    "\tif path is None:\n",
    "\t\tpath = []\n",
    "\t\n",
    "\tpath.append(start)\n",
    "\n",
    "\tif start is end:\n",
    "\t\treturn path\n",
    "\n",
    "\telse:\n",
    "\t\tif successorsf(start):\n",
    "\t\t\tfor child in successorsf(start):\n",
    "\t\t\t\tif child not in visited:\n",
    "\t\t\t\t\tvisited.append(child)\n",
    "\t\t\t\t\tcurrent_path = depthFirstSearch(child, end, successorsf, visited, path)\n",
    "\t\t\t\t\tif current_path:\n",
    "\t\t\t\t\t\treturn current_path\n",
    "\t\t\t\t\telse:\n",
    "\t\t\t\t\t\tpath.pop()\n",
    "\t\n",
    "\treturn None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is a simple example.  States are defined by lower case letters.  A dictionary stores a list of successor states for each state in the graph that has successors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "successors = {'a':  ['b', 'c', 'd'],\n",
    "              'b':  ['e', 'f', 'g'],\n",
    "              'c':  ['a', 'h', 'i'],\n",
    "              'd':  ['j', 'z'],\n",
    "              'e':  ['k', 'l'],\n",
    "              'g':  ['m'],\n",
    "              'k':  ['z']\n",
    "             }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import copy\n",
    "\n",
    "def successorsf(state):\n",
    "    return copy.copy(successors.get(state, []))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['k', 'l']"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "successorsf('e')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Breadth-first\n",
      "path from a to a is ['a']\n",
      "path from a to b is ['a', 'b', 'g', 'm']\n",
      "path from a to i is ['a', 'd', 'z']\n"
     ]
    }
   ],
   "source": [
    "print('Breadth-first')\n",
    "print('path from a to a is', breadthFirstSearch('a', 'a', successorsf))\n",
    "print('path from a to b is', breadthFirstSearch('a', 'm', successorsf))\n",
    "print('path from a to i is', breadthFirstSearch('a', 'z', successorsf))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Depth-first\n",
      "path from a to a is ['a']\n",
      "path from a to b is ['a', 'b', 'g', 'm']\n",
      "path from a to i is ['a', 'b', 'e', 'k', 'z']\n"
     ]
    }
   ],
   "source": [
    "print('Depth-first')\n",
    "print('path from a to a is', depthFirstSearch('a', 'a', successorsf))\n",
    "print('path from a to b is', depthFirstSearch('a', 'm', successorsf))\n",
    "print('path from a to i is', depthFirstSearch('a', 'z', successorsf))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Searching this graph:\n",
      " {'a': ['b'], 'b': ['c', 'd'], 'c': ['e'], 'd': ['f', 'i'], 'e': ['g', 'h', 'i']}\n",
      "Looking for path from a to b.\n",
      "20/20 points. Your breadthFirstSearch found correct solution path of ['a', 'b']\n",
      "20/20 points. Your depthFirstSearch found correct solution path of ['a', 'b']\n",
      "Looking for path from a to i.\n",
      "20/20 points. Your breadthFirstSearch found correct solution path of ['a', 'b', 'd', 'i']\n",
      "20/20 points. Your depthFirstSearch found correct solution path of ['a', 'b', 'c', 'e', 'i']\n",
      "\n",
      "cs440 Grade is 80/100\n",
      "Up to 20 more points will be given based on the qualty of your descriptions of the method and the results.\n"
     ]
    }
   ],
   "source": [
    "%run -i A1grader.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}