05th_Nov_Recurrence Releation.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2398d036-8044-4be8-9dc5-e7a9e1e89ac9",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "3d09acd0-b50d-4bd5-ae92-5faf66f18f2f",
   "metadata": {},
   "source": [
    "Q.1 Can you explain the logic and working of the Tower of Hanoi algorithm by writing a Java program?\n",
    "How does the recursion work, and how are the movements of disks between rods accomplished?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "6667b962-1884-4a9c-ac4b-e795458659b1",
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (1123214801.py, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001b[1;36m  Cell \u001b[1;32mIn[11], line 1\u001b[1;36m\u001b[0m\n\u001b[1;33m    class TowerOfHanoi {\u001b[0m\n\u001b[1;37m                       ^\u001b[0m\n\u001b[1;31mSyntaxError\u001b[0m\u001b[1;31m:\u001b[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "class TowerOfHanoi {\n",
    "    // Recursive method to solve Tower of Hanoi\n",
    "    static void solveTowerOfHanoi(int n, char source, char auxiliary, char destination) {\n",
    "        if (n == 1) {\n",
    "            System.out.println(\"Move disk 1 from \" + source + \" to \" + destination);\n",
    "            return;\n",
    "        }\n",
    "        // Step 1: Move n-1 disks from source to auxiliary\n",
    "        solveTowerOfHanoi(n - 1, source, destination, auxiliary);\n",
    "        \n",
    "        // Step 2: Move the nth disk from source to deQstination\n",
    "        System.out.println(\"Move disk \" + n + \" from \" + source + \" to \" + destination);\n",
    "        \n",
    "        // Step 3: Move the n-1 disks from auxiliary to destination\n",
    "        solveTowerOfHanoi(n - 1, auxiliary, source, destination);\n",
    "    }\n",
    "\n",
    "    public static void main(String[] args) {\n",
    "        int n = 3; // Number of disks\n",
    "        solveTowerOfHanoi(n, 'A', 'B', 'C'); // A is source, B is auxiliary, C is destination\n",
    "    }\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7be40a09-e35c-45a8-b083-7ea568a34d54",
   "metadata": {},
   "source": [
    "Q.2 Given two strings word1 and word2, return the minimum number of operations required to convert word1\n",
    "to word2.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e905b73-7feb-4667-ad17-27fc10a5de75",
   "metadata": {},
   "source": [
    "Example 1:\n",
    "Input: word1 = \"horse\", word2 = \"ros\"\n",
    "Output: 3\n",
    "Explanation:\n",
    "horse -> rorse (replace 'h' with 'r')\n",
    "rorse -> rose (remove 'r')\n",
    "rose -> ros (remove 'e')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "b02ea10f-025b-4c5b-91ee-41e210487454",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "def min_distance(word1, word2):\n",
    "    m, n = len(word1), len(word2)\n",
    "    dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    " \n",
    "    for i in range(m + 1):\n",
    "        dp[i][0] = i\n",
    "    for j in range(n + 1):\n",
    "        dp[0][j] = j\n",
    " \n",
    "    for i in range(1, m + 1):\n",
    "        for j in range(1, n + 1):\n",
    "            if word1[i - 1] == word2[j - 1]:\n",
    "                dp[i][j] = dp[i - 1][j - 1]\n",
    "            else:\n",
    "                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1\n",
    "\n",
    "    return dp[m][n]\n",
    " \n",
    "word1 = \"horse\"\n",
    "word2 = \"ros\"\n",
    "output = min_distance(word1, word2)\n",
    "print(output)   "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46d25be2-3424-40f1-a226-0d4091b73df6",
   "metadata": {},
   "source": [
    "Example 2:\n",
    "Input: word1 = \"intention\", word2 = \"execution\"\n",
    "Output: 5\n",
    "Explanation:\n",
    "intention -> inention (remove 't')\n",
    "inention -> enention (replace 'i' with 'e')\n",
    "enention -> exention (replace 'n' with 'x')\n",
    "exention -> exection (replace 'n' with 'c')\n",
    "exection -> execution (insert 'u')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "54b2b558-8d41-423f-a222-a8a0295e21e2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "def min_distance(word1, word2):\n",
    "    m, n = len(word1), len(word2)\n",
    "    dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "    # Base cases\n",
    "    for i in range(m + 1):\n",
    "        dp[i][0] = i   \n",
    "    for j in range(n + 1):\n",
    "        dp[0][j] = j   \n",
    "    for i in range(1, m + 1):\n",
    "        for j in range(1, n + 1):\n",
    "            if word1[i - 1] == word2[j - 1]:\n",
    "                dp[i][j] = dp[i - 1][j - 1]  \n",
    "            else:\n",
    "                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1\n",
    "\n",
    "    return dp[m][n]\n",
    " \n",
    "word1 = \"intention\"\n",
    "word2 = \"execution\"\n",
    "output = min_distance(word1, word2)\n",
    "print(output)  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "75104c1f-f09f-41b7-98aa-017a88481a6c",
   "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.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}