22S1_W11_Prac.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b7bd1e38",
   "metadata": {},
   "source": [
    "# COMP SCI 2009 Programming for IT - W11 - Practical"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fbfa3074",
   "metadata": {},
   "source": [
    "# Set Covering\n",
    "As mentioned in the lecture, the **set cover problem** is an NP-complete problem. In this task, you will solve this question using both exhausive search (brute force) and greedy apporach. \n",
    "\n",
    "The problem is defined as follow:\n",
    "\n",
    "Given a `list` of `sets` where each `set` contains integers, please find the minimum number of sets that cover the integers from `1` to `10`\n",
    "\n",
    "For example, given the following three sets:\n",
    "1. `[1, 2, 3, 4, 5]`\n",
    "1. `[2, 4, 6, 8]`\n",
    "1. `[6, 7, 8, 9, 10]`\n",
    "\n",
    "Your code should find that `set1` and `set3` will cover all the integers from `1` to `10`.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4ba3759",
   "metadata": {},
   "source": [
    "## Exercise 1: Set cover - brute force \n",
    "\n",
    "First, implement the brute force approach that tests `all` combinations. You can assume there will be a solution. To simplify your code a bit, you can use the `itertools`. Please read its document and examples below:\n",
    "\n",
    "- https://www.geeksforgeeks.org/itertools-combinations-module-python-print-possible-combinations/\n",
    "- https://docs.python.org/3/library/itertools.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "8e86559b",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "([1, 2, 3], [4, 5, 6], [7, 8, 9, 10])\n",
      "---\n",
      "([1, 7], [2, 4, 8, 9, 10], [3, 5, 6])\n"
     ]
    }
   ],
   "source": [
    "import itertools\n",
    "\n",
    "def brute_force_set(subsets):\n",
    "    # INSERT YOUR CODE BELOW\n",
    "    # use itertools.combinations\n",
    "    # ~ 8 lines\n",
    "    for length in range(len(subsets)): #for length in the range of subsets length\n",
    "        combined = itertools.combinations(subsets, length) #combined is assigned to combinations of subsets and length\n",
    "        for potential in combined: #potential is a list of lists\n",
    "            union = [] #create union list/set\n",
    "            for end in potential: #for end in potential\n",
    "                union += end #end is added to union and it becomes the 'new' union\n",
    "            if set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]).issubset(set(union)): #if subset has 10 elements\n",
    "                return potential #return 'potential' subset\n",
    "# ================\n",
    "# TEST CASES BELOW\n",
    "\n",
    "set_list1 = [ # first test input\n",
    "    [1, 2, 3],\n",
    "    [4, 5, 6],\n",
    "    [7, 8, 9, 10],\n",
    "    [1, 3, 7],\n",
    "    [2, 4, 6, 8]\n",
    "]\n",
    "\n",
    "set_list2 = [ # second test input\n",
    "    [4, 2, 5],\n",
    "    [1, 7],\n",
    "    [2, 4, 8, 9, 10],\n",
    "    [5, 10],\n",
    "    [3, 5, 6],\n",
    "    [2, 6],\n",
    "    [1, 8, 9, 10]\n",
    "]\n",
    "            \n",
    "ss = brute_force_set(set_list1)\n",
    "print(ss) # ([1, 2, 3], [4, 5, 6], [7, 8, 9, 10])\n",
    "print('---')\n",
    "ss = brute_force_set(set_list2)\n",
    "print(ss) # ([1, 7], [2, 4, 8, 9, 10], [3, 5, 6])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bcf7b2ca",
   "metadata": {},
   "source": [
    "## Exercise 2: Set cover - greedy\n",
    "\n",
    "\n",
    "\n",
    "In this exercise, please implement a greedy algorithm that **for each step, takes a set that contains the most uncovered integers** until it covers all integers from `1` to `10`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "7f385186",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[7, 8, 9, 10], [1, 2, 3], [4, 5, 6]]\n",
      "---\n",
      "[[2, 4, 8, 9, 10], [3, 5, 6], [1, 7]]\n"
     ]
    }
   ],
   "source": [
    "def greedy_set(subsets):  #define the function with subsets as variable\n",
    "    \n",
    "    union = set() #create union list/set\n",
    "    result = [] #create result list\n",
    "    covered = set() #create covered set to put elements that algorithm has found so far\n",
    "\n",
    "    for subset in subsets: #to find the subset in subsets\n",
    "        union = union.union(subset) #we append the subset into union set by using the .union function\n",
    "\n",
    "    while covered != union: #while covered is not equal to union\n",
    "        subset = [] #create another empty list for subset\n",
    "        for sset in subsets: # for sset in subsets\n",
    "            if len(set(sset) - covered) > len(set(subset) - covered): #if the length of sset set - covered is greater than length of subset - covered\n",
    "                subset = sset #subset is now sset\n",
    "        result.append(subset) #append subset to result\n",
    "        covered |= set(subset) #covered is now union to subset, which is now a set with |=\n",
    "    return result #return the result\n",
    "\n",
    "\n",
    "# ================\n",
    "# TEST CASES BELOW\n",
    "\n",
    "set_list1 = [ # first test input\n",
    "    [1, 2, 3],\n",
    "    [4, 5, 6],\n",
    "    [7, 8, 9, 10],\n",
    "    [1, 3, 7],\n",
    "    [2, 4, 6, 8]\n",
    "]\n",
    "\n",
    "set_list2 = [ # second test input\n",
    "    [4, 2, 5],\n",
    "    [1, 7],\n",
    "    [2, 4, 8, 9, 10],\n",
    "    [5, 10],\n",
    "    [3, 5, 6],\n",
    "    [2, 6],\n",
    "    [1, 8, 9, 10]\n",
    "]\n",
    "\n",
    "s = greedy_set(set_list1)\n",
    "print(s) # [[7, 8, 9, 10], [1, 2, 3], [4, 5, 6]]\n",
    "print('---')\n",
    "s = greedy_set(set_list2)\n",
    "print(s) # [[2, 4, 8, 9, 10], [3, 5, 6], [1, 7]]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a49e3a8",
   "metadata": {},
   "source": [
    "# Exercise 3 - Knapsack Problem\n",
    "\n",
    "It’s Boxing Day and you are in a shopping contest! You have one shopping bag and you would like to fill your bags with items that have the largest sum of values. Please solve this problem using dynamic programming."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a7c65dd5",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    0    0    0    0 3000 \n",
      "    0 1500 1500 1500 3000 \n",
      "    0 1500 1500 2000 3500 \n",
      "---\n",
      "    0  700  700  700  700  700  700  700 \n",
      "    0  700  700  700 1000 1000 1000 1000 \n",
      "    0  700  700  700 1400 1400 1400 1700 \n",
      "    0  700  700  700 1400 1700 1700 1700 \n",
      "    0  700  700 1200 1900 1900 1900 2600 \n",
      "    0  900 1600 1600 2100 2800 2800 2800 \n",
      "    0  900 1700 2400 2400 2900 3600 3600 \n"
     ]
    }
   ],
   "source": [
    "bag1 = 4 # the maximum weight for the bag\n",
    "item_list1 = [\n",
    "    ['guitar', 4, 3000],\n",
    "    ['speaker', 1, 1500],\n",
    "    ['laptop', 3, 2000]\n",
    "]\n",
    "\n",
    "bag2 = 7 # the maximum weight for the bag\n",
    "item_list2 = [\n",
    "    ['pasta', 1, 700],\n",
    "    ['soups', 3, 300],\n",
    "    ['pork', 3, 700],\n",
    "    ['steak', 4, 1000],\n",
    "    ['lamb', 3, 1200],\n",
    "    ['Cheese', 1, 900],\n",
    "    ['Mushroom', 1, 800],\n",
    "]\n",
    "\n",
    "def knapsack_dp(bag_size, items):\n",
    "    num_row = len(items)\n",
    "    num_col = bag_size    \n",
    "    grid = [[0]* (num_col+1) for _ in range(num_row)] # initialise the grid    \n",
    "    prev_max = 0\n",
    "    \n",
    "    # INSERT YOUR CODE\n",
    "    # Update the DP table (the variable grid)\n",
    "    # ~ 15 lines\n",
    "    for x in range(0, num_row):\n",
    "        for y in range(1, num_col + 1): #first column will be full of 0's, this is normal as this is initial cost/weight\n",
    "            if x == 0:\n",
    "                prev_max = 0 #if x is 0 then the previous max is 0\n",
    "            else:\n",
    "                prev_max = grid[x - 1][y]\n",
    "            item_w = items[x][1]\n",
    "            new_value = items[x][2] + grid[x - 1][y - item_w] # to get the value of the current item and the previous max value of the remaining weight\n",
    "            if y >= item_w:\n",
    "                grid[x][y] = max(prev_max, new_value)\n",
    "            else:\n",
    "                grid[x][y] = prev_max\n",
    "\n",
    "    return grid\n",
    "\n",
    "def display(grid):\n",
    "    for r in grid:\n",
    "        s = ' '\n",
    "        for c in r:\n",
    "            s += f'{c:4} '\n",
    "        print(s)\n",
    "\n",
    "g = knapsack_dp(bag1, item_list1)\n",
    "display(g)\n",
    "print('---')\n",
    "g = knapsack_dp(bag2, item_list2)\n",
    "display(g)\n",
    "\n",
    "# output should be as below\n",
    "\n",
    "#     0    0    0    0 3000 \n",
    "#     0 1500 1500 1500 3000 \n",
    "#     0 1500 1500 2000 3500 \n",
    "# ---\n",
    "#     0  700  700  700  700  700  700  700 \n",
    "#     0  700  700  700 1000 1000 1000 1000 \n",
    "#     0  700  700  700 1400 1400 1400 1700 \n",
    "#     0  700  700  700 1400 1700 1700 1700 \n",
    "#     0  700  700 1200 1900 1900 1900 2600 \n",
    "#     0  900 1600 1600 2100 2800 2800 2800 \n",
    "#     0  900 1700 2400 2400 2900 3600 3600 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f72aa28",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.6 64-bit (windows store)",
   "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.10.6"
  },
  "otter": {
   "tests": {
    "Task1": {
     "name": "Task1",
     "points": 1,
     "suites": [
      {
       "cases": [
        {
         "code": ">>> s = [[1, 2, 3], [4, 5, 6, 7], [8, 9, 10], [3, 5]]\n>>> ss = brute_force_set(s)\n>>> ss[-1]\n[8, 9, 10]",
         "failure_message": "Incorrect answer, try again!",
         "hidden": false,
         "locked": false,
         "success_message": "Good job!"
        },
        {
         "code": ">>> s = [[1, 2, 3, 4, 5, 6, 7, 8], [2, 4, 6], [9], [10], [8]]\n>>> ss = brute_force_set(s)\n>>> ss[-1]\n[10]",
         "failure_message": "Incorrect answer, try again!",
         "hidden": false,
         "locked": false,
         "success_message": "Good job!"
        }
       ],
       "scored": true,
       "setup": "",
       "teardown": "",
       "type": "doctest"
      }
     ]
    },
    "Task2": {
     "name": "Task2",
     "points": 1,
     "suites": [
      {
       "cases": [
        {
         "code": ">>> s = [[1, 2, 3], [4, 5, 6, 7], [8, 9, 10], [3, 5]]\n>>> ss = greedy_set(s)\n>>> ss[-1]\n[8, 9, 10]",
         "failure_message": "Incorrect answer, try again!",
         "hidden": false,
         "locked": false,
         "success_message": "Good job!"
        },
        {
         "code": ">>> s = [[1, 2, 3, 4, 5, 6, 7, 8], [2, 4, 6], [9], [10], [8]]\n>>> ss = greedy_set(s)\n>>> ss[-1]\n[10]",
         "failure_message": "Incorrect answer, try again!",
         "hidden": false,
         "locked": false,
         "success_message": "Good job!"
        }
       ],
       "scored": true,
       "setup": "",
       "teardown": "",
       "type": "doctest"
      }
     ]
    },
    "Task3": {
     "name": "Task3",
     "points": 2,
     "suites": [
      {
       "cases": [
        {
         "code": ">>> item_list1 = [['a', 4, 3000],['b', 1, 1500],['c', 3, 2000]]\n>>> g = knapsack_dp(5, item_list1)\n>>> g[-1][-1]\n4500",
         "failure_message": "Incorrect answer, try again!",
         "hidden": false,
         "locked": false,
         "success_message": "Good job!"
        },
        {
         "code": ">>> # the maximum weight for the bag\n>>> item_list1 = [['a', 2, 3000],['b', 1, 1500],['c', 1, 2000]]\n>>> g = knapsack_dp(5, item_list1)\n>>> g[-1][-1]\n6500",
         "failure_message": "Incorrect answer, try again!",
         "hidden": false,
         "locked": false,
         "success_message": "Good job!"
        }
       ],
       "scored": true,
       "setup": "",
       "teardown": "",
       "type": "doctest"
      }
     ]
    }
   }
  },
  "vscode": {
   "interpreter": {
    "hash": "81c43766d3b88c54b3a27528e996ec6233d9853b5c4711a526d87e19df354489"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}