{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem Set 1: Uninformed Search\n",
    "\n",
    "**Release Date:** 23 January 2024\n",
    "\n",
    "**Due Date:** 23:59, 3 Febuary 2024"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview\n",
    "\n",
    "In class, we discussed a number of different uninformed search algorithms. In this problem set, we get some hands-on practice by implementing them to solve some simple puzzles. In particular, we investigate the Missionaries and Cannibals problem and the Pitcher Filling problem.\n",
    "\n",
    "Required Files:\n",
    "\n",
    "* ps1.py\n",
    "\n",
    "**Honour Code**: Note that plagiarism will not be condoned! You may discuss with your classmates and check the internet for references, but you MUST NOT submit code/report that is copied directly from other sources!\n",
    "\n",
    "**IMPORTANT**: While it is possible to write and run Python code directly in Jupyter notebook, we recommend that you do this Problem Set with an IDE using the `.py` file provided. An IDE will make debugging significantly easier."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Missionaries and Cannibals\n",
    "\n",
    "The Missionaries and Cannibals (MnC) problem is a classic river-crossing logic puzzle. It is not difficult to solve this problem by hand when we have 3 Missionaries and 3 Cannibals. However, the solution becomes less obvious when we generalize the problem to *m* Missionaries and *c* Cannibals where *m* and *c* are some positive integers.\n",
    "\n",
    "The Missionaries and Cannibals problem is usually stated as follows: *m* missionaries and *c* cannibals are on the right side of a river, along with a boat that can hold at most 2 people. Your goal is to find a way to get everyone to the other side, without ever leaving a group of missionaries in one place outnumbered by the cannibals in that location (or the missionaries will get eaten!). You can try it here: https://javalab.org/en/boat_puzzle_en/ to test your understanding of the problem. \n",
    "\n",
    "Some important points to note when solving this question:\n",
    "\n",
    "* If the number of missionaries is zero, it does not matter how many cannibals there are even though technically they outnumber the number of missionaries. \n",
    "* You need to have at least 1 person in the boat to row the boat from one side of the river to the other. \n",
    "* At all times, both sides of the river AND the boat must have either 0 missionaries or at least as many missionaries as cannibals."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1  - State Representation\n",
    "\n",
    "Propose a state representation for this problem if we want to formulate it as a search problem and define the corresponding actions.\n",
    "\n",
    "### Task 1.2  - Initial & Goal States\n",
    "\n",
    "What are the initial and goal states for the problem under your proposed representation?\n",
    "\n",
    "### Task 1.3  - Representation Invariant\n",
    "\n",
    "What is the invariant that your representation needs to satisfy? Explain how you will use this invariant when you implement search? \n",
    "\n",
    "### Task 1.4  - Which Search Algorithm Should We Pick?\n",
    "\n",
    "If we want to implement Tree Search to solve this problem, which **Tree Search** should we implement: BFS, DFS or Depth-Limited Search? Explain. You may make minor modifications to these algorithms if necessary to suit the problem.\n",
    "\n",
    "### Task 1.5  - Completeness and Optimality\n",
    "\n",
    "Derive a loose upper bound on the maximum number of valid states a game of $m$ missionaries and $c$ cannibals. Express your answer in terms of $m$ and $c$, for example, $(m+c)^{m+c}$.\n",
    "\n",
    "Using the above upper bound, how can you ensure that Tree Search **will always terminate**? In your proposed formulation, is your Tree Search (i) complete and/or (ii) optimal? Explain.\n",
    "\n",
    "### Task 1.6  - Implement Tree Search\n",
    "\n",
    "Implement the function `mnc_tree_search` with **Tree** Search using your proposed representation described in Tasks 1.1, 1.2 and 1.3. \n",
    "\n",
    "`mnc_tree_search` takes two integers $m$ and $c$, which are the numbers of missionaries and cannibals on one side of the river initially, and returns the solution to the problem as a tuple of steps. Each step is a tuple of two numbers $m$ and $c$, indicating the number of missionaries and cannibals on the boat respectively as the boat moves from one side of the river to another. The odd steps are for the boat moving from right to left and the even steps are for the boat moving from left to right, assuming that we are counting from step zero in the tuple. Note that $1 <= c + m <= 2$, i.e. you need to have at least one person in the boat to row the boat from one side of the river to the other.\n",
    "\n",
    "Note that your solution needs to be optimal.\n",
    "\n",
    "\n",
    "#### Worked Example\n",
    "\n",
    "Note that there are a **range** of possible solutions. This example is just one of them. Let us consider the case of 2 missionaries and 1 cannibal. One possible solution is as follows:\n",
    "- **Start:** 2 missionaries, 1 cannibal and the boat are on the LHS of the river\n",
    "- **Step 1:** 2 missionaries row the boat to the RHS of the river\n",
    "  \n",
    "   1 cannibal is on the LHS of the river. 2 missionaries and boat are on the RHS of the river\n",
    "   \n",
    "   **Note:** 1 cannibal and 0 missionaries on the LHS of the river is a valid state (0 missionaries is a valid state)\n",
    "- **Step 2:** 1 missionary rows the boat to the LHS of the river\n",
    "   \n",
    "   **Note:** 1 cannibal and 1 missionary on the LHS of the river is a valid state (no. of missionaries >= no. of cannibals)\n",
    "- **Step 3:** 1 cannibal and 1 missionary row the boat to the RHS of the river\n",
    "- **End:** 2 missionaries and 1 cannibal are on the RHS of the river\n",
    "\n",
    "Hence, the solution is `((2, 0), (1, 0), (1, 1))`.\n",
    "\n",
    "Hint: You may find data structures helpful for your implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mnc_tree_search(m, c):  \n",
    "    '''\n",
    "    Solution should be the action taken from the root node (initial state) to \n",
    "    the leaf node (goal state) in the search tree.\n",
    "\n",
    "    Parameters\n",
    "    ----------    \n",
    "    m: no. of missionaries\n",
    "    c: no. of cannibals\n",
    "    \n",
    "    Returns\n",
    "    ----------    \n",
    "    Returns the solution to the problem as a tuple of steps. Each step is a tuple of two numbers x and y, indicating the number of missionaries and cannibals on the boat respectively as the boat moves from one side of the river to another. If there is no solution, return False.\n",
    "    '''\n",
    "    # TODO: add your solution here and remove `raise NotImplementedError`\n",
    "    raise NotImplementedError\n",
    "\n",
    "\n",
    "# Test cases \n",
    "print(mnc_tree_search(2,1))     # ((2, 0), (1, 0), (1, 1))\n",
    "\n",
    "print(mnc_tree_search(2,2))     # ((1, 1), (1, 0), (2, 0), (1, 0), (1, 1))\n",
    "\n",
    "print(mnc_tree_search(3,3))     # ((1, 1), (1, 0), (0, 2), (0, 1), (2, 0), (1, 1), (2, 0), (0, 1), (0, 2), (1, 0), (1, 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.7 - Implement Graph Search\n",
    "\n",
    "Next, implement the function `mnc_graph_search` with **Graph** Search using your proposed representation described in 1.1, 1.2 and 1.3. `mnc_graph_search` takes two integers $m$ and $c$, which are the numbers of missionaries and cannibals on one side of the river initially, and returns the to the problem as a tuple of steps following the format in Task 1.5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mnc_graph_search(m,c):\n",
    "    '''\n",
    "    Graph search requires to deal with the redundant path: cycle or loopy path.\n",
    "    Modify the above implemented tree search algorithm to accelerate your AI.\n",
    "\n",
    "    Parameters\n",
    "    ----------    \n",
    "    m: no. of missionaries\n",
    "    c: no. of cannibals\n",
    "    \n",
    "    Returns\n",
    "    ----------    \n",
    "    Returns the solution to the problem as a tuple of steps. Each step is a tuple of two numbers x and y, indicating the number of missionaries and cannibals on the boat respectively as the boat moves from one side of the river to another. If there is no solution, return False.\n",
    "    '''\n",
    "    # TODO: add your solution here and remove `raise NotImplementedError`\n",
    "    raise NotImplementedError\n",
    "\n",
    "\n",
    "# Test cases \n",
    "print(mnc_graph_search(2,1))     # ((2, 0), (1, 0), (1, 1))\n",
    "\n",
    "print(mnc_graph_search(2,2))     # ((1, 1), (1, 0), (2, 0), (1, 0), (1, 1))\n",
    "\n",
    "print(mnc_graph_search(3,3))     # ((1, 1), (1, 0), (0, 2), (0, 1), (2, 0), (1, 1), (2, 0), (0, 1), (0, 2), (1, 0), (1, 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Task 1.8 - Tree vs Graph Search\n",
    "\n",
    "Evaluate the difference in performance between Tree Search and Graph Search by timing how long each piece of code takes to run for some configurations and report your results. \n",
    "\n",
    "Is Graph Search (i) complete and/or (ii) optimal in your proposed formulation? Explain."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pitcher Filling Problem\n",
    "\n",
    "You currently have 3 pitchers $P_1$, $P_2$ and $P_3$ with capacities $c_1$, $c_2$ and $c_3$ respectively, such that $0 < c_1 < c_2 < c_3$ where each capacity is a positive integer. You also have access to a well (unlimited supply of water). Your job is to determine a sequence of steps to measure out an amount of water $a$ in any of the pitchers, where $0<a \\leq c_3, a \\in \\mathbb{Z}_{+}$. \n",
    "\n",
    "<p align=\"center\">\n",
    "<img src=\"imgs/pitchers.jpg\">\n",
    "</p>\n",
    "\n",
    "In each step, you can do one of three things:\n",
    "* You can fill a pitcher $P_i$ to the brim; or\n",
    "* You can empty a pitcher $P_i$; or\n",
    "* You can pour water from pitcher $P_i$ to pitcher $P_j$.\n",
    "\n",
    "In the 3rd case, we will try to pour enough water from $P_i$ to $P_j$ to fill $P_j$\n",
    "**but not more**. For example, if $P_j$ is already full, then nothing happens. If the total amount of water in $P_i$ and $P_j$ is less than or equal to $c_j$, then all the water gets poured into $P_j$ and $P_i$ is emptied.\n",
    "\n",
    "### Task 2.1  - State Representation for Pitcher Problem\n",
    "\n",
    "Propose a state representation for this problem if we want to formulate it as a search problem and define the corresponding actions.\n",
    "\n",
    "### Task 2.2  - Initial & Goal States\n",
    "\n",
    "What are the initial and goal states for the problem under your proposed representation in Task 2.1?\n",
    "\n",
    "### Task 2.3  - Implement Pitcher Search\n",
    "\n",
    "Implement the function `pitcher_search` that can will solve the problem  **efficiently** (i.e. be mindful of your time and space complexity) using your representation in Tasks 2.1 and 2.2. `pitcher_search` takes in 4 integers integers $p_1$, $p_2$, $p_3$ and $a$, where $p_i$ are the capacities of the $i$-th pitcher and $a$ is the target amount of water, and return the answer as a tuple of steps. Each step is one of three strings:\n",
    "1. \"Fill $P_i$\"\n",
    "2. \"$P_i$ => $P_j$\"\n",
    "3. \"Empty $P_i$\"\n",
    "where $i$ is the label of the pitcher. If there is no solution, return `False`.\n",
    "\n",
    "Your solution here needs to be optimal as well.\n",
    "\n",
    "#### Worked Example\n",
    "\n",
    "Note that there are a **range** of possible solutions. This example is just one of them. Let us consider the case where $P_1 = 2$, $P_2 = 3$, $P_3 = 7$. Assume we want to measure $a = 6$. One possible solution is as follows:\n",
    "- **Start:** All 3 pitchers are empty\n",
    "- **Step 1:** Fill $P_2$\n",
    "- Now $P_2$ has 3 litres and $P_1$, $P_3$ have 0 litres\n",
    "- **Step 2:** Pour $P_2$ into $P_3$\n",
    "- Now $P_3$ has 3 litres and $P_1$, $P_2$ have 0 litres\n",
    "- **Step 3:** Fill $P_2$\n",
    "- Now $P_2$ has 3 litres, $P_3$ has 3 litres, and $P_1$ has 0 litres\n",
    "- **Step 4:** Pour $P_2$ into $P_3$\n",
    "- Now $P_3$ has 6 litres and $P_1$, $P_2$ have 0 litres\n",
    "\n",
    "Hence, the solution is `('Fill P2', 'P2=>P3', 'Fill P2', 'P2=>P3')`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pitcher_search(p1, p2, p3, a):\n",
    "    '''\n",
    "    Solution should be the action taken from the root node (initial state) to \n",
    "    the leaf node (goal state) in the search tree.\n",
    "\n",
    "    Parameters\n",
    "    ----------    \n",
    "    p1: capacity of pitcher 1\n",
    "    p2: capacity of pitcher 2\n",
    "    p3: capacity of pitcher 3\n",
    "    a: amount of water we want to measure\n",
    "    \n",
    "    Returns\n",
    "    ----------    \n",
    "    Returns the solution to the problem as a tuple of steps. Each step is a string: \"Fill Pi\", \"Empty Pi\", \"Pi=>Pj\". \n",
    "    If there is no solution, return False.\n",
    "    '''\n",
    "    # TODO: add your solution here and remove `raise NotImplementedError`\n",
    "    raise NotImplementedError\n",
    "\n",
    "\n",
    "# Test cases\n",
    "print(pitcher_search(2,3,4,1))  # ('Fill P2', 'P2=>P1')\n",
    "\n",
    "print(pitcher_search(1,4,9,7))  # ('Fill P3', 'P3=>P1', 'Empty P1', 'P3=>P1')\n",
    "\n",
    "print(pitcher_search(2,3,7,8))  # False"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.11 64-bit (microsoft store)",
   "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.10.11"
  },
  "vscode": {
   "interpreter": {
    "hash": "5bd82fe7d6960a8d360fa7f139d752acec6855dc3eced6eff166183e4ea63ebb"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
