08 Water Jug Problem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2ddb37f4",
   "metadata": {},
   "source": [
    "## Water Jug Problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "e38a3a7d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "Enter the capacity of Jug 1:  2\n",
      "Enter the capacity of Jug 2:  5\n",
      "Enter the goal state:  3\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Solution Found\n",
      "\n",
      "  j1    j2        action\n",
      "======================================\n",
      "   0    0      Fill Jug 2\n",
      "   0    5      Pour Jug 2 into Jug 1\n",
      "   2    3      Final State\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "def waterJugProblem(cap1, cap2, target):\n",
    "    # Initialize the starting state of both jugs and the queue for BFS\n",
    "    queue = deque([(0, 0, [])])  # Both jugs start empty\n",
    "    visited = set()  # To track visited states\n",
    "\n",
    "    while queue:\n",
    "        j1, j2, actions = queue.popleft()  # Get the current state\n",
    "        \n",
    "        if j1 == target or j2 == target:    # If target is reached, return the sequence of actions\n",
    "            return actions + [(j1, j2, 'Final State')]\n",
    "\n",
    "        state = (j1, j2)\n",
    "        if state in visited:\n",
    "            continue          # Skip if the state has been visited\n",
    "        visited.add(state)        # Mark the current state as visited\n",
    "\n",
    "        # List of all possible actions and resulting states\n",
    "        possible_actions = [\n",
    "            (cap1, j2, \"Fill Jug 1\"),\n",
    "            (j1, cap2, \"Fill Jug 2\"),\n",
    "            (0, j2, \"Empty Jug 1\"),\n",
    "            (j1, 0, \"Empty Jug 2\"),\n",
    "            (max(0, j1 - (cap2 - j2)), min(cap2, j2 + j1), \"Pour Jug 1 into Jug 2\"),\n",
    "            (min(cap1, j1 + j2), max(0, j2 - (cap1 - j1)), \"Pour Jug 2 into Jug 1\"),\n",
    "        ]\n",
    "\n",
    "        # Enqueue all valid next states\n",
    "        for new_j1, new_j2, action in possible_actions:\n",
    "            if (new_j1, new_j2) not in visited:\n",
    "                queue.append((new_j1, new_j2, actions + [(j1, j2, action)]))      # Add new state with actions\n",
    "\n",
    "    return None     # Return None if no solution is found\n",
    "\n",
    "# Input values for the problem\n",
    "cap1 = int(input(\"Enter the capacity of Jug 1: \"))\n",
    "cap2 = int(input(\"Enter the capacity of Jug 2: \"))\n",
    "goal = int(input(\"Enter the goal state: \"))\n",
    "\n",
    "# Find and print the solution\n",
    "result = waterJugProblem(cap1, cap2, goal)\n",
    "if result:\n",
    "    print('\\nSolution Found\\n')\n",
    "    print('  j1    j2        action')\n",
    "    print('======================================')\n",
    "    for j1, j2, action in result:\n",
    "        print(f'   {j1}    {j2}      {action}')\n",
    "else:\n",
    "    print('No solutions Found')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ed68e21d-1e32-4eaa-8496-a32198cd3dda",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.12.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}