DTSA5503-Homework2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "3e7a36052f9179311eb7176388b0a340",
     "grade": false,
     "grade_id": "cell-baa1efcc1ca6d618",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Problem 1 : Longest Stable Subsequence\n",
    "\n",
    "Consider a list of numbers $[a_0, a_1, \\cdots, a_{n-1}]$. Our goal is to find the the longest stable subsequence: $[a_{i_1}, a_{i_2}, \\cdots, a_{i_k} ]$ which is a sub-list of the original list that selects elements at indices $i_1, i_2, \\ldots, i_k$ from the original list such that \n",
    "  1. $i_1 < i_2 < \\cdots < i_k$; \n",
    "  2. $a_{i_{j+1}} - 1 \\leq a_{i_{j}} \\leq a_{i_{j+1}} + 1 $. We can also write this as $|a_{i_{j+1}} - a_{i_j}| \\leq 1$. I.e, each element of the subsequence must be within $\\pm 1$ or equal to the previous element.\n",
    "  3. The length of the subsequence $k$ is maximized.\n",
    "\n",
    "### Example \n",
    "\n",
    "Consider the list `[1, 4, 2, -2, 0, -1, 2, 3]`.  There are many \"stable subsequences\":\n",
    " - `[1, 0, -1]`\n",
    " - `[1, 2, 2, 3]`\n",
    " - `[4, 3]`\n",
    "\n",
    "The longest stable subsequence is `[1, 2, 2, 3]` of length 4. Note that each element of the subsequence is at most $1$ away from the previous element.\n",
    "\n",
    "The goal of this problem is to formulate a dynamic programming solution to find the length of the longest stable subsequence and the subsequence itself."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "ff287239877ea9df527694710fad2c17",
     "grade": false,
     "grade_id": "cell-8cc398488f835758",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### A: Write a Recurrence With Base Case\n",
    "$$\\newcommand\\lss{\\textsf{LSSLength}}$$\n",
    "Let $n$ be the length of the original array $[a_0, \\ldots, a_{n-1}]$. Define $$\\lss(\\color{red}{i}, a_j)$$ to be the length of the longest stable subsequence for the subarray from $[a_{\\color{red}{i}}, \\ldots, a_{n-1}]$ (note that $a_{\\color{red}{i}}$ is included) with the additional constraint that the  first element in the subsequence chosen (let us call it $a_{i_1}$) must satisfy $$| a_{i_1} - a_j |  \\leq 1$$.\n",
    "\n",
    "\n",
    "__Notes__\n",
    "  0. $0 \\leq i \\leq n$. $i = n$ denotes the empty subarray.\n",
    "  1. $a_j$ represents a previous choice we have made before encountering the current subproblem. It is made an argument of the recurrence to ensure that the subsequent choice made from $[a_i, \\ldots, a_{n-1}]$ satisfies $|a - a_j| \\leq 1$.\n",
    "  2. We will use the special value $a_j = \\textsf{None}$ to denote that no such element $a_j$ has been chosen.\n",
    "\n",
    "Fill out the missing portion of the recurrence and base cases. We will not grade your answer below. Instead please use it as a guide to complete the code for the recurrence and pass the test cases provided.\n",
    "\n",
    "\n",
    "$\\lss(i, a_j) = \\begin{cases}\n",
    "?? & i = n & \\text{# Base Case when subarray is empty} \\\\\n",
    "\\lss(i+1, a_j) & i < n\\ \\text{and}\\ a_j \\not= \\text{None}\\ \\text{and}\\ |a_i - a_j| > 1 & \\text{# We cannot choose a[i], skip it and move right along}\\\\\n",
    "\\max(??? + 1, ??? ) & i < n\\ \\text{and}\\ \\left( a_j = \\text{None}\\ \\text{or}\\ |a_i - a_j| \\leq 1 \\right) & \\text{# Choose maximum of two options: take a[i]  or skip a[i]}\\\\\n",
    "\\end{cases}$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "c9d6b93f4fef246a198a01b0328f92a3",
     "grade": true,
     "grade_id": "cell-8aef09ea5f8a7aa8",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "?? = 1 + LSSLength(i+1,0)\n",
    "\n",
    "??? = max( 1 + LSSLength( i+1 , i ) , 0 + LSSLength( i+1 , j ) )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "7e922c6a5334d0753fa5837e10ebf14e",
     "grade": false,
     "grade_id": "cell-fccf4bfd6124b1cd",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Program the recurrence for longest stable subsequence\n",
    "# 0 <= i <= len(a)\n",
    "# Note that if j == -1, then take aj = None\n",
    "# else aj = a[j]\n",
    "def lssLength(a, i, j):\n",
    "    aj = a[j] if 0 <= j < len(a) else None \n",
    "  \n",
    "    # Implement the recurrence below. Use recursive calls back to lssLength\n",
    "    if aj is None and i ==0:\n",
    "        j = 0\n",
    "        i +=1\n",
    "        return 1 + lssLength(a,i,j)\n",
    "    elif i > len(a)-1 or j > len(a)-1:\n",
    "        return 0\n",
    "    else:\n",
    "        if abs( a[i] - a[j] ) <= 1 : \n",
    "            \n",
    "            #print(f'max(lssl({a},Counter:{i},Keeping:{a[i]} vs Keeping:{a[j]}))')\n",
    "            k = i + 1\n",
    "            return max(1 + lssLength(a,k,i), 0 + lssLength(a,k,j)) \n",
    "        \n",
    "        else: \n",
    "            i += 1\n",
    "            return 0 + lssLength(a,i,j)\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "281d8c3e85e2ef04fb717a993831b3aa",
     "grade": true,
     "grade_id": "cell-46a8002c4c41cc33",
     "locked": true,
     "points": 8,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--Test1--\n",
      "4\n",
      "passed\n",
      "--Test2--\n",
      "8\n",
      "--Test3--\n",
      "1\n",
      "--Test 4--\n",
      "14\n",
      "All Tests Passed (8 points)\n"
     ]
    }
   ],
   "source": [
    "print('--Test1--')\n",
    "n1 = lssLength([1, 4, 2, -2, 0, -1, 2, 3],0, -1)\n",
    "print(n1)\n",
    "assert n1== 4, f'Test 1 failed: expected answer 4, your code: {n1}'\n",
    "print('passed')\n",
    "\n",
    "print('--Test2--')\n",
    "n2 = lssLength([1, 2, 3, 4, 0, 1, -1, -2, -3, -4, 5, -5, -6], 0, -1)\n",
    "print(n2)\n",
    "assert n2 == 8, f'Test 2 failed: expected answer 8, your code: {n2}'\n",
    "\n",
    "print('--Test3--')\n",
    "n3 = lssLength([0,2, 4, 6, 8, 10, 12],0, -1)\n",
    "print(n3)\n",
    "assert n3 == 1, f'Test 3 failed: expected answer 1, your code: {n3}'\n",
    "\n",
    "\n",
    "print('--Test 4--')\n",
    "n4 = lssLength([4,8, 7, 5, 3, 2, 5, 6, 7, 1, 3, -1, 0, -2, -3, 0, 1, 2, 1, 3, 1, 0, -1, 2, 4, 5, 0, 2, -3, -9, -4, -2, -3, -1], 0, -1)\n",
    "print(n4)\n",
    "assert n4 == 14, f'Test 4 failed: expected answer 14, your code: {n4}'\n",
    "\n",
    "print('All Tests Passed (8 points)')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "074966d3e09313b62fd0f84dde882c4a",
     "grade": false,
     "grade_id": "cell-f0891651a1dcd5a2",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Part 2: Memoize the Recurrence \n",
    "\n",
    "Construct a memo table as a dictionary that maps from `(i,j)` where `0 <= i <= n` and `-1 <= j < i` to the value $\\lss(a, i, a_j)$ where $a_j = a[j]$ if $j \\geq 0$ else $a_j = \\text{None}$.\n",
    "\n",
    "Your code should run in worst case time $\\Theta(n^2)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "fbfb25a2a89ba0f522c24e0bc0ea34f5",
     "grade": false,
     "grade_id": "cell-96d3d39aabb560b3",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "## Attempt 1: didn't use the structure provided...\n",
    "    \n",
    "# def memoizeLSS(a):\n",
    "#     T = {} # Initialize the memo table to empty dictionary\n",
    "#     # Now populate the entries for the base case \n",
    "#     n = len(a)\n",
    "    \n",
    "#     T[(0, -1)] = 0 # i = n and j \n",
    "    \n",
    "#     # Now fill out the table : figure out the two nested for loops\n",
    "#     # It is important to also figure out the order in which you iterate the indices i and j\n",
    "#     # Use the recurrence structure itself as a guide: see for instance that T[(i,j)] will depend on T[(i+1, j)]\n",
    "#     def lssLengthMemo(a,i,j,T):\n",
    "        \n",
    "#         aj = a[j] if 0 <= j < len(a) else None \n",
    "#         #print(\"\\n Raw data: \",a,i,j,T,\"\\n\")\n",
    "#         if (i,j) in T.keys():\n",
    "#             return T[(i,j)]\n",
    "#         if j == -1 and i == 0 : \n",
    "#             sets = 1 + lssLengthMemo(a,1,0,T)\n",
    "#             T[(i,j)] = sets\n",
    "            \n",
    "#         elif i >= (len(a)) or j >= (len(a) ) : #or aj is None:\n",
    "#             #print(f\"Terminate on I={i}, J={j} \")\n",
    "#             T[(i,j)] = 0\n",
    "#             return 0\n",
    "#         else:\n",
    "#             if abs(a[i]-a[j]) <= 1:\n",
    "#                 k = i + 1\n",
    "#                 #print(f\"I={i}, Ival={a[i]},  J={j}, Jval={a[j]}\")\n",
    "#                 sets = max(1 + lssLengthMemo(a,k,i,T), 0 + lssLengthMemo(a,k,j,T))\n",
    "#                 T[(i,j)] = sets\n",
    "#                 #print(f\"Good Sets: {i}:{sets}\")\n",
    "#                 return int(sets)\n",
    "#             else:\n",
    "#             #abs(a[i]-a[j]) > 1:\n",
    "\n",
    "#                 #print(f\"Passing I={i}, Ival={a[i]},  J={j}, Jval={a[j]}\")\n",
    "#                 k = i + 1\n",
    "#                 sets = int(0 + lssLengthMemo(a,k,j,T))\n",
    "#                 #print(f\"Zero Sets: I,J= {i},{j} Sets = {sets}\")\n",
    "#                 T[(i,j)] = sets\n",
    "#                 return int(sets)\n",
    "\n",
    "#     #uh oh, should never get here, so print the Dictionary and see why\n",
    "#     print(T)\n",
    "#     for i in range(n):\n",
    "#         for j in range(-1,n):\n",
    "#             #print(f\"Starting{a}{i}{j}{T}\\n\")\n",
    "#             lssLengthMemo(a,i,j,T)\n",
    "#     T[(0,-1)] = 1 + T[(1,0)]         \n",
    "#     #print(sorted((k,v) for k,v in T.items()))\n",
    "\n",
    "#     return T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def memoizeLSS(a):\n",
    "    T = {}\n",
    "    n = len(a)\n",
    "    for j in range(-1,n):\n",
    "        T[(n,j)] = 0 \n",
    "        # i = n and j \n",
    "    # Now fill out the table...\n",
    "    \n",
    "    for i in range(n-1,-1,-1):\n",
    "        for j in range(i-1,-2,-1):\n",
    "            if j != -1:\n",
    "                if abs(a[i]-a[j]) > 1:\n",
    "                     \n",
    "                    T[(i,j)] = T[(i+1),j]\n",
    "                else: \n",
    "                    oa = 1 + T[(i+1,i)]\n",
    "                    ob = T[(i+1,j)]\n",
    "                    #print(f'Eval(1+[i + 1,i] or ({i+1},{i}) vs [i+1,j] or ({i+1},{j})) --> {i},{j}={max (oa,ob)}') \n",
    "                    T[(i,j)] = max(oa,ob)\n",
    "                     \n",
    "            else: #j ==-1\n",
    "                oa = 1 + T[(i+1,i)]\n",
    "                ob = T[(i+1,j)]\n",
    "                 \n",
    "                T[(i,j)]= max(oa,ob)\n",
    "                \n",
    "                \n",
    "    #print(sorted((k,v) for k,v in T.items()))\n",
    "    return(T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "14bb799a3895b576edb029b927a59dcf",
     "grade": true,
     "grade_id": "cell-173fb571d3611cba",
     "locked": true,
     "points": 7,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-- Test 1 -- \n",
      "[1, 4, 2, -2, 0, -1, 2, 3]\n",
      "Passed\n",
      "--Test2--\n",
      "[1, 2, 3, 4, 0, 1, -1, -2, -3, -4, 5, -5, -6]\n",
      "--Test3--\n",
      "[0, 2, 4, 6, 8, 10, 12]\n",
      "--Test4--\n",
      "[4, 8, 7, 5, 3, 2, 5, 6, 7, 1, 3, -1, 0, -2, -3, 0, 1, 2, 1, 3, 1, 0, -1, 2, 4, 5, 0, 2, -3, -9, -4, -2, -3, -1]\n",
      "All tests passed (7 points)\n"
     ]
    }
   ],
   "source": [
    "def lssLength(a, i, j):\n",
    "    assert False, 'Redefining lssLength: You should not be calling this function from your memoization code'\n",
    "\n",
    "def checkMemoTableHasEntries(a, T):\n",
    "    for i in range(len(a)+1):\n",
    "        for j in range(i):\n",
    "            assert (i, j) in T, f'entry for {(i,j)} not in memo table'\n",
    "            \n",
    "def checkMemoTableBaseCase(a, T):\n",
    "    n = len(a)\n",
    "    for j in range(-1, n):\n",
    "        assert T[(n, j)] == 0, f'entry for {(n,j)} is not zero as expected'\n",
    "        \n",
    "print('-- Test 1 -- ')\n",
    "a1 = [1, 4, 2, -2, 0, -1, 2, 3]\n",
    "print(a1)\n",
    "T1 = memoizeLSS(a1)\n",
    "checkMemoTableHasEntries(a1, T1)\n",
    "checkMemoTableBaseCase(a1, T1)\n",
    "assert T1[(0, -1)] == 4, f'Test 1: Expected answer is 4. your code returns {T1[(0, -1)]}'\n",
    "print('Passed')\n",
    "\n",
    "\n",
    "print('--Test2--')\n",
    "a2 = [1, 2, 3, 4, 0, 1, -1, -2, -3, -4, 5, -5, -6]\n",
    "print(a2)\n",
    "T2 = memoizeLSS(a2)\n",
    "checkMemoTableHasEntries(a2, T2)\n",
    "checkMemoTableBaseCase(a2, T2)\n",
    "assert T2[(0, -1)] == 8, f'Test 2: Expected answer is 8. Your code returns {T2[(0, -1)]}'\n",
    "\n",
    "print('--Test3--')\n",
    "a3 = [0,2, 4, 6, 8, 10, 12]\n",
    "print(a3)\n",
    "T3 = memoizeLSS(a3)\n",
    "checkMemoTableHasEntries(a3, T3)\n",
    "checkMemoTableBaseCase(a3, T3)\n",
    "assert T3[(0, -1)] == 1, f'Test 3: Expected answer is  1. Your code returns {T3[(0, -1)]}'\n",
    "\n",
    "\n",
    "print('--Test4--')\n",
    "a4 = [4,8, 7, 5, 3, 2, 5, 6, 7, 1, 3, -1, 0, -2, -3, 0, 1, 2, 1, 3, 1, 0, -1, 2, 4, 5, 0, 2, -3, -9, -4, -2, -3, -1]\n",
    "print(a4)\n",
    "T4 = memoizeLSS(a4)\n",
    "checkMemoTableHasEntries(a4, T4)\n",
    "checkMemoTableBaseCase(a4, T4)\n",
    "assert T4[(0, -1)] == 14, f'Text 4: Expected answer is 14. Your code returns {T4[(0,-1)]}'\n",
    "\n",
    "print('All tests passed (7 points)')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "91ae887455b1019790f28e4c7a416b05",
     "grade": false,
     "grade_id": "cell-265fe38a89a50dd0",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Part 3: Modify Memoized Code to Recover Solution\n",
    "\n",
    "Write a function `computeLSS(a)` that modifies the memo table to allow you to recover the longest stable subsequence as well as its length. `computeLSS` should return  the longest stable subsequence of the input `a` as a list.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "466067fb37a67d0958899e7281a09aa7",
     "grade": false,
     "grade_id": "cell-0c1d69eff40121b5",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def computeLSS(a):\n",
    "    T = memoizeLSS(a)\n",
    "    #print([sorted([k,v] for k,v in T.items())])\n",
    "    n = len(a)\n",
    "    i = 0\n",
    "    j = -1\n",
    "    sg = []\n",
    "    while i < n:\n",
    "        #print(i)\n",
    "        current = T[(i,j)]\n",
    "        nextt = T[i+1,j]\n",
    "        if current > nextt:\n",
    "            sg.append(a[i])\n",
    "            j = i\n",
    "        i += 1\n",
    "    return sg\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "4d4bdf283e1e9bf8c7b674135e5cfb8f",
     "grade": true,
     "grade_id": "cell-8e5b9536d543fb37",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--Test 1 --\n",
      "[1, 4, 2, -2, 0, -1, 2, 3]\n",
      "sub1 = [1, 2, 2, 3]\n",
      "--Test2--\n",
      "[1, 2, 3, 4, 0, 1, -1, -2, -3, -4, 5, -5, -6]\n",
      "sub2 = [1, 0, -1, -2, -3, -4, -5, -6]\n",
      "--Test3--\n",
      "[0, 2, 4, 6, 8, 10, 12]\n",
      "sub3 = [12]\n",
      "--Test4--\n",
      "[4, 8, 7, 5, 3, 2, 5, 6, 7, 1, 3, -1, 0, -2, -3, 0, 1, 2, 1, 3, 1, 0, -1, 2, 4, 5, 0, 2, -3, -9, -4, -2, -3, -1]\n",
      "sub4 = [4, 3, 2, 1, 0, 0, 1, 2, 1, 1, 0, -1, -2, -1]\n",
      "All test passed (10 points)\n"
     ]
    }
   ],
   "source": [
    "## BEGIN TESTS \n",
    "def checkSubsequence(a, b):\n",
    "    i = 0\n",
    "    j = 0\n",
    "    n = len(a)\n",
    "    m = len(b)\n",
    "    for j in range(m-1):\n",
    "        assert abs(b[j] - b[j+1]) <= 1\n",
    "    while (i < n and j < m):\n",
    "        if a[i] == b[j]: \n",
    "            j = j + 1\n",
    "        i = i + 1\n",
    "    if j < m:\n",
    "        return False\n",
    "    return True \n",
    "\n",
    "print('--Test 1 --')\n",
    "a1 = [1, 4, 2, -2, 0, -1, 2, 3]\n",
    "print(a1)\n",
    "sub1 = computeLSS(a1)\n",
    "print(f'sub1 = {sub1}')\n",
    "assert len(sub1) == 4, f'Subsequence does not have length 4'\n",
    "assert checkSubsequence(a1, sub1), f'Your solution is not a subsequence of the original sequence'\n",
    "\n",
    "print('--Test2--')\n",
    "a2 = [1, 2, 3, 4, 0, 1, -1, -2, -3, -4, 5, -5, -6]\n",
    "print(a2)\n",
    "sub2 = computeLSS(a2)\n",
    "print(f'sub2 = {sub2}')\n",
    "assert len(sub2) == 8\n",
    "assert checkSubsequence(a2, sub2)\n",
    "\n",
    "print('--Test3--')\n",
    "a3 = [0,2, 4, 6, 8, 10, 12]\n",
    "print(a3)\n",
    "sub3 = computeLSS(a3)\n",
    "print(f'sub3 = {sub3}')\n",
    "assert len(sub3) == 1\n",
    "assert checkSubsequence(a3, sub3)\n",
    "\n",
    "\n",
    "\n",
    "print('--Test4--')\n",
    "a4 = [4,8, 7, 5, 3, 2, 5, 6, 7, 1, 3, -1, 0, -2, -3, 0, 1, 2, 1, 3, 1, 0, -1, 2, 4, 5, 0, 2, -3, -9, -4, -2, -3, -1]\n",
    "print(a4)\n",
    "sub4 = computeLSS(a4)\n",
    "print(f'sub4 = {sub4}')\n",
    "assert len(sub4) == 14\n",
    "assert checkSubsequence(a4, sub4)\n",
    "\n",
    "print('All test passed (10 points)')\n",
    "## END TESTS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "af35923fad2a0d604e92c7a625040ef7",
     "grade": false,
     "grade_id": "cell-0273e0a415634d03",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Problem 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "a0f69414c24d34c31d29801236ec1f0d",
     "grade": false,
     "grade_id": "cell-3280fda8da210996",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "We are given a set of _natural numbers_ $S:\\ \\{ n_1, \\ldots, n_k \\}$ and a target _natural number_ $N$.\n",
    "\n",
    "\n",
    "Our goal is to choose a subset of numbers $T:\\ \\{ n_{i_1}, \\ldots, n_{i_j} \\} \\subseteq S$ such that:\n",
    "\n",
    " 1. $\\sum_{l=1}^j n_{i_l}  \\leq N$, the sum of chosen numbers is less than or equal to $N$, \n",
    " 2. The difference $N - \\sum_{l=1}^j n_{i_l} $ is made as small as possible.\n",
    "\n",
    "For example, $S = \\{ 1, 2, 3, 4, 5, 10 \\}$ and $N = 20$ then \n",
    "  - Choosing $T = \\{1, 2, 3, 4, 5\\}$, we have   $1 + 2 + 3 + 4 + 5 = 15 \\leq 20$, achieving a difference of $5$.  \n",
    "  - However, if we chose $T = \\{ 2,3,5,10\\}$  we obtain a sum of $2 + 3 + 5 + 10 = 20$ achieving the smallest possible difference of $0$.\n",
    "  - Choosing $T = \\{ 2, 3, 4, 5, 10\\}$ is disallowed because $2 + 3 + 4+ 5+ 10 = 24 > 20$.\n",
    "\n",
    "\n",
    "Therefore the problem is as follows:\n",
    "\n",
    "  * Inputs: list  $S: [n_1, \\ldots, n_k]$ (assume that no element repeats in $S$), and number $N$.\n",
    "  * Output: a list $T$ of elements from $S$ such that sum of elements of $T$ is  $\\leq N$ and $N - \\sum_{e \\in T} e$ is the smallest possible.\n",
    "\n",
    "The subsequent parts to this problem ask you to derive a dynamic programming solution to this problem.\n",
    "\n",
    "__Note:__ Because $S$ and $T$ are viewed as sets, each element in the set may occur exactly once.\n",
    "\n",
    "### Part (A) Write a recursive function\n",
    "\n",
    "$$\\newcommand\\targetSum{\\textsf{targetSum}}$$\n",
    "Write down a recurrence: $\\targetSum( \\{ S[i], \\ldots, S[k] \\}, \\hat{T} )$ that expresses the best possible solution to the sub problem where \n",
    "  - we choose a subset of $S$ with elements from from $S[i]$  to $S[k]$ inclusive. \n",
    "  - If $i > k$, we take that to be the empty set and \n",
    "  - $\\hat{T}$ is the current target.\n",
    "  \n",
    " Complete the missing portions of the definitions below.\n",
    "\n",
    "$$\\targetSum(\\left\\{ S[i], \\ldots, S[k] \\right\\}, \\hat{T}) = \\begin{cases}\n",
    "  ??? & \\hat{T} < 0 \\\\\n",
    "  ??? & i > k\\ \\text{and}\\ \\hat{T} \\geq 0 \\\\\n",
    "  \\min( ???, ???) & \\mbox{otherwise}\\\\\n",
    "\\end{cases} $$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "c42f19f08beb6853dde0226dd7e2b3de",
     "grade": true,
     "grade_id": "cell-33856e2d4e11e1f7",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "return float('inf')\n",
    "return empty set[]\n",
    "min(targetSum(S,T^)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "392c6bc0fef8dead30105c134eed97b1",
     "grade": false,
     "grade_id": "cell-6597352dee8db777",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Code up the recurrence below\n",
    "\n",
    "# def targetSum(S, i,  tgt):\n",
    "#     if tgt == 0:\n",
    "#         return 0\n",
    "#     elif tgt < 0:\n",
    "#         return float('inf')\n",
    "#     else:\n",
    "#         if i < (len(S)-1):\n",
    "#             #i <=len(S):\n",
    "#             #print(f\"target = {tgt}, i = {i}\")\n",
    "#             return   min(targetSum(S,i+1,(tgt-S[i])), targetSum(S,i+1,tgt))\n",
    "#         elif i == len(S)-1 :\n",
    "#             #print(f\"target = {tgt}, i = {i}\")\n",
    "#             if tgt-S[i] >=0:\n",
    "#                 return min(tgt-S[i],tgt)\n",
    "#             else:\n",
    "#                 return tgt\n",
    "#         else:\n",
    "#             return 100000000\n",
    "# t2 = tgtSum(26, [1, 2, 3, 4, 5, 10]) # should be 1\n",
    "# assert t2 == 1, 'Test 2 failed'\n",
    "\n",
    "def targetSum(S,i,tgt):\n",
    "    k = len(S)\n",
    "    if tgt < 0:\n",
    "        return float('inf')\n",
    "    elif i>=k:\n",
    "        return tgt\n",
    "    else:\n",
    "        oa = targetSum(S,i+1,tgt)\n",
    "        ob = targetSum(S,i+1,tgt-S[i])\n",
    "        return min(oa,ob)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "3952db0cc7bc1e51a18bbc1863b3c826",
     "grade": true,
     "grade_id": "cell-a3e3a96cb2f9401a",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "All tests passed (10 points)!\n"
     ]
    }
   ],
   "source": [
    "def tgtSum(tgt, S):\n",
    "    return targetSum(S, 0, tgt)\n",
    "\n",
    "t1 = tgtSum(15, [1, 2, 3, 4, 5, 10]) # Should be zero\n",
    "assert t1 == 0, 'Test 1 failed'\n",
    "\n",
    "t2 = tgtSum(26, [1, 2, 3, 4, 5, 10]) # should be 1\n",
    "assert t2 == 1, 'Test 2 failed'\n",
    "\n",
    "t3 = (tgtSum(23, [1, 2, 3, 4, 5, 10])) # should be 0\n",
    "assert t3 == 0, 'Test 3 failed'\n",
    "\n",
    "\n",
    "t4 = (tgtSum(18, [1, 2, 3, 4, 5, 10])) # should be 0\n",
    "assert t4 == 0, 'Test 4 failed'\n",
    "\n",
    "t5 = (tgtSum(9, [1, 2, 3, 4, 5, 10])) # should be 0\n",
    "assert t5 == 0, 'Test 5 failed'\n",
    "\n",
    "t6 = (tgtSum(457, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 1\n",
    "assert t6 == 1, 'Test 6 failed'\n",
    "\n",
    "t7 = (tgtSum(512, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 0\n",
    "assert t7 == 0, 'Test 7 failed'\n",
    "\n",
    "t8 = (tgtSum(616, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 1\n",
    "assert t8 == 1, 'Test 8 failed'\n",
    "\n",
    "print('All tests passed (10 points)!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "5c89d7770e76c893fc0ef6d96d2572c5",
     "grade": false,
     "grade_id": "cell-5f50174e27e8d144",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Part (B) \n",
    "\n",
    "Memoize your recurrence by using a memo table of the form $T[(i, j)]$ wherein $0 \\leq i \\leq len(S)$ and $0 \\leq j \\leq \\textsf{tgt}$. It may be helpful to add a function `lookupMemoTable` inside your code to help you handle lookups where $j < 0$. Assume that the target satisfies `tgt >= 0`. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "51ff650a2ed3616b1483781ba1593d95",
     "grade": false,
     "grade_id": "cell-acd6c6b6c9e63ee1",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def memoTargetSum(S, tgt):\n",
    "    n = len(S)\n",
    "    assert tgt >= 0\n",
    "    ## Fill in base case for T[(i,j)] where i == k\n",
    "    T = {} # Memo table initialized as empty dictionary\n",
    "    for j in range(tgt+1):\n",
    "        T[(n,j)] = j\n",
    "    # your code here\n",
    "    for i in range(n-1,-1,-1):\n",
    "        for j in range(tgt+1):\n",
    "            #print(f\"i:{i},tgt:{j}\")\n",
    "            oa = T[(i+1,j)]\n",
    "            if j-S[i]>=0:\n",
    "                ob = T[(i+1,j-S[i])]\n",
    "            else:\n",
    "                ob = T[(i+1,j)]\n",
    "                \n",
    "            T[(i,j)] = min(oa,ob)\n",
    "    \n",
    "    #print(sorted([v,k] for v,k in T.items()))        \n",
    "    return T\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ed2c3429f1e1e52fd2f3e2c49fcb23c1",
     "grade": true,
     "grade_id": "cell-3113771c1e0dee1b",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--test 1--\n",
      "[1, 2, 3, 4, 5, 10] 15\n",
      "--test 2--\n",
      "[1, 2, 3, 4, 5, 10] 26\n",
      "--test3--\n",
      "[11, 23, 37, 48, 94, 152, 230, 312, 339, 413] 457\n",
      "--test4--\n",
      "[11, 23, 37, 48, 94, 152, 230, 312, 339, 413] 512\n",
      "--test5--\n",
      "[11, 23, 37, 48, 94, 152, 230, 312, 339, 413] 616\n",
      "All tests passed (10 points)!\n"
     ]
    }
   ],
   "source": [
    "def checkMemoTblTargetSum(a, tgt, expected):\n",
    "    T = memoTargetSum(a, tgt)\n",
    "    for i in range(len(a)+1):\n",
    "        for j in range(tgt+1):\n",
    "            assert (i, j) in T, f'Memo table fails to have entry for i, j = {(i, j)}'\n",
    "    assert T[(0,tgt)] == expected, f'Expected answer = {expected}, your code returns {T[(0, tgt)]}'\n",
    "    return \n",
    "\n",
    "print('--test 1--')\n",
    "a1 = [1, 2, 3, 4, 5, 10]\n",
    "print(a1, 15)\n",
    "checkMemoTblTargetSum(a1, 15, 0)\n",
    "\n",
    "print('--test 2--')\n",
    "a2= [1, 2, 3, 4, 5, 10]\n",
    "print(a2, 26)\n",
    "checkMemoTblTargetSum(a2, 26, 1)\n",
    "\n",
    "print('--test3--')\n",
    "a3= [11, 23, 37, 48, 94, 152, 230, 312, 339, 413]\n",
    "print(a3, 457)\n",
    "checkMemoTblTargetSum(a3, 457, 1)\n",
    "\n",
    "print('--test4--')\n",
    "print(a3, 512)\n",
    "checkMemoTblTargetSum(a3, 512, 0)\n",
    "\n",
    "print('--test5--')\n",
    "print(a3, 616)\n",
    "checkMemoTblTargetSum(a3, 616, 1)\n",
    "print('All tests passed (10 points)!')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "57aa12c24e4d73e14e45401931cabbae",
     "grade": false,
     "grade_id": "cell-1c36c654c2578daa",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Part (C)\n",
    "\n",
    "Modify your code in part B to record additional information so that you can recover the solution.\n",
    "Implement a function `getBestTargetSum(S, tgt)` that returns a new sub list `T` of `S` so that the sum of elements of `T` is less than or equal to `tgt` and is as close as possible to `tgt`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "f40c788ab5601fbdf7f3c3d381d51a5a",
     "grade": false,
     "grade_id": "cell-60dcc8c2490b23da",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def getBestTargetSum(S, tgt):\n",
    "    k = len(S)\n",
    "    assert tgt >= 0\n",
    "    j = tgt\n",
    "    i=0\n",
    "    T=memoTargetSum(S,tgt)\n",
    "    res = []\n",
    "    while i < k:\n",
    "        cs = T[(i,j)]\n",
    "        cn = T[(i+1,j)]\n",
    "        if cs != cn:\n",
    "            res.append(S[i])\n",
    "            j=j-S[i]\n",
    "        i = i +1\n",
    "    print(res)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "698e0f1bf672540f993cc9f1e2219eec",
     "grade": true,
     "grade_id": "cell-6f68c556faf759c0",
     "locked": true,
     "points": 15,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--test 1--\n",
      "[1, 2, 3, 4, 5, 10] 15\n",
      "[5, 10]\n",
      "Your result: [5, 10]\n",
      "--test 2--\n",
      "[1, 8, 3, 4, 5, 12] 26\n",
      "[1, 5, 8, 12]\n",
      "Your result: [1, 5, 8, 12]\n",
      "--test 3--\n",
      "[8, 3, 2, 4, 5, 7, 12] 38\n",
      "[2, 4, 5, 7, 8, 12]\n",
      "Your result: [2, 4, 5, 7, 8, 12]\n",
      "--test 4 --\n",
      "[0, 1, 2, 7, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 26, 29, 38, 45, 51, 82, 111, 124, 135, 189]\n",
      "[18, 26, 111]\n",
      "Your result: [18, 26, 111]\n",
      "--test 5--\n",
      "[189]\n",
      "Your result: [189]\n",
      "--test 7--\n",
      "[29, 38, 45, 111, 124]\n",
      "Your result: [29, 38, 45, 111, 124]\n",
      "--test 8--\n",
      "[26, 111, 135, 189]\n",
      "Your result: [26, 111, 135, 189]\n",
      "--test 9--\n",
      "[38, 111, 124, 189]\n",
      "Your result: [38, 111, 124, 189]\n",
      "--test 9--\n",
      "[82, 111, 135, 189]\n",
      "Your result: [82, 111, 135, 189]\n",
      "--test 10--\n",
      "[1, 2, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 26, 29, 38, 45, 51, 82, 111, 124, 135, 189]\n",
      "Your result: [1, 2, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 26, 29, 38, 45, 51, 82, 111, 124, 135, 189]\n",
      "All Tests Passed (15 points)\n"
     ]
    }
   ],
   "source": [
    "def checkTgtSumRes(a, tgt,expected):\n",
    "    a = sorted(a)\n",
    "    res = getBestTargetSum(a, tgt)\n",
    "    res = sorted(res)\n",
    "    print('Your result:' , res)\n",
    "    assert tgt - sum(res)  == expected, f'Your code returns result that sums up to {sum(res)}, expected was {expected}'\n",
    "    i = 0\n",
    "    j = 0\n",
    "    n = len(a)\n",
    "    m = len(res)\n",
    "    while (i < n and j < m):\n",
    "        if a[i] == res[j]: \n",
    "            j = j + 1\n",
    "        i = i + 1\n",
    "    assert j == m, 'Your result  {res} is not a subset of {a}'\n",
    "\n",
    "\n",
    "print('--test 1--')\n",
    "a1 = [1, 2, 3, 4, 5, 10]\n",
    "print(a1, 15)\n",
    "checkTgtSumRes(a1, 15, 0)\n",
    "\n",
    "print('--test 2--')\n",
    "a2 = [1, 8, 3, 4, 5, 12]\n",
    "print(a2, 26)\n",
    "checkTgtSumRes(a2, 26, 0)\n",
    "\n",
    "print('--test 3--')\n",
    "a3 = [8, 3, 2, 4, 5, 7, 12]\n",
    "print(a3, 38)\n",
    "checkTgtSumRes(a3, 38, 0)\n",
    "\n",
    "print('--test 4 --')\n",
    "a4 = sorted([1, 10, 19, 18, 12, 11, 0, 9,  16, 17, 2, 7, 14, 29, 38, 45, 13, 26, 51, 82, 111, 124, 135, 189])\n",
    "print(a4)\n",
    "checkTgtSumRes(a4, 155, 0)\n",
    "print('--test 5--')\n",
    "checkTgtSumRes(a4, 189, 0)\n",
    "\n",
    "print('--test 7--')\n",
    "checkTgtSumRes(a4, 347, 0)\n",
    "\n",
    "print('--test 8--')\n",
    "checkTgtSumRes(a4, 461, 0)\n",
    "\n",
    "\n",
    "print('--test 9--')\n",
    "checkTgtSumRes(a4, 462, 0)\n",
    "\n",
    "\n",
    "print('--test 9--')\n",
    "checkTgtSumRes(a4, 517, 0)\n",
    "\n",
    "\n",
    "print('--test 10--')\n",
    "checkTgtSumRes(a4, 975, 3)\n",
    "\n",
    "print('All Tests Passed (15 points)')\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "de3f8bf321213a8c6334371fd269b534",
     "grade": false,
     "grade_id": "cell-5d88b4169e6907e1",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## That's All Folks!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}