A2 Iterative-Deepening Search.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Assignment 2: Iterative-Deepening Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Maxwell You*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook, I have implemented the iterative-deepening search (IDS) algorithm used for uninformed searches. For this assignment, I had to apply IDS to the 8-puzzle and a puzzle of my choice: the pegboard puzzle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iterative Deepening and Depth Limited Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "IDS uses depth limited search (DLS) to search the game states. The signatures of the IDS algorithm are as follows:\n",
    "\n",
    "  * `iterativeDeepeningSearch(startState, actionsF, takeActionF, goalState, goalTestF, maxDepth)`\n",
    "  * `depthLimitedSearch(startState, actionsF, takeActionF, goalState, goalTestF, depthLimit)`\n",
    "  \n",
    "`depthLimitedSearch` is called by `iterativeDeepeningSearch` with `depthLimit`s of $0, 1, \\ldots, $ `maxDepth`. Both must return either the solution path as a list of states, or the strings `cutoff` or `failure`.  `failure` signifies that all states were searched and the goal was not found. \n",
    "\n",
    "Each receives the arguments\n",
    "\n",
    "  * the starting state, \n",
    "  * a function `actionsF` that is given a state and returns a list of valid actions from that state,\n",
    "  * a function `takeActionF` that is given a state and an action and returns the new state that results from applying the action to the state,\n",
    "  * the goal state,\n",
    "  * a function `goalTestF` that is given a state and the goal state and returns `True` if the state satisfies the goal, and\n",
    "  * either a `depthLimit` for `depthLimitedSearch`, or `maxDepth` for `iterativeDeepeningSearch`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solving the 8-puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The state of the puzzle is represented as a list of integers. 0 represents the empty position.\n",
    "\n",
    "Functions for the 8-puzzle are the following:\n",
    "\n",
    "  * `findBlank_8p(state)`: return the row and column index for the location of the blank (the 0 value).\n",
    "  * `actionsF_8p(state)`: returns a list of up to four valid actions that can be applied in `state`. Actions are returned in the order `left`, `right`, `up`, `down`, though only if each one is a valid action.\n",
    "  * `takeActionF_8p(state, action)`: return the state that results from applying `action` in `state`.\n",
    "  * `printPath_8p(startState, goalState, path)`: print a solution path in a readable form.\n",
    "  \n",
    "**Disclaimer:** *When I say 'index' below, I mean the index of the number as it appears in the list.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Printing the state of the 8-puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I traverse the state one row at a time and print the numbers with a trailing whitespace, unless it is the last number in the row, then I just print it. If a 0 is found, a space is printed instead."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def printState_8p(state):\n",
    "    \"\"\"\n",
    "    Prints the state of the 8 puzzle as a 3x3 board given a state in the form of a list\n",
    "    :param state:\n",
    "    :return:\n",
    "    \"\"\"\n",
    "    for i in range(3):\n",
    "        if state[i] == 0:\n",
    "            if i == 2:\n",
    "                print(' ')\n",
    "                break\n",
    "            print('  ', end='') # print a space for 0 and a trailing space\n",
    "        elif i == 2:\n",
    "            print(state[i])\n",
    "        else:\n",
    "            print(state[i], end=' ')\n",
    "    for i in range(3, 6):\n",
    "        if state[i] == 0:\n",
    "            if i == 5:\n",
    "                print(' ')\n",
    "                break\n",
    "            print('  ', end='') # print a space for 0 and a trailing space\n",
    "        elif i == 5:\n",
    "            print(state[i])\n",
    "        else:\n",
    "            print(state[i], end=' ')\n",
    "    for i in range(6, 9):\n",
    "        if state[i] == 0:\n",
    "            if i == 8:\n",
    "                print(' ')\n",
    "                break\n",
    "            print('  ', end='') # print a space for 0 and a trailing space\n",
    "        elif i == 8:\n",
    "            print(state[i])\n",
    "        else:\n",
    "            print(state[i], end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Find the blank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finding which rows the numbers belonged to was simple. Finding the column they belonged in was a little trickier. Because this is a 3x3 puzzle, the only valid columns are `[0, 1, 2]`. The columns of the first three numbers (row 0) are just their respective indices (e.g. index 0 = column 0). \n",
    "\n",
    "To find the columns for numbers in indices 3-8, I first had to define the maximum index for each row. If a number was in row 1 (indices 3-5), their maximum index would be 5. If we subtract the index of the number from 5, we get an offset that we can subtract from the maximum column, 2, to find the column that number would occupy in the 8-puzzle.\n",
    "\n",
    "Example:\n",
    "\n",
    "    state = [1, 2, 3, 4, 0, 5, 6, 7, 8]\n",
    "    \n",
    "    Find blank\n",
    "    \n",
    "    Index of 0 = 4\n",
    "    \n",
    "    row = 1\n",
    "    \n",
    "    Maximum index for row 1 = 5\n",
    "    \n",
    "    col = 2 - (5 - 4)\n",
    "    \n",
    "    col = 1\n",
    "    \n",
    "    (row, col) of blank = (1, 1)\n",
    "    \n",
    "    1 2 3\n",
    "    4 0 5   # Indeed, the blank is at (1, 1)\n",
    "    6 7 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def findBlank_8p(state):\n",
    "    \"\"\"\n",
    "    Returns tuple with coordinates of blank\n",
    "    Assumes that there will be a blank (0) in the input list\n",
    "    :param state:\n",
    "    :return (row, col):\n",
    "    \"\"\"\n",
    "    row = -1\n",
    "    col = -1\n",
    "    for i in range(len(state)):\n",
    "        if i < 3 and state[i] == 0:\n",
    "                row = 0                # in 1st row if (0 <= index in list < 3)\n",
    "                col = i                # col is the offset within first 3 indices\n",
    "                break\n",
    "        elif i < 6 and state[i] == 0:\n",
    "                row = 1                # in 2nd row if (3 <= index in list < 6)\n",
    "                col = 2 - (5 - i)      # col is the offset within 3rd-5th indices\n",
    "                break\n",
    "        elif i < 9 and state[i] == 0:\n",
    "                row = 2                # in 3rd row if (6 <= index in list < 9)\n",
    "                col = 2 - (8 - i)      # col is the offset within 6th-8th indices\n",
    "                break\n",
    "    return (row, col)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### List the valid actions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A blank can only move left, right, up, or down. Some manipulation of row and col allowed me to find the valid actions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def actionsF_8p(state):\n",
    "    \"\"\"\n",
    "    Returns list of valid actions based on the position of the blank\n",
    "    Assumes a valid state with blank is provided\n",
    "    :param state:\n",
    "    :return actions:\n",
    "    \"\"\"\n",
    "    actions = []\n",
    "    row, col = findBlank_8p(state)\n",
    "    if 0 <= col - 1 < 3:\n",
    "        actions.append('left')\n",
    "    if 0 <= col + 1 < 3:\n",
    "        actions.append('right')\n",
    "    if 0 <= row - 1 < 3:\n",
    "        actions.append('up')\n",
    "    if 0 <= row + 1 < 3:\n",
    "        actions.append('down')\n",
    "\n",
    "    return actions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Executing a valid action"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to write `takeActionF_8p`, I wrote a helper function to find the index of the blank given the row and column of the blank in the hypothetical 2D gameboard. The function is called `blankIndexInList`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def blankIndexInList(row, col):\n",
    "    \"\"\"\n",
    "    Returns index of blank in the list based on its row, col in the gameboard\n",
    "    Assumes valid row, col are given\n",
    "    :param row: \n",
    "    :param col: \n",
    "    :return index: \n",
    "    \"\"\"\n",
    "    index = -1\n",
    "    if row == 0:\n",
    "        index = col\n",
    "    if row == 1:\n",
    "        index = 3 + col\n",
    "    if row == 2:\n",
    "        index = 6 + col\n",
    "    return index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using this helper, `takeActionF_8p` was much easier to write as I discovered ways to manipulate the index of the blank given what action was to be performed. For example, if the index of the blank is 1, then an action of 'down' would move the blank to index 4. Before we do that though, we have to make sure we move the value that will be swapped with the blank into the blank's position (so we don't lose its value).\n",
    "\n",
    "The `takeActionF_8p` function is defined below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def takeActionF_8p(state, action):\n",
    "    \"\"\"\n",
    "    Returns the modified state list by applying the action\n",
    "    Assumes only valid actions are given\n",
    "    :param state:\n",
    "    :param action:\n",
    "    :return state:\n",
    "    \"\"\"\n",
    "    stateCopy = state[:]  # copy state into a new list, so we dont modify the original\n",
    "    row, col = findBlank_8p(state)\n",
    "    if action == 'up':\n",
    "        moveFrom = blankIndexInList(row, col)  # index of blank in the list\n",
    "        stateCopy[moveFrom] = stateCopy[moveFrom - 3]  # swap blank with tile above\n",
    "        stateCopy[moveFrom - 3] = 0  # place blank in tile above\n",
    "\n",
    "    elif action == 'down':\n",
    "        moveFrom = blankIndexInList(row, col)  # index of blank in the list\n",
    "        stateCopy[moveFrom] = stateCopy[moveFrom + 3]  # swap blank with tile below\n",
    "        stateCopy[moveFrom + 3] = 0  # place blank in tile below\n",
    "\n",
    "    elif action == 'left':\n",
    "        moveFrom = blankIndexInList(row, col)  # index of blank in the list\n",
    "        stateCopy[moveFrom] = state[moveFrom - 1]  # swap blank with left tile\n",
    "        stateCopy[moveFrom - 1] = 0  # place blank in left tile\n",
    "\n",
    "    elif action == 'right':\n",
    "        moveFrom = blankIndexInList(row, col)  # index of blank in the list\n",
    "        stateCopy[moveFrom] = stateCopy[moveFrom + 1]  # swap blank with right tile\n",
    "        stateCopy[moveFrom + 1] = 0  # place blank in right tile\n",
    "    return stateCopy  # return updated state"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Depth Limited Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Depth limited search depth first searches the tree in a breadth-first-like manner. DLS runs DFS down a branch until the `depthLimit` is reached. When it reaches the `depthLimit`, it will backtrack to the last unexplored node and DFS down that branch to the `depthLimit`. When it begins to explore the new node, it no longer keeps the previous branch of nodes in memory, thereby providing the space benefit of DFS.\n",
    "\n",
    "Depth limited search on its own is not complete nor optimal (i.e. not guaranteed to find a solution or find the best one).\n",
    "\n",
    "It is not complete because choosing a depth limit *l* that is less than the depth *d* of the shallowest goal node (*l < d*) would lead it to find no solution.\n",
    "\n",
    "It is not optimal because if we choose *l > d*, then it could find a goal node at a depth below *d* that would be correct, but not the shortest path."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def depthLimitedSearch(state, goalState, actionsF, takeActionF, depthLimit):\n",
    "    if state == goalState:\n",
    "        return []\n",
    "    if depthLimit == 0:\n",
    "        return 'cutoff'\n",
    "\n",
    "    cutoffOccurred = False\n",
    "\n",
    "    for action in actionsF(state):\n",
    "        childState = takeActionF(state, action)\n",
    "        result = depthLimitedSearch(childState, goalState, actionsF, takeActionF, depthLimit - 1)\n",
    "        if result == 'cutoff':\n",
    "            cutoffOccurred = True\n",
    "        elif result is not 'failure':\n",
    "            result.insert(0, childState)\n",
    "            return result\n",
    "\n",
    "    if cutoffOccurred:\n",
    "        return 'cutoff'\n",
    "    else:\n",
    "        return 'failure'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iterative Deepening Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Iterative deepening search improves upon DLS by trying incremental max depths. In doing so, this search is both complete and optimal.\n",
    "\n",
    "It is complete, when the branching factor is finite, because it will search every level of the state space.\n",
    "\n",
    "It is optimal because it DLSs every level, so if a goal node is found, then we know that this is the shortest path to the goal node. If there were a shorter path to this goal node, it would have been found in the previous level or before this node on the same level."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def iterativeDeepeningSearch(startState, goalState, actionsF, takeActionF, maxDepth):\n",
    "    for depth in range(maxDepth):\n",
    "        result = depthLimitedSearch(startState, goalState, actionsF, takeActionF, depth)\n",
    "        if result is 'failure':\n",
    "            return 'failure'\n",
    "        if result is not 'cutoff':\n",
    "            result.insert(0, startState)\n",
    "            return result\n",
    "    return 'cutoff'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Printing the path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def printPath_8p(startState, goalState, path):\n",
    "    print('Path from')\n",
    "    printState_8p(startState)\n",
    "    print('  to')\n",
    "    printState_8p(goalState)\n",
    "    print('is ' + str(len(path)) + ' nodes long:')\n",
    "    print()\n",
    "    for p in path:\n",
    "        printState_8p(p)\n",
    "        print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are some example results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "startState = [1, 0, 3, 4, 2, 5, 6, 7, 8]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1   3\n",
      "4 2 5\n",
      "6 7 8\n"
     ]
    }
   ],
   "source": [
    "printState_8p(startState)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 1)"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findBlank_8p(startState)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['left', 'right', 'down']"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "actionsF_8p(startState)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 0, 5, 6, 7, 8]"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "takeActionF_8p(startState, 'down')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3\n",
      "4   5\n",
      "6 7 8\n"
     ]
    }
   ],
   "source": [
    "printState_8p(takeActionF_8p(startState, 'down'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "goalState = takeActionF_8p(startState, 'down')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "newState = takeActionF_8p(startState, 'down')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "newState == goalState"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 0, 3, 4, 2, 5, 6, 7, 8]"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "startState"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 1, 3, 4, 2, 5, 6, 7, 8],\n",
       " [1, 0, 3, 4, 2, 5, 6, 7, 8],\n",
       " [1, 2, 3, 4, 0, 5, 6, 7, 8]]"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "path = depthLimitedSearch(startState, goalState, actionsF_8p, takeActionF_8p, 3)\n",
    "path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that `depthLimitedSearch` result is missing the start state.  This is inserted by `iterativeDeepeningSearch`.\n",
    "\n",
    "But, when we try `iterativeDeepeningSearch` to do the same search, it finds a shorter path!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 0, 3, 4, 2, 5, 6, 7, 8], [1, 2, 3, 4, 0, 5, 6, 7, 8]]"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "path = iterativeDeepeningSearch(startState, goalState, actionsF_8p, takeActionF_8p, 3)\n",
    "path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'cutoff'"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "startState = [4, 7, 2, 1, 6, 5, 0, 3, 8]\n",
    "path = iterativeDeepeningSearch(startState, goalState, actionsF_8p, takeActionF_8p, 3)\n",
    "path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'cutoff'"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "startState = [4, 7, 2, 1, 6, 5, 0, 3, 8]\n",
    "path = iterativeDeepeningSearch(startState, goalState, actionsF_8p, takeActionF_8p, 5)\n",
    "path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sometimes, we can't reach the goal state from just any start state. We need a way to randomly generate a valid start state. The idea here is kind of like scrambling a Rubik's Cube from the solved state into a jumbled state, then solving it from there."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'left'"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random.choice(['left', 'right'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def randomStartState(goalState, actionsF, takeActionF, nSteps):\n",
    "    state = goalState\n",
    "    for i in range(nSteps):\n",
    "        state = takeActionF(state, random.choice(actionsF(state)))\n",
    "    return state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 8, 6, 7, 0]"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "startState = randomStartState(goalState, actionsF_8p, takeActionF_8p, 10)\n",
    "startState"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3, 4, 5, 8, 6, 7, 0],\n",
       " [1, 2, 3, 4, 5, 0, 6, 7, 8],\n",
       " [1, 2, 3, 4, 0, 5, 6, 7, 8]]"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "path = iterativeDeepeningSearch(startState, goalState, actionsF_8p, takeActionF_8p, 20)\n",
    "path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's print out the state sequence in a readable form."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3\n",
      "4 5 8\n",
      "6 7  \n",
      "\n",
      "1 2 3\n",
      "4 5  \n",
      "6 7 8\n",
      "\n",
      "1 2 3\n",
      "4   5\n",
      "6 7 8\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for p in path:\n",
    "    printState_8p(p)\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below, I use the `printPath_8p` function to print the solution path in a readable format."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Path from\n",
      "1 2 3\n",
      "4 5 8\n",
      "6 7  \n",
      "  to\n",
      "1 2 3\n",
      "4   5\n",
      "6 7 8\n",
      "is 3 nodes long:\n",
      "\n",
      "1 2 3\n",
      "4 5 8\n",
      "6 7  \n",
      "\n",
      "1 2 3\n",
      "4 5  \n",
      "6 7 8\n",
      "\n",
      "1 2 3\n",
      "4   5\n",
      "6 7 8\n",
      "\n"
     ]
    }
   ],
   "source": [
    "printPath_8p(startState, goalState, path)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solving the Pegboard puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Pegboard puzzle seems to be most commonly found in Cracker Barrel restuarants. It is played on a 5x5 triangular gameboard populated with 14 pins and an empty hole. A peg can effectively 'jump' over another peg into an empty hole to 'eat' that peg. The objective of the game is to move the pegs so that only one peg remains at the end.\n",
    "\n",
    "Example:\n",
    "\n",
    "        0                     1\n",
    "       1 1                   0 0\n",
    "      1 1 1       -->       0 0 0\n",
    "     1 1 1 1               0 0 0 0\n",
    "    1 1 1 1 1             0 0 0 0 0\n",
    "    \n",
    "In order to solve this puzzle, I will be thinking in terms of how the blank(s) can move and not the pegs themselves. This is similar to the logic used to solve the 8-puzzle. It is also worth noting that there are only four starting positions as any other starting position is a rotation of one of those four. Also, there are only four ending states possible. These observations were taken from: [Pegboard Puzzle Solution Page](http://pegboardgame.blogspot.com)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Helper functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* `printState_pb(state)`: print the state of the board\n",
    "* `printPath_pb(startState, goalState, path)`: print the solution path\n",
    "* `findBlank_pb(state)`: return a list of coordinates of every blank on the board\n",
    "* `coordToIndex(row, col)`: return an index into the state list based off the coordinates of the blank\n",
    "* `actionsF_pb(state)`: returns a list of coordinate, action pairs that contain all the valid actions for those blanks\n",
    "* `takeActionF_pb(state, action)`: returns the state of the board after taking the action\n",
    "\n",
    "**Note:** *I refer to empty holes on the pegboard as 'blanks'*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Coordinates of the board"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This contains a list of valid coordinates on the board. It will be used to check boundaries `actionsF_pb`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "pb = [(0, 0),\n",
    "      (1, 0), (1, 1),\n",
    "      (2, 0), (2, 1), (2, 2),\n",
    "      (3, 0), (3, 1), (3, 2), (3, 3),\n",
    "      (4, 0), (4, 1), (4, 2), (4, 3), (4, 4)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Printing the state of the board"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I padded the numbers to make the output look like a pegboard."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def printState_pb(state):\n",
    "    print('    {0}'.format(state[0]))\n",
    "    print('   {0} {1}'.format(state[1], state[2]))\n",
    "    print('  {0} {1} {2}'.format(state[3], state[4], state[5]))\n",
    "    print(' {0} {1} {2} {3}'.format(state[6], state[7], state[8], state[9]))\n",
    "    print('{0} {1} {2} {3} {4}'.format(state[10], state[11], state[12], state[13], state[14]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Printing the solution path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pretty much the same as the printPath of the 8-puzzle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def printPath_pb(startState, goalState, path):\n",
    "    # Assumes a valid solution path is provided (i.e. failure was not returned)\n",
    "    \n",
    "    print('Path from')\n",
    "    printState_pb(startState)\n",
    "    print('   to')\n",
    "    printState_pb(goalState)\n",
    "    print('is ' + str(len(path)) + ' nodes long:')\n",
    "    print()\n",
    "    for p in path:\n",
    "        printState_pb(p)\n",
    "        print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Find the blanks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similar thought process as finding blanks for the 8-puzzle. The pegboard had more rows and columns to check for."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def findBlank_pb(state):\n",
    "    \"\"\"\n",
    "    Return a list of coordinates (row, col) of every blank on the board\n",
    "    :param state:\n",
    "    :return blanks:\n",
    "    \"\"\"\n",
    "    blanks = []\n",
    "\n",
    "    # blanks are in a specific row depending on what range of indices blank is found in\n",
    "    for i in range(len(state)):\n",
    "        if i == 0 and state[i] == 0:    # blank in 0th row\n",
    "            row = 0\n",
    "            col = 0\n",
    "            blanks.append((row, col))\n",
    "            continue                    # look for next blank\n",
    "        elif i < 3 and state[i] == 0:\n",
    "            row = 1\n",
    "            col = 1 - (2 - i)\n",
    "            blanks.append((row, col))\n",
    "            continue\n",
    "        elif i < 6 and state[i] == 0:\n",
    "            row = 2\n",
    "            col = 2 - (5 - i)\n",
    "            blanks.append((row, col))\n",
    "            continue\n",
    "        elif i < 10 and state[i] == 0:\n",
    "            row = 3\n",
    "            col = 3 - (9 - i)\n",
    "            blanks.append((row, col))\n",
    "            continue\n",
    "        elif i < 15 and state[i] == 0:  # blank in 4th row\n",
    "            row = 4\n",
    "            col = 4 - (14 - i)\n",
    "            blanks.append((row, col))\n",
    "            continue\n",
    "    return blanks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Converting a coordinate to an index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The triangular nature of the board introduced some interesting patterns. For example, starting in row 0 and going down the left diagonal, indices would increase by 1, 2, 3, 4 depending on what row they were on. If you go down the left diagonal from row 2 to row 3, the indicies increase by 3 (e.g. index 4 --> index 7).\n",
    "\n",
    "Picture:\n",
    "\n",
    "           0\n",
    "         1   2\n",
    "       3   4  5\n",
    "      6  7  8  9\n",
    "    10 11 12 13 14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def coordToIndex(row, col):\n",
    "    \"\"\"\n",
    "    Returns an index into the state list based off the coordinates of the blank\n",
    "    Assumes a valid blank coordinate is given\n",
    "    :param row:\n",
    "    :param col:\n",
    "    :return index:\n",
    "    \"\"\"\n",
    "\n",
    "    index = -1              # location of blank in list\n",
    "\n",
    "    if row == 0:\n",
    "        index = 0\n",
    "    elif row == 1:\n",
    "        index = col + 1     # use column plus an offset to find index\n",
    "    elif row == 2:\n",
    "        index = col + 3\n",
    "    elif row == 3:\n",
    "        index = col + 6\n",
    "    else:                   # row is 4\n",
    "        index = col + 10\n",
    "    return index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Listing valid actions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The tricky part of running iterative deepening search on this puzzle was figuring out the valid actions.\n",
    "\n",
    "In the pegboard puzzle, the start state will only has one blank that can move. But as the blank moves, it opens up more blanks to move. For example, going from the start state to the next leaves two free blanks to move in the next step.\n",
    "\n",
    "With the 8-puzzle, I only had to record the valid actions of the single blank. With multiple blanks, **I had to record the valid moves for each blank.** This list of valid moves will be used in IDS to check what moves it should check next.\n",
    "\n",
    "Because of this, I implemented the valid actions as (coordinate, action) pairs. I use `findBlanks_pb` to find the positions of all the blanks. Then, I loop through each blank and add its coordinates and any valid moves into a list containing valid actions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def actionsF_pb(state):\n",
    "    \"\"\"\n",
    "    Returns a list of coordinate, action pairs that contain all the valid actions for those blanks\n",
    "    Assumes a valid state is given\n",
    "    :param state:\n",
    "    :return actions:\n",
    "    \"\"\"\n",
    "    actions = []\n",
    "    blanks = findBlank_pb(state)    # find coordinates of all blanks\n",
    "\n",
    "    for blank in blanks:\n",
    "        row, col = blank\n",
    "\n",
    "        if row in [0, 1]:  # if blank is in 0th or 1st row\n",
    "            if (row + 2, col) in pb and (state[coordToIndex(row + 1, col)] == 1\n",
    "                                         and state[coordToIndex(row + 2, col)] == 1):\n",
    "                actions.append((blank, 'l_diag_down'))\n",
    "            if (row + 2, col + 2) in pb and (state[coordToIndex(row + 1, col + 1)] == 1\n",
    "                                             and state[coordToIndex(row + 2, col + 2)] == 1):    # left diagonal down\n",
    "                actions.append((blank, 'r_diag_down'))\n",
    "\n",
    "        if row == 2:\n",
    "            if (row + 2, col) in pb and (state[coordToIndex(row + 1, col)] == 1\n",
    "                                         and state[coordToIndex(row + 2, col)] == 1):\n",
    "                actions.append((blank, 'l_diag_down'))\n",
    "            if (row + 2, col + 2) in pb and (state[coordToIndex(row + 1, col + 1)] == 1\n",
    "                                             and state[coordToIndex(row + 2, col + 2)] == 1):    # left diagonal down\n",
    "                actions.append((blank, 'r_diag_down'))\n",
    "            if (row - 2, col) in pb and (state[coordToIndex(row - 1, col)] == 1\n",
    "                                         and state[coordToIndex(row - 2, col)] == 1):\n",
    "                actions.append((blank, 'l_diag_up'))\n",
    "            if (row - 2, col - 2) in pb and (state[coordToIndex(row - 1, col - 1)] == 1\n",
    "                                             and state[coordToIndex(row - 2, col - 2)] == 1):\n",
    "                actions.append((blank, 'r_diag_up'))\n",
    "            if (row, col + 2) in pb and (state[coordToIndex(row, col + 1)] == 1\n",
    "                                         and state[coordToIndex(row, col + 2)] == 1):\n",
    "                actions.append((blank, 'r_horiz'))\n",
    "            if (row, col - 2) in pb and (state[coordToIndex(row, col - 1)] == 1\n",
    "                                         and state[coordToIndex(row, col - 2)] == 1):\n",
    "                actions.append((blank, 'l_horiz'))\n",
    "\n",
    "        if row in [3, 4]:\n",
    "            if (row - 2, col) in pb and (state[coordToIndex(row - 1, col)] == 1\n",
    "                                         and state[coordToIndex(row - 2, col)] == 1):\n",
    "                actions.append((blank, 'l_diag_up'))\n",
    "            if (row - 2, col - 2) in pb and (state[coordToIndex(row - 1, col - 1)] == 1\n",
    "                                             and state[coordToIndex(row - 2, col - 2)] == 1):\n",
    "                actions.append((blank, 'r_diag_up'))\n",
    "            if (row, col + 2) in pb and (state[coordToIndex(row, col + 1)] == 1\n",
    "                                         and state[coordToIndex(row, col + 2)] == 1):\n",
    "                actions.append((blank, 'r_horiz'))\n",
    "            if (row, col - 2) in pb and (state[coordToIndex(row, col - 1)] == 1\n",
    "                                         and state[coordToIndex(row, col - 2)] == 1):\n",
    "                actions.append((blank, 'l_horiz'))\n",
    "\n",
    "    return actions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Executing a valid action"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Executing an action is a matter of converting the coordinates into indices so that we can manipulate the state list accordingly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def takeActionF_pb(state, action):\n",
    "    \"\"\"\n",
    "    Returns the state of the board after taking the action\n",
    "    action comes in as a tuple of coordinates (e.g. (3, 2)) and an action (e.g. l_diag_up)\n",
    "    :param state:\n",
    "    :param action:\n",
    "    :return:\n",
    "    \"\"\"\n",
    "    stateCopy = state[:]    # copy state into a new list, so we dont modify the original\n",
    "    row, col = action[0]    # coordinates are the first part of action tuple\n",
    "    move = action[1]        # move to be taken is second part of actions tuple\n",
    "\n",
    "    if move == 'l_diag_down':\n",
    "        stateCopy[coordToIndex(row + 1, col)] = 0\n",
    "        stateCopy[coordToIndex(row + 2, col)] = 0\n",
    "        stateCopy[coordToIndex(row, col)] = 1\n",
    "\n",
    "    if move == 'r_diag_down':\n",
    "        stateCopy[coordToIndex(row + 1, col + 1)] = 0\n",
    "        stateCopy[coordToIndex(row + 2, col + 2)] = 0\n",
    "        stateCopy[coordToIndex(row, col)] = 1\n",
    "\n",
    "    if move == 'l_diag_up':\n",
    "        stateCopy[coordToIndex(row - 1, col)] = 0\n",
    "        stateCopy[coordToIndex(row - 2, col)] = 0\n",
    "        stateCopy[coordToIndex(row, col)] = 1\n",
    "\n",
    "    if move == 'r_diag_up':\n",
    "        stateCopy[coordToIndex(row - 1, col - 1)] = 0\n",
    "        stateCopy[coordToIndex(row - 2, col - 2)] = 0\n",
    "        stateCopy[coordToIndex(row, col)] = 1\n",
    "\n",
    "    if move == 'r_horiz':\n",
    "        stateCopy[coordToIndex(row, col + 1)] = 0\n",
    "        stateCopy[coordToIndex(row, col + 2)] = 0\n",
    "        stateCopy[coordToIndex(row, col)] = 1\n",
    "\n",
    "    if move == 'l_horiz':\n",
    "        stateCopy[coordToIndex(row, col - 1)] = 0\n",
    "        stateCopy[coordToIndex(row, col - 2)] = 0\n",
    "        stateCopy[coordToIndex(row, col)] = 1\n",
    "\n",
    "    return stateCopy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pegboard puzzle tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "startState = [0, 1, 1, 1, 1,\n",
    "              1, 1, 1, 1, 1,\n",
    "              1, 1, 1, 1, 1]\n",
    "startState"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    0\n",
      "   1 1\n",
      "  1 1 1\n",
      " 1 1 1 1\n",
      "1 1 1 1 1\n"
     ]
    }
   ],
   "source": [
    "printState_pb(startState)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "blank(s) at: [(0, 0)]\n"
     ]
    }
   ],
   "source": [
    "print('blank(s) at: {0}'.format(findBlank_pb(startState)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "valid action(s): [((0, 0), 'l_diag_down'), ((0, 0), 'r_diag_down')]\n"
     ]
    }
   ],
   "source": [
    "print('valid action(s): {0}'.format(actionsF_pb(startState)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "moving blank (0, 0) to (2, 0):\n",
      "    1\n",
      "   0 1\n",
      "  0 1 1\n",
      " 1 1 1 1\n",
      "1 1 1 1 1\n"
     ]
    }
   ],
   "source": [
    "print('moving blank (0, 0) to (2, 0):')\n",
    "printState_pb(takeActionF_pb(startState, ((0, 0), 'l_diag_down')))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Running some additional tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "test = [1, 1, 1, 0, 1,    # some random board state\n",
    "        1, 0, 0, 1, 1,\n",
    "        1, 1, 1, 0, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "blank(s) at: [(2, 0), (3, 0), (3, 1), (4, 3)]\n",
      "valid action(s) for: \n",
      "    1\n",
      "   1 1\n",
      "  0 1 1\n",
      " 0 0 1 1\n",
      "1 1 1 0 1\n",
      "[((2, 0), 'l_diag_up'), ((2, 0), 'r_horiz'), ((3, 1), 'l_diag_up'), ((3, 1), 'r_horiz'), ((4, 3), 'r_diag_up'), ((4, 3), 'l_horiz')]\n"
     ]
    }
   ],
   "source": [
    "print('blank(s) at: {0}'.format(findBlank_pb(test)))\n",
    "print('valid action(s) for: ')\n",
    "printState_pb(test)\n",
    "print('{0}'.format(actionsF_pb(test)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Now to search for a solution to this pegboard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are going to try to get from here:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    0\n",
      "   1 1\n",
      "  1 1 1\n",
      " 1 1 1 1\n",
      "1 1 1 1 1\n"
     ]
    }
   ],
   "source": [
    "printState_pb(startState)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "to here:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    1\n",
      "   0 0\n",
      "  0 0 0\n",
      " 0 0 0 0\n",
      "0 0 0 0 0\n"
     ]
    }
   ],
   "source": [
    "goalState = [1, 0, 0, 0, 0,\n",
    "             0, 0, 0, 0, 0,\n",
    "             0, 0, 0, 0, 0]\n",
    "printState_pb(goalState)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This takes a while! About a minute and a half."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "path = iterativeDeepeningSearch(startState, goalState, actionsF_pb, takeActionF_pb, 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Path from\n",
      "    0\n",
      "   1 1\n",
      "  1 1 1\n",
      " 1 1 1 1\n",
      "1 1 1 1 1\n",
      "   to\n",
      "    1\n",
      "   0 0\n",
      "  0 0 0\n",
      " 0 0 0 0\n",
      "0 0 0 0 0\n",
      "is 14 nodes long:\n",
      "\n",
      "    0\n",
      "   1 1\n",
      "  1 1 1\n",
      " 1 1 1 1\n",
      "1 1 1 1 1\n",
      "\n",
      "    1\n",
      "   0 1\n",
      "  0 1 1\n",
      " 1 1 1 1\n",
      "1 1 1 1 1\n",
      "\n",
      "    1\n",
      "   0 1\n",
      "  1 1 1\n",
      " 1 0 1 1\n",
      "1 1 0 1 1\n",
      "\n",
      "    1\n",
      "   1 1\n",
      "  0 1 1\n",
      " 0 0 1 1\n",
      "1 1 0 1 1\n",
      "\n",
      "    0\n",
      "   0 1\n",
      "  1 1 1\n",
      " 0 0 1 1\n",
      "1 1 0 1 1\n",
      "\n",
      "    0\n",
      "   0 0\n",
      "  1 0 1\n",
      " 0 1 1 1\n",
      "1 1 0 1 1\n",
      "\n",
      "    0\n",
      "   0 1\n",
      "  1 0 0\n",
      " 0 1 1 0\n",
      "1 1 0 1 1\n",
      "\n",
      "    0\n",
      "   0 1\n",
      "  1 0 0\n",
      " 0 1 1 0\n",
      "1 1 1 0 0\n",
      "\n",
      "    0\n",
      "   0 1\n",
      "  1 0 0\n",
      " 0 1 1 0\n",
      "1 0 0 1 0\n",
      "\n",
      "    0\n",
      "   0 1\n",
      "  0 0 0\n",
      " 0 0 1 0\n",
      "1 0 1 1 0\n",
      "\n",
      "    0\n",
      "   0 1\n",
      "  0 0 0\n",
      " 0 0 1 0\n",
      "1 1 0 0 0\n",
      "\n",
      "    0\n",
      "   0 1\n",
      "  0 0 0\n",
      " 0 0 1 0\n",
      "0 0 1 0 0\n",
      "\n",
      "    0\n",
      "   0 1\n",
      "  0 0 1\n",
      " 0 0 0 0\n",
      "0 0 0 0 0\n",
      "\n",
      "    1\n",
      "   0 0\n",
      "  0 0 0\n",
      " 0 0 0 0\n",
      "0 0 0 0 0\n",
      "\n"
     ]
    }
   ],
   "source": [
    "printPath_pb(startState, goalState, path)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's run another one!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "gs2 = [0, 0, 0, 0, 0,\n",
    "       0, 0, 0, 0, 0,\n",
    "       0, 0, 1, 0, 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "path = iterativeDeepeningSearch(startState, gs2, actionsF_pb, takeActionF_pb, 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Path from\n",
      "    0\n",
      "   1 1\n",
      "  1 1 1\n",
      " 1 1 1 1\n",
      "1 1 1 1 1\n",
      "   to\n",
      "    0\n",
      "   0 0\n",
      "  0 0 0\n",
      " 0 0 0 0\n",
      "0 0 1 0 0\n",
      "is 14 nodes long:\n",
      "\n",
      "    0\n",
      "   1 1\n",
      "  1 1 1\n",
      " 1 1 1 1\n",
      "1 1 1 1 1\n",
      "\n",
      "    1\n",
      "   0 1\n",
      "  0 1 1\n",
      " 1 1 1 1\n",
      "1 1 1 1 1\n",
      "\n",
      "    1\n",
      "   1 1\n",
      "  0 0 1\n",
      " 1 1 0 1\n",
      "1 1 1 1 1\n",
      "\n",
      "    1\n",
      "   1 1\n",
      "  1 0 1\n",
      " 0 1 0 1\n",
      "0 1 1 1 1\n",
      "\n",
      "    1\n",
      "   1 1\n",
      "  1 1 1\n",
      " 0 0 0 1\n",
      "0 0 1 1 1\n",
      "\n",
      "    1\n",
      "   0 1\n",
      "  0 1 1\n",
      " 1 0 0 1\n",
      "0 0 1 1 1\n",
      "\n",
      "    1\n",
      "   0 0\n",
      "  0 0 1\n",
      " 1 1 0 1\n",
      "0 0 1 1 1\n",
      "\n",
      "    1\n",
      "   0 1\n",
      "  0 0 0\n",
      " 1 1 0 0\n",
      "0 0 1 1 1\n",
      "\n",
      "    0\n",
      "   0 0\n",
      "  0 0 1\n",
      " 1 1 0 0\n",
      "0 0 1 1 1\n",
      "\n",
      "    0\n",
      "   0 0\n",
      "  0 0 1\n",
      " 0 0 1 0\n",
      "0 0 1 1 1\n",
      "\n",
      "    0\n",
      "   0 0\n",
      "  0 0 1\n",
      " 0 0 1 0\n",
      "0 1 0 0 1\n",
      "\n",
      "    0\n",
      "   0 0\n",
      "  0 0 0\n",
      " 0 0 0 0\n",
      "0 1 1 0 1\n",
      "\n",
      "    0\n",
      "   0 0\n",
      "  0 0 0\n",
      " 0 0 0 0\n",
      "0 0 0 1 1\n",
      "\n",
      "    0\n",
      "   0 0\n",
      "  0 0 0\n",
      " 0 0 0 0\n",
      "0 0 1 0 0\n",
      "\n"
     ]
    }
   ],
   "source": [
    "printPath_pb(startState, gs2, path)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reflection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It takes about about a minute to a few minutes for IDS to solve the pegboard puzzle depending on which start and goal states you define. Sometimes, you'll specify a goal state that can't be reached from that start state. I did not think of a better way to generate a start state from a goal state like was done above for the 8-puzzle. I ran an example from the blog post mentioned above that I knew was solvable. For another puzzle, I tried some other start and goal states and chose one that worked.\n",
    "\n",
    "When IDS fails, it takes a while for it to figure out it failed. For example, the start state:\n",
    "    \n",
    "        1\n",
    "       1 1\n",
    "      0 1 1\n",
    "     1 1 1 1\n",
    "    1 1 1 1 1\n",
    "    \n",
    "and the goal state:\n",
    "\n",
    "        0\n",
    "       0 0\n",
    "      0 0 0\n",
    "     0 0 0 0\n",
    "    0 0 1 0 0\n",
    "\n",
    "took ~6 minutes to terminate and when it did, 'failure' was returned. I ran this with a `maxDepth` input of `20`. In order to find the solution, I would have to increase the maxDepth, but since it is already taking ~6 minutes to get to this point, I did not try.\n",
    "\n",
    "I do not think iterative deepening search is the best algorithm to solve the pegboard puzzle. I believe it has to do with having multiple pegs that can move, and each peg having multiple moves as well. I think it leads to a really large branching factor that slows down the algorithm. While this is a problem that would affect most algorithms, I believe an informed search algorithm would probably solve this in faster time, or running a different uninformed search algorithm."
   ]
  }
 ],
 "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
}