assignments/assignment_5.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyP4b89sbMhHVcKTL8JozRrh",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/gayatri-p/cs142-lab/blob/main/assignments/assignment_5.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **Assignment 5**\n",
        "\n",
        "---\n",
        "\n",
        "#### *Finding subsets, n-queen problem as well as its modification to find the number of superqueens Introduction to Object Oriented Programming*\n"
      ],
      "metadata": {
        "id": "yggBS1wF38XI"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Problem 1(a).** Given a set of non-negative integers, a value $t$, and an integer $k$, determine if there is a subset of size exactly $k$ such that the sum of the elements in the set is equal to $t$. Use backtracking to reduce the number of calls you make to your recursive function.\n",
        "\n",
        "*Example:* \\\n",
        "**Input:** [3, 34, 4, 12, 5, 2], t = 9, k = 2 \\\n",
        "**Output:** True, there is a subset (4, 5) of size 2 with a sum of 9."
      ],
      "metadata": {
        "id": "kKIn1CKw4Ecy"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "counter = 0\n",
        "\n",
        "def find_subset(lst, n, t, k, subset=[]):\n",
        "  global counter\n",
        "  counter += 1\n",
        "\n",
        "  if t == 0:\n",
        "    if len(subset) == k: \n",
        "      return subset\n",
        "    else:\n",
        "      return False\n",
        "  \n",
        "  if n == 0:\n",
        "    return False\n",
        "\n",
        "  # ignore if last element greater than the sum\n",
        "  if (lst[n-1] > t):\n",
        "    return find_subset(lst, n-1, t, k, subset)\n",
        "\n",
        "  including_last = find_subset(lst, n-1, t-lst[n-1], k, subset+[lst[n-1]])\n",
        "  excluding_last = find_subset(lst, n-1, t, k, subset)\n",
        "\n",
        "  return including_last or excluding_last\n",
        "\n",
        "lst = [22, 11, 9, 10]\n",
        "t = 19\n",
        "k = 2\n",
        "print(find_subset(lst, len(lst), t, k))\n",
        "print('No. of function runs:', counter)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hSnX4mQn7ytF",
        "outputId": "080cc90e-b4e8-4f4e-9107-c909cbb60cea"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[10, 9]\n",
            "No. of function runs: 15\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Problem 1(b).** Given a set of positive and negative integers, and a value $t$, and an integer $k$ determine if there is a subset of size exactly k, such that the sum of the elements in the set is equal to $t$. Write a program that uses the function in Problem 1 as a subroutine."
      ],
      "metadata": {
        "id": "fkNOcdFp44HC"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "'''Run code cell for 1(a) first'''\n",
        "\n",
        "counter = 0\n",
        "\n",
        "def find_subset_2(lst, t, k):\n",
        "  n = min(lst)-1\n",
        "  lst = [i-n for i in lst]\n",
        "  t -= n*k\n",
        "  subset = find_subset(lst, len(lst), t, k)\n",
        "\n",
        "  if subset:\n",
        "    return [i+n for i in subset]\n",
        "  return None\n",
        "\n",
        "lst = [8, 7, 6, 5, 4, 3, 2, 1, -1, -5, -6]\n",
        "t = 3\n",
        "k = 2\n",
        "\n",
        "print(find_subset_2(lst, t, k))\n",
        "print('No. of function runs:', counter)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "EqxnpiEF70Ij",
        "outputId": "7ba8e177-c03e-40c6-cca9-56c94e2210a4"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[-5, 8]\n",
            "No. of function runs: 270\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Problem 2(a).** Given an $n×n$ chess board, you must place $n$ queens on the board so that no two queens attack each other. Print a matrix satisfying the conditions with positions with queens marked with $1$ and empty spaces with $0$. You must solve the $n$ queens problem using backtracking."
      ],
      "metadata": {
        "id": "Q5arsxc955Kp"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def is_safe(queen_positions, row, col, n):\n",
        "  '''\n",
        "  Takes the board and check if the queen can be\n",
        "  placed in (row, col)\n",
        "  '''\n",
        "  if (row, col) in queen_positions:\n",
        "    return False\n",
        "\n",
        "  # upper columns\n",
        "  for x in range(0, row):\n",
        "    if (x, col) in queen_positions:\n",
        "      return False\n",
        "\n",
        "  # top right diagonal\n",
        "  for x, y in zip(range(row, -1, -1), range(col, n)):\n",
        "    if (x, y) in queen_positions:\n",
        "      return False\n",
        "\n",
        "  # top left diagonal\n",
        "  for x, y in zip(range(row, -1, -1), range(col, -1, -1)):\n",
        "    if (x, y) in queen_positions:\n",
        "      return False\n",
        "\n",
        "  return True \n",
        "\n",
        "def add_soln(queen_positions, sols, n):\n",
        "  '''\n",
        "  From a possible solution, generate a board\n",
        "  and add it to the list\n",
        "  '''\n",
        "  config = ''\n",
        "  for row in range(n):\n",
        "    for col in range(n):\n",
        "      if (row,col) in queen_positions:\n",
        "        config += ' Q'\n",
        "      else:\n",
        "        config += ' .'\n",
        "    config += '\\n'\n",
        "  sols.append(config)\n",
        "\n",
        "def solve(queen_positions, sols, n, row=0):\n",
        "  '''\n",
        "  For each position on a row, places the queen if its safe\n",
        "  and then recursively calls the fuction on the next row\n",
        "  '''\n",
        "  if row >= n:\n",
        "    add_soln(queen_positions, sols, n)\n",
        "    return \n",
        "  \n",
        "  for col in range(n):\n",
        "    if is_safe(queen_positions, row, col, n):\n",
        "      queen_positions.append((row, col))\n",
        "      solve(queen_positions, sols, n, row+1)\n",
        "\n",
        "      queen_positions.pop() # backtracking\n",
        "  \n",
        "def main(n):\n",
        "  '''\n",
        "  Calls the solve function and prints the possible boards\n",
        "  '''\n",
        "  queen_positions = []\n",
        "  solutions = []\n",
        "  solve(queen_positions, solutions, n)\n",
        "  \n",
        "  if solutions:\n",
        "    print(f'Found {len(solutions)} solutions:')\n",
        "    for s in solutions:\n",
        "      print(s)\n",
        "  else:\n",
        "    print('No possible chess board configurations')\n",
        "\n",
        "n = 6\n",
        "main(n)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hiWc5Uvu71Pg",
        "outputId": "a4901a86-e29c-414b-b043-a0fa5068ab05"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Found 4 solutions:\n",
            " . Q . . . .\n",
            " . . . Q . .\n",
            " . . . . . Q\n",
            " Q . . . . .\n",
            " . . Q . . .\n",
            " . . . . Q .\n",
            "\n",
            " . . Q . . .\n",
            " . . . . . Q\n",
            " . Q . . . .\n",
            " . . . . Q .\n",
            " Q . . . . .\n",
            " . . . Q . .\n",
            "\n",
            " . . . Q . .\n",
            " Q . . . . .\n",
            " . . . . Q .\n",
            " . Q . . . .\n",
            " . . . . . Q\n",
            " . . Q . . .\n",
            "\n",
            " . . . . Q .\n",
            " . . Q . . .\n",
            " Q . . . . .\n",
            " . . . . . Q\n",
            " . . . Q . .\n",
            " . Q . . . .\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Problem 2(b).** Let us define a super-queen if a queen also has the power of a knight. Given an $n × n$ chess board, use backtracking to find the maximum number of super-queens you can place in the board so that no two super-queens attack each other."
      ],
      "metadata": {
        "id": "2fHbTDeV55Nl"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def is_safe(queen_positions, row, col, n):\n",
        "  '''\n",
        "  Takes the board and check if the queen can be\n",
        "  placed in (row, col)\n",
        "  '''\n",
        "  if (row, col) in queen_positions:\n",
        "    return False\n",
        "\n",
        "  # upper columns\n",
        "  for x in range(0, row):\n",
        "    if (x, col) in queen_positions:\n",
        "      return False\n",
        "\n",
        "  # top right diagonal\n",
        "  for x, y in zip(range(row, -1, -1), range(col, n)):\n",
        "    if (x, y) in queen_positions:\n",
        "      return False\n",
        "\n",
        "  # top left diagonal\n",
        "  for x, y in zip(range(row, -1, -1), range(col, -1, -1)):\n",
        "    if (x, y) in queen_positions:\n",
        "      return False\n",
        "\n",
        "  # knight\n",
        "  knight_moves = [(-2, -1), (2, -1), (-1, -2), (1, -2),\n",
        "                  (-2, 1),  (2, 1),  (-1, 2),  (1, 2) ]\n",
        "  for move_x, move_y in knight_moves:\n",
        "    x = move_x + row\n",
        "    y = move_y + col\n",
        "\n",
        "    if 0 <= x < n and 0 <= y < n:\n",
        "      if (x, y) in queen_positions:\n",
        "        return False\n",
        "    \n",
        "  return True \n",
        "\n",
        "def solve(queen_positions, n, super_queens, row=0):\n",
        "  '''\n",
        "  For each position on a row, places the queen if its safe\n",
        "  and then recursively calls the function on the next row\n",
        "  '''\n",
        "  if row == n:\n",
        "    return\n",
        "  \n",
        "  for col in range(n):\n",
        "    if is_safe(queen_positions, row, col, n):\n",
        "      queen_positions.append((row, col))\n",
        "\n",
        "      if len(queen_positions) >= max(super_queens):\n",
        "        super_queens.append(len(queen_positions))\n",
        "        \n",
        "      solve(queen_positions, n, super_queens, row+1)\n",
        "      queen_positions.pop() # backtracking\n",
        "  \n",
        "def main(n):\n",
        "  queen_positions = []\n",
        "  super_queens = [0]\n",
        "  solve(queen_positions, n, super_queens)\n",
        "  \n",
        "  print(f'Maximum number of superqueens: {max(super_queens)}')\n",
        "\n",
        "n = 9\n",
        "main(n)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "FSHL6qzu73IB",
        "outputId": "94ebd45c-a14c-47d7-e9fe-06adb3d6a0ca"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Maximum number of superqueens: 7\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Problem 3.** Recall the question no. 2 from the exam. We have a function $F$ such that given two lists $L1$ and $L2$, $f(L1, L2)$ returns the difference of the sum of the elements of $L1$ and $L2$. Now given a list of size $3^k$ that consists of $3^k − 1$ many $1s$ and a single $2$, find the position of $2$ making at most $k$ many calls to the function $F$.\n",
        "\n",
        "```python\n",
        "def F(L1, L2):\n",
        "  diff = 0\n",
        "  for x in L1: diff += x\n",
        "  for x in L2: diff -= x\n",
        "  return diff\n",
        "```"
      ],
      "metadata": {
        "id": "gTfSv8PC7PCy"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "counter = 0\n",
        "\n",
        "def F(L1, L2):\n",
        "  global counter\n",
        "  counter += 1\n",
        "\n",
        "  diff = 0\n",
        "  for x in L1: diff += x\n",
        "  for x in L2: diff -= x\n",
        "  return diff\n",
        "\n",
        "def find_two(arr, prev=0):\n",
        "  if len(arr) == 1 :\n",
        "    return prev if arr[0] == 2 else -1\n",
        "    \n",
        "  else:\n",
        "    n = len(arr)\n",
        "    one_third = n // 3\n",
        "\n",
        "    if arr[one_third] == 2:\n",
        "      return one_third + prev\n",
        "\n",
        "    left = arr[:one_third]\n",
        "    middle = arr[one_third:one_third*2]\n",
        "    right = arr[one_third*2:]\n",
        "\n",
        "    diff = F(left, right)\n",
        "\n",
        "    if diff == -1:\n",
        "      return find_two(right, prev+(2*one_third))\n",
        "\n",
        "    elif diff == 0: \n",
        "      return find_two(middle, prev+one_third)\n",
        "\n",
        "    elif diff == 1:\n",
        "      return find_two(left, prev)\n",
        "\n",
        "k = 4\n",
        "arr = [1 for i in range(3**k)]\n",
        "arr[56] = 2\n",
        "print('Position of 2:', find_two(arr))\n",
        "print('Number of calls of F:', counter)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "LbFThLroucin",
        "outputId": "10d538f2-3451-4cc2-f57d-a46c543afd56"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Position of 2: 56\n",
            "Number of calls of F: 4\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Problem 3.** Define a class in python."
      ],
      "metadata": {
        "id": "vJL_2JHF94gS"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Person:\n",
        "  '''\n",
        "  A Class is like an object constructor, or a \"blueprint\" for creating objects.\n",
        "  '''\n",
        "\n",
        "  def __init__(self, name, age):\n",
        "    self.name = name\n",
        "    self.age = age\n",
        "\n",
        "  def greet(self, name):\n",
        "    '''\n",
        "    Methods are function called on objects.\n",
        "    '''\n",
        "    print(f'Hello {self.name}. My name is {name}.')\n",
        "\n",
        "  def describe(self):\n",
        "    print(f'{self.name} is {self.age} years old.')\n",
        "\n",
        "p1 = Person(\"John\", 36)\n",
        "\n",
        "print(p1.name)\n",
        "print(p1.age)\n",
        "p1.greet('Jack')\n",
        "p1.describe()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "4jOifBe_93Gl",
        "outputId": "14624eff-6624-4def-9a36-9895eeef2a88"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "John\n",
            "36\n",
            "Hello John. My name is Jack.\n",
            "John is 36 years old.\n"
          ]
        }
      ]
    }
  ]
}