supplemental/scans--soln.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-0af27ec9fdec76fd",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "[![Open in Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/hpcgarage/pyboot-g2s3/blob/master/supplemental/scans--soln.ipynb)\n",
    "\n",
    "# Exercises: Scans\n",
    "\n",
    "## (Sample solutions)\n",
    "\n",
    "This problem is about a useful computational primitive known as a _scan_.\n",
    "\n",
    "By way of set up, the module will revolve around a possibly new function for you called `accumulate()`, which is available in the [itertools](https://docs.python.org/3/library/itertools.html) module. Run the following code cell to preload it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-4de5eb06806dd351",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "from itertools import accumulate\n",
    "\n",
    "SAVE_ACCUMULATE = accumulate # You may ignore this line, which some test cells will use"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-13af8be5f40d402f",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Background: Cumulative sums\n",
    "\n",
    "Consider a sequence of $n$ values, $[x_0, x_1, x_2, \\ldots, x_{n-1}]$. Its _cumulative sum_ (or _running sum_) is \n",
    "\n",
    "$$[x_0, \\underbrace{x_0+x_1}, \\underbrace{x_0+x_1+x_2}, \\ldots, \\underbrace{x_0+x_1+x_2+\\cdots+x_{n-1}}]$$.\n",
    "\n",
    "For example, the list\n",
    "\n",
    "```python\n",
    "    [5, 3, -4, 20, 2, 9, 0, -1]\n",
    "```\n",
    "\n",
    "has the following cumulative sum:\n",
    "\n",
    "```python\n",
    "    [5, 8, 4, 24, 26, 35, 35, 34]\n",
    "```\n",
    "\n",
    "The `accumulate()` function makes it easy to compute cumulative sums."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-b45383877e2dfadf",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Exercise 0** (1 point). Run the following code cells."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = accumulate([5, 3, -4, 20, 2, 9, 0, -1])\n",
    "print(\"A:\", A, ':', type(A)) # Note the type of `A`\n",
    "\n",
    "L = list(A)\n",
    "print(\"L:\", L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-0aeb1ddc274962ec",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "> Note: The `accumulate()` function returns a certain object, which is why `list()` is used to convert its result into a list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-3813d7f45f20e341",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Scans\n",
    "\n",
    "A cumulative sum is one example of a more general primitive also known as a _scan_.\n",
    "\n",
    "Let $f(x,y)$ be any associative function of two values. Associative means that $f(f(x, y), z) = f(x, f(y, z))$. For example, addition is associative: suppose that $f(x, y) = x + y$; then it is true that $(x + y) + z = x + (y + z)$. The _scan_ of a sequence with respect to $f$ is\n",
    "\n",
    "$$\\begin{eqnarray}\n",
    "  \\mathrm{scan}([x_0, x_1, \\ldots, x_{n-1}], f) =\n",
    "  & [ & x_0, \\\\\n",
    "  &   & f(x_0, x_1) \\\\\n",
    "  &   & f(f(x_0, x_1), x_2) \\\\\n",
    "  &   & \\vdots, \\\\\n",
    "  &   & f(\\cdots(f(x_0, x_1), x_2), \\cdots), x_{n-1}) \\\\\n",
    "  & ] &\n",
    "\\end{eqnarray}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-341cde48e43f4242",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "The `accumulate()` function lets you implement these kinds of scans easily, too. For example, convince yourself that computing the minimum of two values, $\\min(x, y)$, is also associative. Then you can implement a _minimum scan_, or _min-scan_ for short, as follows:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-78dbf7c9766caa2e",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Exercise 1** (1 point). Run the following cell and make sure its output makes sense to you. (Yes, that's it -- no coding required.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": true,
     "grade_id": "exercise_1_test",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "def min_scan(X):\n",
    "    return list(accumulate(X, min))\n",
    "\n",
    "print('min_scan({}) == {}'.format(L, min_scan(L)))\n",
    "\n",
    "print(\"\\n(Passed!)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-818d646fffcf99b0",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Exercise 2: Line-of-sight** (3 points). Suppose a camera is fixed at a certain height in front of a bunch of obstacles of varying heights at different locations. You wish to determine all locations in which the camera's view is obstructed.\n",
    "\n",
    "For example, in this cartoon, the camera's view is obstructed at all positions starting at 8:\n",
    "\n",
    "![Line of sight](https://cse6040.gatech.edu/datasets/line-of-sight.png)\n",
    "\n",
    "Let `h` be the height of the camera and `X` be a list such that `X[i]` is the height of the obstacle at position `i`. Use `accumulate()` to complete the function, `get_obstruction(X, h)`, so that it returns a list of all positions at which the camera is obstructed. For data corresponding to the above figure, this function would return `[8, 9, 10, 11, 12]`.\n",
    "\n",
    "> An obstacle obstructs the camera if its height is _greater than **or** equal to_ the height of the camera. For this exercise, your code must use `accumulate()` in some way."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "exercise_2",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def get_obstruction(X, h):\n",
    "    ### BEGIN SOLUTION\n",
    "    X_max = accumulate(X, max)\n",
    "    return [i for i, x in enumerate(X_max) if x >= h]\n",
    "    ### END SOLUTION"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": true,
     "grade_id": "exercise_2_test",
     "locked": true,
     "points": 3,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Test cell: `exercise_2_test`\n",
    "\n",
    "def check_get_obstruction(X, h):\n",
    "    global accumulate\n",
    "    print(\"Testing: h={}, X={}\".format(h, X))\n",
    "    try:\n",
    "        del accumulate\n",
    "        pos_test = get_obstruction(X, h)\n",
    "    except NameError as n:\n",
    "        if n.args[0] != \"name 'accumulate' is not defined\":\n",
    "            raise n\n",
    "    else:\n",
    "        assert False, \"*** Did you use `accumulate()`, as required by this exercise? ***\"\n",
    "    finally:\n",
    "        accumulate = SAVE_ACCUMULATE\n",
    "        \n",
    "    pos = get_obstruction(X, h)\n",
    "    print(\"\\t==> Your code's reports these positions as 'obstructed': {}\".format(pos))\n",
    "    for i in range(len(X)):\n",
    "        msg = \"Position i={} is incorrectly labeled.\"\n",
    "        assert X[i] < h or i in pos, msg\n",
    "        \n",
    "# Test 0: Roughly the figure\n",
    "X_test = [5, 1, 3, 3.5, 2, 3, 5.9, 4, 10, 8, 5, 12, 6]\n",
    "h_test = 6\n",
    "check_get_obstruction(X_test, h_test)\n",
    "\n",
    "# Test 1: Random test cases\n",
    "for _ in range(8):\n",
    "    from random import randint\n",
    "    h = randint(1, 5)\n",
    "    n = randint(1, 10)\n",
    "    X = [randint(0, 10) for _ in range(n)]\n",
    "    check_get_obstruction(X, h)\n",
    "    \n",
    "print(\"\\n(Passed!)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Application: When to buy a stock?** Suppose you have the price of a stock on $n$ consecutive days. For example, here is a list of stock prices observed on 14 consecutive days (assume these are numbered from 0 to 13, corresponding to the indices):\n",
    "\n",
    "```python\n",
    "prices = [13, 11, 10, 8, 5, 8, 9, 6, 7, 7, 10, 7, 4, 3]\n",
    "```\n",
    "\n",
    "Suppose you buy on day `i` and sell on day `j`, where `j > i`. Then `prices[j] - prices[i]` measures your _profit_ (or _loss_, if negative)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-b243511f0f9ffc32",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Exercise 3** (5 points). Implement a function, `max_profit(prices)`, to compute the best possible profit you could have made given a list of prices.\n",
    "\n",
    "In the example above, that profit turns out to be 5. That's because you can buy on day 4, whose price is `prices[4] == 5`, and then sell on day 10, whose price is `prices[10] == 10`; it turns out there is no other combination will beat that profit.\n",
    "\n",
    "There are two constraints on your solution:\n",
    "\n",
    "1. You must use `accumulate()`. There is a (relatively) simple and fast solution that does so.\n",
    "2. If only a loss is possible, your function should return 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "exercise_3",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def max_profit(prices):\n",
    "    ### BEGIN SOLUTION\n",
    "    lowest_prices = accumulate(prices, min)\n",
    "    gains = [p - l for p, l in zip(prices, lowest_prices)]\n",
    "    max_gain = max([0] + gains)\n",
    "    return max_gain\n",
    "    ### END SOLUTION"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": true,
     "grade_id": "exercise_3_test",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Test cell: `exercise_3_test`\n",
    "\n",
    "def check_profit(prices):\n",
    "    global accumulate\n",
    "    print(\"\\nTesting: prices={}\".format(prices))\n",
    "    try:\n",
    "        del accumulate\n",
    "        profit_test = max_profit(prices)\n",
    "    except NameError as n:\n",
    "        if n.args[0] != \"name 'accumulate' is not defined\":\n",
    "            raise n\n",
    "    else:\n",
    "        assert False, \"*** Did you use `accumulate()`, as required by this exercise? ***\"\n",
    "    finally:\n",
    "        accumulate = SAVE_ACCUMULATE\n",
    "\n",
    "    profit = max_profit(prices)\n",
    "    print(\"\\t==> Your code's maximum profit: {}\".format(profit))\n",
    "    \n",
    "    # Do an exhaustive search -- a correct, but highly inefficient, algorithm\n",
    "    true_max = 0\n",
    "    i_max, j_max = -1, -1\n",
    "    for i in range(len(prices)):\n",
    "        for j in range(i, len(prices)):\n",
    "            gain_ij = prices[j] - prices[i]\n",
    "            if gain_ij > true_max:\n",
    "                i_max, j_max, true_max = i, j, gain_ij\n",
    "    if i_max >= 0 and j_max >= 0:\n",
    "        explain = \"Buy on day {} at price {} and sell on {} at {}.\".format(i_max, prices[i_max],\n",
    "                                                                           j_max, prices[j_max])\n",
    "    else:\n",
    "        explain = \"No buying options!\"\n",
    "    print(\"\\t==> True max profit: {} ({})\".format(true_max, explain))\n",
    "    assert profit == true_max, \"Your code's calculation does not match.\"\n",
    "\n",
    "check_profit([13, 11, 10, 8, 5, 8, 9, 6, 7, 7, 10, 7, 4, 3])\n",
    "check_profit([5, 4, 3, 2, 1])\n",
    "check_profit([1, 2, 3, 4, 5])\n",
    "\n",
    "for _ in range(8): # Random test cases\n",
    "    from random import randint\n",
    "    num_days = randint(1, 10)\n",
    "    prices = [randint(1, 20) for _ in range(num_days)]\n",
    "    check_profit(prices)\n",
    "\n",
    "print(\"\\n(Passed!)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-52a7122f70cf4e61",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Fin!** If you've reached this point and all tests above pass, you are ready to submit your solution to this problem. Don't forget to save you work prior to submitting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbgrader": {
     "grade": true,
     "grade_id": "ran_to_completion",
     "locked": true,
     "points": 0,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "print(\"\\n(This notebook ran to completion.)\")"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Create Assignment",
  "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}