4th_Nov_Recursion_Assignment.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e2b0dfb3",
   "metadata": {},
   "source": [
    "### Q.1 Can you explain the logic and working of the Tower of Hanoi algorithm by writing a Java program? How does the recursion work, and how are the movements of disks between rods accomplished?"
   ]
  },
  {
   "cell_type": "raw",
   "id": "46460b0d",
   "metadata": {},
   "source": [
    "-> The tower of hanoi problem involves three rods and a numbe of disks of different sizeswhich can slide onto any rod\n",
    "-> the puzzle starts with all the disks stacked in ascending order of size on one rod, with the smallest at the top and the largest at the bottom\n",
    "-> the objective is to move the entire stacs to antoher rod, obeying the following rules "
   ]
  },
  {
   "cell_type": "raw",
   "id": "00195d03",
   "metadata": {},
   "source": [
    "1) Only one disk can be moved at a time \n",
    "2) each move consists of taking the top disk from the one of the stacks and placing it onto antoher stack\n",
    "3) No disk may be placed on top of a smaller disk"
   ]
  },
  {
   "cell_type": "raw",
   "id": "27f4bf79",
   "metadata": {},
   "source": [
    "*) The recursive algorithm to slove the tower of hanoi problem can be broken down into three steps"
   ]
  },
  {
   "cell_type": "raw",
   "id": "e6aa6350",
   "metadata": {},
   "source": [
    "1) Move n-1 disks from the source rod to the auxiliary rod using the destination rod as the auxiliary.\n",
    "2) Move the nth disk from the source rod to the destination rod.\n",
    "3) Move the n-1 disks from the auxiliary rod to the destination rod using the source rod as the auxiliary."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1610fc99",
   "metadata": {},
   "source": [
    "# Example code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "494dc1ba",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Move disk 1 from rod A to rod C\n",
      "Move disk 2 from rod A to rod B\n",
      "Move disk 1 from rod C to rod B\n",
      "Move disk 3 from rod A to rod C\n",
      "Move disk 1 from rod B to rod A\n",
      "Move disk 2 from rod B to rod C\n",
      "Move disk 1 from rod A to rod C\n"
     ]
    }
   ],
   "source": [
    "def tower_of_hanoi(n, source, auxiliary, destination):\n",
    "    if n == 1:\n",
    "        print(f\"Move disk 1 from rod {source} to rod {destination}\")\n",
    "        return\n",
    "    tower_of_hanoi(n - 1, source, destination, auxiliary)\n",
    "    print(f\"Move disk {n} from rod {source} to rod {destination}\")\n",
    "    tower_of_hanoi(n - 1, auxiliary, source, destination)\n",
    "\n",
    "def main():\n",
    "    # Number of disks\n",
    "    n = 3  \n",
    "    tower_of_hanoi(n, 'A', 'B', 'C')\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    main()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b19743f3",
   "metadata": {},
   "source": [
    "#### Q.2 Given two strings word1 and word2, return the minimum number of operations required to convert word1\n",
    "#### to word2.\n",
    "#### 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')\n",
    "#### 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": 3,
   "id": "2dc358cb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "def minDistance(word1, word2):\n",
    "    def editDistanceHelper(i, j):\n",
    "        if i == len(word1):\n",
    "            return len(word2) - j\n",
    "        if j == len(word2):\n",
    "            return len(word1) - i\n",
    "\n",
    "        if word1[i] == word2[j]:\n",
    "            return editDistanceHelper(i + 1, j + 1)\n",
    "        \n",
    "        insert = 1 + editDistanceHelper(i, j + 1)\n",
    "        delete = 1 + editDistanceHelper(i + 1, j)\n",
    "        replace = 1 + editDistanceHelper(i + 1, j + 1)\n",
    "        \n",
    "        return min(insert, delete, replace)\n",
    "    \n",
    "    return editDistanceHelper(0, 0)\n",
    "\n",
    "# Test cases\n",
    "word1 = \"horse\"\n",
    "word2 = \"ros\"\n",
    "print(minDistance(word1, word2))  # Output: 3\n",
    "\n",
    "word1 = \"intention\"\n",
    "word2 = \"execution\"\n",
    "print(minDistance(word1, word2))  # Output: 5\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f8c5342",
   "metadata": {},
   "source": [
    "#### Q. 3 Print the max value of the array [ 13, 1, -3, 22, 5]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "11a81b01",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "22\n"
     ]
    }
   ],
   "source": [
    "def print_max(arr):\n",
    "    Max = float('-inf')\n",
    "    for i in arr:\n",
    "        if i > Max:\n",
    "            Max = i\n",
    "    return Max\n",
    "\n",
    "arr = [ 13, 1, -3, 22, 5]\n",
    "MaxOfArray = print_max(arr)\n",
    "print(MaxOfArray)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cdf3912b",
   "metadata": {},
   "source": [
    "#### Q.4 Find the sum of the values of the array [92, 23, 15, -20, 10]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "04ae9f23",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "120\n"
     ]
    }
   ],
   "source": [
    "def SumOfValue(arr):\n",
    "    Sum = 0\n",
    "    \n",
    "    for i in arr:\n",
    "        Sum = Sum+i\n",
    "        \n",
    "    return Sum\n",
    "\n",
    "\n",
    "arr =[92, 23, 15, -20, 10]\n",
    "\n",
    "ArraySum = SumOfValue(arr)\n",
    "print(ArraySum)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c87a8e76",
   "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "211f2e5f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "YES\n"
     ]
    }
   ],
   "source": [
    "def isArmstrongNumber(n):\n",
    "    num_str = str(n)\n",
    "    num_digits = len(num_str)\n",
    "    \n",
    "    armstrong_sum = sum(int(digit) ** num_digits for digit in num_str)\n",
    "    \n",
    "    if armstrong_sum == n:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "N = 153  \n",
    "result = isArmstrongNumber(N)\n",
    "if result:\n",
    "    print(\"YES\")\n",
    "else:\n",
    "    print(\"NO\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e70ec253",
   "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}