AI - Lab 01 - State Space Search.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Artificial Intelligence — Lab — Exercise 01"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Session 1: State Space Search — Decantation Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 18 August 2020"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are given an 8-litre jar full of water and two empty jars of 5- and 3-litre capacity. You have\n",
    "to get exactly 4 litres of water in one of the jars. You can completely empty a jar into another jar\n",
    "with space or completely fill up a jar from another jar.\n",
    "1. Formulate the problem: Identify states, actions, initial state, goal state(s). Represent the\n",
    "   state by a 3-tuple. For example, the intial state state is (8,0,0). (4,1,3) is a goal state\n",
    "   (there may be other goal states also).\n",
    "   \n",
    "   \n",
    "2. Use a suitable data structure to keep track of the parent of every state. Write a function to\n",
    "   print the sequence of states and actions from the initial state to the goal state.\n",
    "\n",
    "\n",
    "3. Write a function next states(s) that returns a list of successor states of a given state s.\n",
    "\n",
    "\n",
    "4. Implement Breadth-First-Search algorithm to search the state space graph for a goal state\n",
    "   that produces the required sequence of pourings. Use a Queue as frontier that stores the\n",
    "   discovered states yet be explored. Use a dictionary for explored that is used to store the\n",
    "   explored states.\n",
    "\n",
    "\n",
    "5. Modify your program to trace the contents of the Queue in your algorithm. How many\n",
    "   states are explored by your algorithm?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_final_state(this_state):\n",
    "    \"\"\"Check whether the final state has been reached.\"\"\"\n",
    "    \n",
    "    if goal in this_state:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decant_jugs(i, j, present_state):\n",
    "    \"\"\"Decant from Jug i to Jug j and return a new state.\"\"\"\n",
    "    \n",
    "    present_state = list(present_state)\n",
    "    \n",
    "    if present_state[i] + present_state[j] >= jug_capacity[j]: #if Jug j's capacity will be exceeded, pour remaining to Jug i\n",
    "        total = present_state[i] + present_state[j]\n",
    "        present_state[j] = jug_capacity[j]\n",
    "        present_state[i] = total - present_state[j]\n",
    "    \n",
    "    else:                                                     #if Jug j's capacity will not be exceeded, empty Jug i into Jug j\n",
    "        present_state[j] += present_state[i]\n",
    "        present_state[i] = 0\n",
    "    \n",
    "    present_state = tuple(present_state)\n",
    "    \n",
    "    return present_state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_next_states(current_state):\n",
    "    \"\"\"Find the possible next states from the present state.\"\"\"\n",
    "    \n",
    "    next_states = []\n",
    "    \n",
    "    for i in range(jug_count):\n",
    "        for j in range(jug_count):\n",
    "            if i != j and current_state[i] != 0 and current_state[j] != jug_capacity[j]:\n",
    "                #To avoid the following:\n",
    "                #Pouring from Jug i to itself\n",
    "                #A case where Jug i is already empty\n",
    "                #A case where Jug j is already full\n",
    "                \n",
    "                next_state = decant_jugs(i, j, current_state)\n",
    "                \n",
    "                if next_state not in visited_states:\n",
    "                    parent_states[next_state] = current_state\n",
    "                    next_states.append(next_state)\n",
    "                    visited_states.append(next_state)\n",
    "    \n",
    "    return next_states"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def BFS():\n",
    "    \"\"\"Perform BFS on the state space to find the shallowest path.\"\"\"\n",
    "    \n",
    "    frontier = []   #Queue\n",
    "    present_state = initial_state\n",
    "    \n",
    "    frontier.append(initial_state)  \n",
    "    visited_states.append(initial_state)\n",
    "    \n",
    "    parent_states[present_state] = present_state  #Parent of the initial state is itself, as there are no states before it.\n",
    "    \n",
    "    while(frontier):   #Performing BFS\n",
    "        this_state = frontier[0]\n",
    "        explored_states.append(this_state)\n",
    "        \n",
    "        if is_final_state(this_state):\n",
    "            goal_states.append(this_state)\n",
    "        \n",
    "        next_states = find_next_states(this_state)\n",
    "        frontier = frontier + next_states\n",
    "        frontier.pop(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def path_tracer(parent_states, goal_state):\n",
    "    \"\"\"To trace the path from the goal state to the initial state.\"\"\"\n",
    "    \n",
    "    path = [goal_state]\n",
    "    current_state = goal_state \n",
    "    \n",
    "    while current_state != initial_state:   #Appending the parent states to path till the initial state is reached.\n",
    "        path.append(parent_states[current_state])\n",
    "        current_state = parent_states[current_state]\n",
    "        \n",
    "    return path[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_path(states):\n",
    "    \"\"\"Print all the visited states explored by the BFS Algorithm.\"\"\"\n",
    "    \n",
    "    print(\"-------------------------------------------------\")\n",
    "    print(\"|\\tJug 1\\t|\\tJug 2\\t|\\tJug 3\\t|\")\n",
    "    print(\"-------------------------------------------------\")\n",
    "    \n",
    "    for state in states:\n",
    "        print(\"|\\t{0} L\\t|\\t{1} L\\t|\\t{2} L\\t|\".format(state[0], state[1], state[2]))\n",
    "    \n",
    "    print(\"-------------------------------------------------\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Variables -- Change jug capacity & goal for different variations of the same problem\n",
    "jug_capacity = [8, 5, 3]\n",
    "goal = 4\n",
    "\n",
    "initial_state = (jug_capacity[0], 0, 0)\n",
    "goal_states = []\n",
    "jug_count = len(jug_capacity)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Data Structures\n",
    "parent_states = dict() #to trace back the path from the goal state to initial state once BFS is explored\n",
    "explored_states = []   #to keep track of states that have been explored by the BFS algorithm\n",
    "visited_states = []    #to keep track of states that have been found by the BFS algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def main():\n",
    "    \"\"\"Driver function to execute the Decantation problem.\"\"\"\n",
    "    print(\"\\t\\tDecantation Problem\\n\")\n",
    "    print(\"Initial State\\t\\t\\t\\t:\", initial_state)\n",
    "    \n",
    "    BFS()\n",
    "    print(\"\\nTotal no. of states explored by BFS\\t:\", len(explored_states))\n",
    "    print(\"\\nNo. of Goal States found\\t\\t:\", len(goal_states))\n",
    "    print(\"\\nGoal States found\\t\\t\\t:\", goal_states)\n",
    "    print(\"\\nDetails\\t\\t\\t\\t\\t:\\n\")\n",
    "    \n",
    "    for goal_state in goal_states:\n",
    "        print(\"\\nGoal State\\t\\t\\t\\t:\", goal_state)\n",
    "        path = path_tracer(parent_states, goal_state)\n",
    "        print(\"\\n\\nPath taken by the BFS Algorithm to reach the Goal State:\\n\")\n",
    "        print_path(path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\t\tDecantation Problem\n",
      "\n",
      "Initial State\t\t\t\t: (8, 0, 0)\n",
      "\n",
      "Total no. of states explored by BFS\t: 16\n",
      "\n",
      "No. of Goal States found\t\t: 3\n",
      "\n",
      "Goal States found\t\t\t: [(1, 4, 3), (4, 4, 0), (4, 1, 3)]\n",
      "\n",
      "Details\t\t\t\t\t:\n",
      "\n",
      "\n",
      "Goal State\t\t\t\t: (1, 4, 3)\n",
      "\n",
      "\n",
      "Path taken by the BFS Algorithm to reach the Goal State:\n",
      "\n",
      "-------------------------------------------------\n",
      "|\tJug 1\t|\tJug 2\t|\tJug 3\t|\n",
      "-------------------------------------------------\n",
      "|\t8 L\t|\t0 L\t|\t0 L\t|\n",
      "|\t3 L\t|\t5 L\t|\t0 L\t|\n",
      "|\t3 L\t|\t2 L\t|\t3 L\t|\n",
      "|\t6 L\t|\t2 L\t|\t0 L\t|\n",
      "|\t6 L\t|\t0 L\t|\t2 L\t|\n",
      "|\t1 L\t|\t5 L\t|\t2 L\t|\n",
      "|\t1 L\t|\t4 L\t|\t3 L\t|\n",
      "-------------------------------------------------\n",
      "\n",
      "Goal State\t\t\t\t: (4, 4, 0)\n",
      "\n",
      "\n",
      "Path taken by the BFS Algorithm to reach the Goal State:\n",
      "\n",
      "-------------------------------------------------\n",
      "|\tJug 1\t|\tJug 2\t|\tJug 3\t|\n",
      "-------------------------------------------------\n",
      "|\t8 L\t|\t0 L\t|\t0 L\t|\n",
      "|\t3 L\t|\t5 L\t|\t0 L\t|\n",
      "|\t3 L\t|\t2 L\t|\t3 L\t|\n",
      "|\t6 L\t|\t2 L\t|\t0 L\t|\n",
      "|\t6 L\t|\t0 L\t|\t2 L\t|\n",
      "|\t1 L\t|\t5 L\t|\t2 L\t|\n",
      "|\t1 L\t|\t4 L\t|\t3 L\t|\n",
      "|\t4 L\t|\t4 L\t|\t0 L\t|\n",
      "-------------------------------------------------\n",
      "\n",
      "Goal State\t\t\t\t: (4, 1, 3)\n",
      "\n",
      "\n",
      "Path taken by the BFS Algorithm to reach the Goal State:\n",
      "\n",
      "-------------------------------------------------\n",
      "|\tJug 1\t|\tJug 2\t|\tJug 3\t|\n",
      "-------------------------------------------------\n",
      "|\t8 L\t|\t0 L\t|\t0 L\t|\n",
      "|\t5 L\t|\t0 L\t|\t3 L\t|\n",
      "|\t5 L\t|\t3 L\t|\t0 L\t|\n",
      "|\t2 L\t|\t3 L\t|\t3 L\t|\n",
      "|\t2 L\t|\t5 L\t|\t1 L\t|\n",
      "|\t7 L\t|\t0 L\t|\t1 L\t|\n",
      "|\t7 L\t|\t1 L\t|\t0 L\t|\n",
      "|\t4 L\t|\t1 L\t|\t3 L\t|\n",
      "-------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "main()"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}