Recursion Assignment.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d05b52f5-1e7b-4509-878a-1da3b90fd99e",
   "metadata": {},
   "source": [
    "### Q.1 Can you explain the logic and working of the Tower of Hanoi algorithm by writing a Python program? How does the recursion work, and how are the movements of disks between rods accomplished? \n",
    "Number of disk = 3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2097d338-a2ec-4ad0-9ae8-c25e6dfef0b2",
   "metadata": {},
   "source": [
    "<b><u>TOWER OF HANOI</u></b><br>\n",
    "- Only one disk can be moved at a time.\n",
    "- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.\n",
    "- No disk may be placed on top of a smaller disk."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "4ae8ff01-6f92-4171-9564-9b08fb41f3e3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Move disk 1 from A to C\n",
      "Move disk 2 from A to B\n",
      "Move disk 1 from C to B\n",
      "Move disk 3 from A to C\n",
      "Move disk 1 from B to A\n",
      "Move disk 2 from B to C\n",
      "Move disk 1 from A to C\n"
     ]
    }
   ],
   "source": [
    "def tower_of_hanoi(n, source_rod, auxiliary_rod, destination_rod):\n",
    "    if n == 1:\n",
    "        # If there is only one disk, move it from the source rod to the destination rod\n",
    "        print(f\"Move disk 1 from {source_rod} to {destination_rod}\")\n",
    "        return\n",
    "    else:\n",
    "        # Move n-1 disks from source to auxiliary rod\n",
    "        tower_of_hanoi(n - 1, source_rod, destination_rod, auxiliary_rod)\n",
    "\n",
    "        # Move the nth disk from source to destination rod\n",
    "        print(f\"Move disk {n} from {source_rod} to {destination_rod}\")\n",
    "\n",
    "        # Move n-1 disks from auxiliary rod to destination rod\n",
    "        tower_of_hanoi(n - 1, auxiliary_rod, source_rod, destination_rod)\n",
    "\n",
    "# Example usage:\n",
    "tower_of_hanoi(3, 'A', 'B', 'C')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af1b0d92-ab09-4422-998d-8d386628bbbd",
   "metadata": {},
   "source": [
    "### Q.2 Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: word1 = \"horse\", word2 = \"ros\"\n",
    "\n",
    "Output: 3\n",
    "\n",
    "Explanation:\n",
    "\n",
    "- horse -> rorse (replace 'h' with 'r')\n",
    "- rorse -> rose (remove 'r')\n",
    "- rose -> ros (remove 'e')\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: word1 = \"intention\", word2 = \"execution\"\n",
    "\n",
    "Output: 5\n",
    "\n",
    "Explanation:\n",
    "\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')tion (insert 'u')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "2aa34f46-d849-40cf-b391-4fa4b19f2226",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "def min_distance_recursive(word1, word2, i, j):\n",
    "    # Base cases\n",
    "    if i == len(word1):\n",
    "        return len(word2) - j  # If word1 is empty, insert the remaining characters of word2\n",
    "    if j == len(word2):\n",
    "        return len(word1) - i  # If word2 is empty, delete the remaining characters of word1\n",
    "\n",
    "    # If the current characters are the same, no operation needed\n",
    "    if word1[i] == word2[j]:\n",
    "        return min_distance_recursive(word1, word2, i + 1, j + 1)\n",
    "\n",
    "    # Otherwise, consider three operations and find the minimum\n",
    "    insert = 1 + min_distance_recursive(word1, word2, i, j + 1)  # Insert\n",
    "    delete = 1 + min_distance_recursive(word1, word2, i + 1, j)  # Delete\n",
    "    replace = 1 + min_distance_recursive(word1, word2, i + 1, j + 1)  # Replace\n",
    "\n",
    "    return min(insert, delete, replace)\n",
    "\n",
    "# Example usage:\n",
    "word1_example = \"horse\"\n",
    "word2_example = \"ros\"\n",
    "result_example = min_distance_recursive(word1_example, word2_example, 0, 0)\n",
    "print(result_example)  # Output: 3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "3e979f05-3267-4af6-adda-7e4acf33de0f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "word1_example = \"intention\"\n",
    "word2_example = \"execution\"\n",
    "result_example = min_distance_recursive(word1_example, word2_example, 0, 0)\n",
    "print(result_example)  # Output: 3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76c4d725-3ba4-4470-91c3-2dbe1c691fca",
   "metadata": {},
   "source": [
    "### Q. 3 Print the max value of the array [ 13, 1, -3, 22, 5]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "c26fc72d-54c5-416d-bd9c-24995a9992ce",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "22\n"
     ]
    }
   ],
   "source": [
    "def maxValue(arr, n):\n",
    "    \n",
    "    if n == 1:\n",
    "        return arr[0]\n",
    "    return max(arr[n-1], maxValue(arr, n-1))\n",
    "\n",
    "arr = [ 13, 1, -3, 22, 5]\n",
    "n = len(arr)\n",
    "print(maxValue(arr, n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3deaeb0-5d27-42d2-a4c4-a22c489f2eb7",
   "metadata": {},
   "source": [
    "### Q.4 Find the sum of the values of the array [92, 23, 15, -20, 10].\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "272aa214-cd25-4996-ad1c-b85ebe3dd74c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "120\n"
     ]
    }
   ],
   "source": [
    "def sum_element(arr, n):\n",
    "    if n <= 0:\n",
    "        return 0\n",
    "    return sum_element(arr, n-1) + arr[n-1]\n",
    "\n",
    "arr = [92, 23, 15, -20, 10]\n",
    "n = len(arr)\n",
    "print(sum_element(arr, n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "768b9637-b495-4ad0-b7b6-e0a22101663a",
   "metadata": {},
   "source": [
    "### Q.5 Given a number n. Print if it is an armstrong number or not.An armstrong number is a number if the sum of every digit in that number raised to the power of total digits in that number is equal to the number.\n",
    "\n",
    "Example : 153 = 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153 hence 153 is an armstrong number. (Easy)\n",
    "\n",
    "Input1 : 153\n",
    "\n",
    "Output1 : Yes\n",
    "\n",
    "Input 2 : 134\n",
    "\n",
    "Output2 : No"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "372f21ff-62ab-423a-bbce-3267c96449c5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "Enter a number:  153\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "153 is an Armstrong number.\n"
     ]
    }
   ],
   "source": [
    "def isArmstrong(num, digits):\n",
    "    if num == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        digit = num % 10\n",
    "        sum = digit ** digits\n",
    "        return sum + isArmstrong(num // 10, digits)\n",
    "\n",
    "num = int(input(\"Enter a number: \"))\n",
    "num_digits = len(str(num))\n",
    "result = isArmstrong(num, num_digits)\n",
    "\n",
    "if result == num:\n",
    "    print(f\"{num} is an Armstrong number.\")\n",
    "else:\n",
    "    print(f\"{num} is not an Armstrong number.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c72eb49d-88b8-4d48-afaa-0127997f4477",
   "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.9.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}