AI Lab - Exam - CAT4 - Paragraph Sort.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "AI - Lab Exam - CAT4 - Paragraph Sort.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyN4AQXHzDQXmk6dqZ0aWOhw",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/svishakan/Artificial-Intelligence/blob/master/AI%20Lab%20-%20Exam%20-%20CAT4%20-%20Paragraph%20Sort.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Y-X7vX4UiB6A"
      },
      "source": [
        "<h3> Question:- </h3>\n",
        "Given n paragraphs numbered from 1 to n, arrange them in the order of 1, 2, . . . , n where n ≤ 9. With\n",
        "the help of a clipboard, you can press Ctrl-X (cut) and Ctrl-V (paste) several times. You cannot cut twice\n",
        "before pasting, but you can cut several contiguous paragraphs at the same time and these paragraphs will\n",
        "later be pasted in order. What is the minimum number of steps required?\n",
        "<br><br>Example 1: Make [2, 4, 1, 5, 3, 6] sorted.\n",
        "<br>[2, 4, 1, 5, 3, 6] cut paragraph (1) and paste it before paragraph (2)\n",
        "<br>[1, 2, 4, 5, 3, 6] cut paragraph (3) and paste it before paragraph (4)\n",
        "<br>[1, 2, 3, 4, 5, 6] Minimum number of steps required = 2\n",
        "<br><br>Example 2: Make [(3, 4, 5), 1, 2] sorted.\n",
        "<br>[3, 4, 5, 1, 2] cut three paragraphs 3, 4, 5 at the same time and paste them after paragraph 2\n",
        "<br>[1, 2, 3, 4, 5] Minimum number of steps required = 1\n",
        "<br>This solution is not unique as we can have the following alternative answer:\n",
        "[3, 4, 5, 1, 2] cut two paragraphs 1, 2 at the same time and paste them before paragraph 3\n",
        "<br>[1, 2, 3, 4, 5] Minimum number of steps required = 1\n",
        "<br><br>Example 3: A trivial algorithm will process [5, 4, 3, 2, 1] as follows: [(5), 4, 3, 2, 1] → [(4), 3, 2, 1, 5] →\n",
        "[(3), 2, 1, 4, 5] → [(2), 1, 3, 4, 5] → [1, 2, 3, 4, 5] of total 4 cut-paste steps. \n",
        "<br>This is not optimal, as we can\n",
        "solve this instance in only 3 steps: [5, 4,(3, 2), 1] → [3,(2, 5), 4, 1] → [3, 4,(1, 2), 5] → [1, 2, 3, 4, 5].\n",
        "<br><br><br>\n",
        "1. Formulate the problem as a state-space search problem. Implement a program to solve the problem\n",
        "using best-first search algorithm. You can use suitable data structures available in Python. (25)\n",
        "(a) For each function, providee code for testing your function (Program with no testing code will\n",
        "get lesser points).\n",
        "<br><br>\n",
        "2. Modify your program to solve the problem using A* algorithm. Decide a suitable heuristic for the\n",
        "problem. (25)\n",
        "<br><br>\n",
        "(a) For each function, provide code for testing your function (Program with no testing code will\n",
        "get lesser points).\n",
        "(b) Give a measure of how much A* performs better than best-first search.\n",
        "<br>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pGNEJClL8l1H"
      },
      "source": [
        "\"\"\"\n",
        "Name:               S. Vishakan\n",
        "Register Number:    18 5001 196\n",
        "Class:              CSE - C\n",
        "\"\"\""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bcNt0DcUB-09"
      },
      "source": [
        "from collections import deque\n",
        "import heapq\n",
        "import math\n",
        "import random\n",
        "import time"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4vr1fY688pZr"
      },
      "source": [
        "class Sorter:\n",
        "    \"\"\"Class to encapsulate the problem state. \"\"\"\n",
        "    \n",
        "    def __init__(self, state, parent = None, depth = 0, is_back_cost = False):\n",
        "        self.n = len(state)\n",
        "        self.state = state\n",
        "        self.cost = self.heuristic()\n",
        "        self.depth = depth\n",
        "        self.is_back_cost = is_back_cost\n",
        "        self.parent = parent\n",
        "\n",
        "    def __str__(self):\n",
        "        return str(self.state)\n",
        "\n",
        "    def __lt__(self, other_state):\n",
        "        if not self.is_back_cost:\n",
        "            #A-star\n",
        "            return self.cost < other_state.cost \n",
        "        #BFS\n",
        "        return self.cost + self.depth < other_state.cost + other_state.depth\n",
        "\n",
        "    def heuristic(self):\n",
        "        cost = 0\n",
        "\n",
        "        for i in range(1, self.n):\n",
        "            if self.state[i] != self.state[i-1] + 1:\n",
        "                cost += 1\n",
        "            \n",
        "            if self.state[0] != 1:\n",
        "                cost += 1\n",
        "\n",
        "        return cost\n",
        "\n",
        "    def is_goal(self):\n",
        "        goal = sorted(self.state)\n",
        "\n",
        "        if goal == self.state:\n",
        "            return True\n",
        "\n",
        "        return False\n",
        "\n",
        "    def find_neighbors(self):\n",
        "        next_states = []\n",
        "\n",
        "        for left in range(self.n):\n",
        "            for right in range(left+1, self.n+1):\n",
        "                sublist = self.state[left:right]\n",
        "                oldlist = [x for x in self.state]\n",
        "\n",
        "                for i in range(right - 1, left - 1, -1):\n",
        "                    oldlist.pop(i)\n",
        "                \n",
        "                for i in range(len(oldlist) + 1):\n",
        "                    newlist = oldlist[:i] + sublist + oldlist[i:]\n",
        "\n",
        "                    if newlist != self.state and newlist not in next_states:\n",
        "                        next_states.append(newlist)\n",
        "                    \n",
        "        for i, state in enumerate(next_states):\n",
        "            next_states[i] = Sorter(state, self, self.is_back_cost, self.depth + 1)\n",
        "\n",
        "\n",
        "        random.shuffle(next_states)\n",
        "        return next_states"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "o_ybDnYTB5JQ"
      },
      "source": [
        "class Solver:\n",
        "    \"\"\"Class to solve a given problem state. \"\"\"\n",
        "    \n",
        "    def __init__(self):\n",
        "        self.solution = None\n",
        "        self.steps = 0\n",
        "\n",
        "    def a_star(self, initial):\n",
        "\n",
        "        frontier = []\n",
        "        explored = set()\n",
        "        visited = set()\n",
        "\n",
        "        heapq.heappush(frontier, initial)\n",
        "        visited.add(tuple(initial.state))\n",
        "\n",
        "        while frontier:\n",
        "            current = heapq.heappop(frontier)\n",
        "            \n",
        "            if tuple(current.state) in explored:\n",
        "                continue\n",
        "\n",
        "            explored.add(tuple(current.state))\n",
        "\n",
        "            if current.is_goal():\n",
        "                self.solution = current\n",
        "                return self.solution, self.steps\n",
        "            \n",
        "            else:\n",
        "                self.steps += 1\n",
        "            \n",
        "            for next_state in current.find_neighbors():\n",
        "                if tuple(next_state.state) not in visited:\n",
        "                    heapq.heappush(frontier, next_state)\n",
        "                    visited.add(tuple(next_state.state))\n",
        "\n",
        "        return None, None\n",
        "\n",
        "    def bfs(self, initial):\n",
        "\n",
        "        frontier = []\n",
        "        explored = set()\n",
        "        visited = set()\n",
        "\n",
        "        heapq.heappush(frontier, initial)\n",
        "        visited.add(tuple(initial.state))\n",
        "\n",
        "        while frontier:\n",
        "            current = heapq.heappop(frontier)\n",
        "\n",
        "            if tuple(current.state) in explored:\n",
        "                continue\n",
        "\n",
        "            explored.add(tuple(current.state))\n",
        "\n",
        "            if current.is_goal():\n",
        "                self.solution = current\n",
        "                return self.solution, self.steps\n",
        "            \n",
        "            else:\n",
        "                self.steps += 1\n",
        "\n",
        "            for next_state in current.find_neighbors():\n",
        "                if tuple(next_state.state) not in visited:\n",
        "                    visited.add(tuple(next_state.state))\n",
        "                    heapq.heappush(frontier, next_state)\n",
        "\n",
        "        return None, None\n",
        "\n",
        "    def get_steps(self):\n",
        "        current = self.solution\n",
        "        path = []\n",
        "\n",
        "        while current != None:\n",
        "            path.append(current)\n",
        "            current = current.parent\n",
        "        \n",
        "        return path[::-1]\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TwnfmW3XUlcx"
      },
      "source": [
        "array1 = [2, 4, 1, 5, 3, 6]\n",
        "array2 = [3, 4, 5, 1, 2]\n",
        "array3 = [5, 4, 3, 2, 1]"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jeYfAjQAMyEY",
        "outputId": "2c4c439e-b1cd-4ad2-de98-4eb77b8b6fb7",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "print(\"\\n\\t\\tBest First Search\\n\")\n",
        "\n",
        "start = time.time()\n",
        "\n",
        "initial = Sorter(array1)\n",
        "solver = Solver()\n",
        "soln, steps = solver.bfs(initial)\n",
        "\n",
        "end = time.time()\n",
        "\n",
        "if soln:\n",
        "    print(\"Initial State:\", initial)\n",
        "    print(\"Solution Reached:\", soln)\n",
        "    print(\"No. of steps taken:\", steps)\n",
        "\n",
        "    print(\"\\nPath taken:\\n\")\n",
        "    path = solver.get_steps()\n",
        "    \n",
        "    for state in path:\n",
        "        print(state)\n",
        "\n",
        "    print(\"\\nTime taken: %.5f\"%(end - start))\n",
        "\n",
        "else:\n",
        "    print(\"No solution.\")"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "\n",
            "\t\tBest First Search\n",
            "\n",
            "Initial State: [2, 4, 1, 5, 3, 6]\n",
            "Solution Reached: [1, 2, 3, 4, 5, 6]\n",
            "No. of steps taken: 2\n",
            "\n",
            "Path taken:\n",
            "\n",
            "[2, 4, 1, 5, 3, 6]\n",
            "[1, 2, 4, 5, 3, 6]\n",
            "[1, 2, 3, 4, 5, 6]\n",
            "\n",
            "Time taken: 0.00114\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RLCOK6TXQ3Wl",
        "outputId": "5b260e3d-1b32-4876-c0b4-6ce592979475",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "print(\"\\n\\t\\tA - Star Search\\n\")\n",
        "\n",
        "start = time.time()\n",
        "\n",
        "initial = Sorter(array1, is_back_cost = True)\n",
        "solver2 = Solver()\n",
        "soln2, steps2 = solver2.a_star(initial)\n",
        "\n",
        "end = time.time()\n",
        "\n",
        "if soln:\n",
        "    print(\"Initial State:\", initial)\n",
        "    print(\"Solution Reached:\", soln2)\n",
        "    print(\"No. of steps taken:\", steps2)\n",
        "\n",
        "    print(\"\\nPath taken:\\n\")\n",
        "    path2 = solver2.get_steps()\n",
        "    \n",
        "    for state in path2:\n",
        "        print(state)\n",
        "    \n",
        "    print(\"\\nTime taken: %.5f\"%(end - start))\n",
        "\n",
        "else:\n",
        "    print(\"No solution.\")"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "\n",
            "\t\tA - Star Search\n",
            "\n",
            "Initial State: [2, 4, 1, 5, 3, 6]\n",
            "Solution Reached: [1, 2, 3, 4, 5, 6]\n",
            "No. of steps taken: 2\n",
            "\n",
            "Path taken:\n",
            "\n",
            "[2, 4, 1, 5, 3, 6]\n",
            "[1, 2, 4, 5, 3, 6]\n",
            "[1, 2, 3, 4, 5, 6]\n",
            "\n",
            "Time taken: 0.00123\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hMwK_xwhYWbz",
        "outputId": "be59fbc9-3dad-41b1-a578-f95e73ca3200",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "print(\"\\n\\t\\tBest First Search\\n\")\n",
        "\n",
        "start = time.time()\n",
        "\n",
        "initial = Sorter(array2)\n",
        "solver = Solver()\n",
        "soln, steps = solver.bfs(initial)\n",
        "\n",
        "end = time.time()\n",
        "\n",
        "if soln:\n",
        "    print(\"Initial State:\", initial)\n",
        "    print(\"Solution Reached:\", soln)\n",
        "    print(\"No. of steps taken:\", steps)\n",
        "\n",
        "    print(\"\\nPath taken:\\n\")\n",
        "    path = solver.get_steps()\n",
        "    \n",
        "    for state in path:\n",
        "        print(state)\n",
        "\n",
        "    print(\"\\nTime taken: %.5f\"%(end - start))\n",
        "\n",
        "else:\n",
        "    print(\"No solution.\")"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "\n",
            "\t\tBest First Search\n",
            "\n",
            "Initial State: [3, 4, 5, 1, 2]\n",
            "Solution Reached: [1, 2, 3, 4, 5]\n",
            "No. of steps taken: 1\n",
            "\n",
            "Path taken:\n",
            "\n",
            "[3, 4, 5, 1, 2]\n",
            "[1, 2, 3, 4, 5]\n",
            "\n",
            "Time taken: 0.00026\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7zu0HUk_YYv9",
        "outputId": "bc78ab42-050d-4b4a-af8d-2370860bc926",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "print(\"\\n\\t\\tA - Star Search\\n\")\n",
        "\n",
        "start = time.time()\n",
        "\n",
        "initial = Sorter(array2, is_back_cost = True)\n",
        "solver2 = Solver()\n",
        "soln2, steps2 = solver2.a_star(initial)\n",
        "\n",
        "end = time.time()\n",
        "\n",
        "if soln:\n",
        "    print(\"Initial State:\", initial)\n",
        "    print(\"Solution Reached:\", soln2)\n",
        "    print(\"No. of steps taken:\", steps2)\n",
        "\n",
        "    print(\"\\nPath taken:\\n\")\n",
        "    path2 = solver2.get_steps()\n",
        "    \n",
        "    for state in path2:\n",
        "        print(state)\n",
        "    \n",
        "    print(\"\\nTime taken: %.5f\"%(end - start))\n",
        "\n",
        "else:\n",
        "    print(\"No solution.\")"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "\n",
            "\t\tA - Star Search\n",
            "\n",
            "Initial State: [3, 4, 5, 1, 2]\n",
            "Solution Reached: [1, 2, 3, 4, 5]\n",
            "No. of steps taken: 1\n",
            "\n",
            "Path taken:\n",
            "\n",
            "[3, 4, 5, 1, 2]\n",
            "[1, 2, 3, 4, 5]\n",
            "\n",
            "Time taken: 0.00027\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Tv42T6ogYBLv"
      },
      "source": [
        "#Thus A-Star takes more time than BFS \n",
        "#but the difference is almost negligible due to the small state space of the problem"
      ],
      "execution_count": 10,
      "outputs": []
    }
  ]
}