csci3155

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3d02434f",
   "metadata": {},
   "source": [
    "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel $\\rightarrow$ Restart) and then **run all cells** (in the menubar, select Cell $\\rightarrow$ Run All).\n",
    "\n",
    "Make sure you fill in any place that says `???`, `YOUR CODE HERE`, \"???\", \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "8a89a7aa",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mNAME\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"Jack Sangdahl\"\u001b[39m\n",
       "\u001b[36mCOLLABORATORS\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"N/A\"\u001b[39m"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val NAME = \"Jack Sangdahl\"\n",
    "val COLLABORATORS = \"N/A\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d009c835",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d34c7c8-c787-4f41-bd3a-5628797aa728",
   "metadata": {},
   "source": [
    "# Exercise: Expressions and Data Types\n",
    "\n",
    "<!-- 3 Expressions -->\n",
    "\n",
    "<!-- 4 Binding and Scope -->\n",
    "\n",
    "The purpose of this assignment is to warm-up with Scala.\n",
    "\n",
    "### Learning Goals\n",
    "\n",
    "The primary learning goals of this assignment are to build intuition for\n",
    "the following:\n",
    "\n",
    "-   thinking in terms of types, values, and expressions; and\n",
    "-   imperative iteration.\n",
    "\n",
    "### Instructions\n",
    "\n",
    "This assignment asks you to write Scala code. There are restrictions\n",
    "associated with how you can solve these problems. Please pay careful\n",
    "heed to those. If you are unsure, ask the course staff.\n",
    "\n",
    "Note that `???` indicates that there is a missing function or code\n",
    "fragment that needs to be filled in. In Scala, it is also an expression\n",
    "that throws a `NotImplementedError` exception. Make sure that you remove\n",
    "the `???` and replace it with the answer.\n",
    "\n",
    "Use the test cases provided to test your implementations. You are also\n",
    "encouraged to write your own test cases to help debug your work.\n",
    "However, please delete any extra cells you may have created lest they\n",
    "break an autograder.\n",
    "\n",
    "## Type Checking\n",
    "\n",
    "In the following, I have left off the return type of function `g`. The\n",
    "body of `g` is well-typed if we can come up with a valid return type. In\n",
    "this question, we will reason for ourselves that `g` is indeed\n",
    "well-typed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "0db88593",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mg\u001b[39m"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def g(x: Int) = /*e1*/({\n",
    "  // env1\n",
    "  val (a, b) = /*e2*/(\n",
    "    // env2\n",
    "    (1, (x, 3))\n",
    "  )\n",
    "  /*e3*/(\n",
    "    // env3\n",
    "    if (x == 0) (b, 1) else (b, a + 2)\n",
    "  )\n",
    "})"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27d6ff35-074c-4171-a7f5-a035015e7b83",
   "metadata": {},
   "source": [
    "We have added parentheses around 3 key sub-expressions of the body of\n",
    "`g` (e.g., `/*e1*/(`$\\ldots$`)`) and noted that there are corresponding\n",
    "environments (e.g., `// env1` for each sub-expression).\n",
    "\n",
    "### Q1.1: What is the type environment `env1`? Briefly explain.\n",
    "\n",
    "Use either format shown in the notes (e.g.,\n",
    "$[ x_1 : \\tau_1, \\ldots, x_n : \\tau_n ]$)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "672c616d-04fb-41cf-aad5-6f025548b7b7",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "e41ca86f62e024565d1f2956f3950f48",
     "grade": true,
     "grade_id": "q1_1",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "The type environment of `env1` alone is $[\\:\\mathtt{env1} \\mapsto\\mathtt{Int}\\:]$. At this point, the only variable in scope is the parameter `x: Int`, so `env1` also maps to `Int`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d577d0ca-7375-4e10-a89f-6a9f067a8f9f",
   "metadata": {},
   "source": [
    "### Q1.2: What is the type environment `env2`? Briefly explain."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "62ae6788-7ed6-4acd-9d5c-40192d303dc9",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "4660b9558a8195d26712214909a62db2",
     "grade": true,
     "grade_id": "q1_2",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "The type environment of `env2` is $[\\:\\mathtt{env2} \\mapsto\\mathtt{Int}\\:]$. `env2` references the known type of `x: Int`, which also maps `env2` to `Int`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93547002-40ae-42f1-a910-38131a7d26f6",
   "metadata": {},
   "source": [
    "### Q1.3: Derive the type of expression `e2`.\n",
    "\n",
    "Showing the type for each sub-expression of `e2`; stop when you reach\n",
    "literals or variable uses."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4114c6c1-7098-466c-bf92-69aa4a321664",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "315ba92969984b267763af81ebd0f5d0",
     "grade": true,
     "grade_id": "q1_3",
     "locked": false,
     "points": 10,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "```scala\n",
    "(1, (x, 3)): (Int, (Int, Int))\n",
    "- if 1: Int\n",
    "- if (x, 3): (Int, Int)\n",
    "  - if x: Int\n",
    "  - if 3: Int\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "934b39f4-9eb5-4186-8e8d-f05f24d0f578",
   "metadata": {},
   "source": [
    "#### Notes\n",
    "\n",
    "Use the format shown in the notes. Here’s such a derivation for the type\n",
    "of the expression `(1 + 2) + (3 + 4)`.\n",
    "\n",
    "``` scala\n",
    "(1 + 2) + (3 + 4): Int\n",
    "- if 1 + 2: Int\n",
    "  - if 1: Int\n",
    "  - if 2: Int\n",
    "- if 3 + 4: Int\n",
    "  - if 3: Int\n",
    "  - if 4: Int\n",
    "```\n",
    "\n",
    "### Q1.4: What is the type environment `env3`? Briefly explain."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e94876a-32b9-477c-9aa1-91253dde0d30",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "e5b9bc3f55c403acbbb1e709d2b68f12",
     "grade": true,
     "grade_id": "q1_4",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "The type environment of `env3` alone is $[\\:\\mathtt{env3} \\mapsto\\mathtt{x: Int, a: Int, b: (Int, Int)}\\:]$. At this point, `env3` includes the variables `x`, `a`, and `b`. We know `x: Int` from the function argument, `a: Int` from the tuple deconstruction, and `b: (Int, Int)` also from the tuple deconstruction."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7faf5604-c103-44b1-a711-334dfdab5d6c",
   "metadata": {},
   "source": [
    "### Q1.5: Derive the type of expression `e3`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ceae2d55-bef9-4cc5-a3dc-cfd11db90e43",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "52869852b70e53b19066a880678a23b7",
     "grade": true,
     "grade_id": "q1_5",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "```scala\n",
    "if (x == 0) (b, 1) else (b, a + 2): ((Int, Int), Int)\n",
    "- if x == 0: Boolean\n",
    "  - if (b, 1): Int\n",
    "    - if b: Int\n",
    "    - if 1: Int\n",
    "  - if (b, a + 2): Int\n",
    "    - if b: Int\n",
    "    - if a + 2: Int\n",
    "      - if a: Int\n",
    "      - if 2: Int\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bab903c4-188f-46ed-86dd-9495e781ff51",
   "metadata": {},
   "source": [
    "### Q1.6: Confirm your derivations by adding type assertions to each sub-expression of `g` and adding the return type of `g`.\n",
    "\n",
    "That is, replace sub-expressions $e$ of `g` with expressions $e$ `:`\n",
    "$\\tau$. You may need to add some parentheses—`(` $e$ `:` $\\tau$ `)`—to\n",
    "preserve the syntactic structure. Skip adding typing assertions for\n",
    "literals and variable uses.\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "b472b0a7",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "c4abe7222641b8ec119ec31036e39b95",
     "grade": true,
     "grade_id": "q1_6",
     "locked": false,
     "points": 9,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mg\u001b[39m"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def g(x: Int) = /*e1*/({\n",
    "  // env1\n",
    "  val (a: Int, b: (Int, Int)) = /*e2*/(\n",
    "    // env2\n",
    "    (1, (x, 3)): (Int, (Int, Int))\n",
    "  )\n",
    "  /*e3*/(\n",
    "    // env3\n",
    "    if (x == 0: Boolean) (b, 1): ((Int, Int), Int) else (b, a + 2): ((Int, Int), Int)\n",
    "  ): ((Int, Int), Int)\n",
    "}): ((Int, Int), Int) "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5e75af2-a72c-4fed-a247-aa90d3f8f0ad",
   "metadata": {},
   "source": [
    "*Hint*: There are 8 sub-expressions that are not literals nor variable\n",
    "uses that need typing assertions (i.e., $e$ `:` $\\tau$), plus 1 more\n",
    "annotation for the return type of `g`.\n",
    "\n",
    "## Unit Testing\n",
    "\n",
    "When starting to program in the large, it is useful to use a testing\n",
    "framework to manage tests and integrate with IDEs. One that is commonly\n",
    "used in Scala is [ScalaTest](https://www.scalatest.org/).\n",
    "\n",
    "While it is somewhat overkill for testing small exercises like the ones\n",
    "to come, we practice here writing tests using ScalaTest.\n",
    "\n",
    "To load the ScalaTest library, run the following cell:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "8fea5968",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "bdf4aa1ba5caa128e0dbcd6cc1ad5766",
     "grade": false,
     "grade_id": "testing",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mimport \u001b[39m\u001b[36mRUN this cell FIRST before testing\n",
       "import $ivy.$                                , org.scalatest._, events._, flatspec._\n",
       "\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mreport\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36massertPassed\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mtest\u001b[39m"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// RUN this cell FIRST before testing\n",
    "import $ivy.`org.scalatest::scalatest:3.2.19`, org.scalatest._, events._, flatspec._\n",
    "def report(suite: Suite) = suite.execute(stats = true)\n",
    "def assertPassed(suite: Suite) =\n",
    "  suite.run(None, Args(new Reporter {\n",
    "    def apply(e: Event) = e match {\n",
    "      case e @ (_: TestFailed) => assert(false, s\"${e.message} (${e.testName})\")\n",
    "      case _ => ()\n",
    "    }\n",
    "  }))\n",
    "def test(suite: Suite) = {\n",
    "  report(suite)\n",
    "  assertPassed(suite)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67ac4efd-c505-4a4f-a6f5-91610f977849",
   "metadata": {},
   "source": [
    "### Q2.1: Unit Test `plus`\n",
    "\n",
    "For this question, **edit the next two code cells** to fix the\n",
    "implementation of `plus` and add the appropriate assertion for the third\n",
    "test case `\"add (3,4) == 7\"`.\n",
    "\n",
    "Our goal is unit test the following complicated function (that we’ve\n",
    "gotten wrong!):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "6bc42853",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mplus\u001b[39m"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def plus(n: Int, m: Int): Int = n + m"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2fd19eae-bb49-4616-94f4-e2383aad90c9",
   "metadata": {},
   "source": [
    "To use ScalaTest, we create “Spec” objects using ScalaTest methods like\n",
    "`should` that define an embedded domain-specific language (DSL) for\n",
    "defining tests:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "1255cbba",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n",
      "\u001b[32mcmd52$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mplus\u001b[0m\n",
      "\u001b[32m- should add 1 + 1 == 2\u001b[0m\n",
      "\u001b[32m- should add 2 + 2 == 4\u001b[0m\n",
      "\u001b[32m- should add 3 + 4 == 7\u001b[0m\n",
      "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 3\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mplusSuite\u001b[39m: \u001b[32mAnyFlatSpec\u001b[39m = cmd52$Helper$$anon$1"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val plusSuite = new AnyFlatSpec {\n",
    "  // Define a *subject* to test (e.g., \"plus\").\n",
    "  // After `should`, name a test (e.g, \"add (1, 1) == 2\").\n",
    "  // After `in`, specify assertions (e.g., `assert(plus(1,1) == 2))\n",
    "  \"plus\" should \"add 1 + 1 == 2\" in {\n",
    "    // Specify assertions here.\n",
    "    assert(plus(1,1) == 2)\n",
    "  }\n",
    "\n",
    "  it should \"add 2 + 2 == 4\" in {\n",
    "    // It is convenient to distinguish the expected result from the code that\n",
    "    // you're testing, which affects the error messages when the test fails.\n",
    "    assertResult(2 + 2) {\n",
    "      plus(2,2)\n",
    "    }\n",
    "  }\n",
    "  it should \"add 3 + 4 == 7\"  in {\n",
    "    assertResult(3 + 4) {\n",
    "      plus(3, 4)\n",
    "    }\n",
    "  }\n",
    "}\n",
    "report(plusSuite)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "27368277",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "8ac2636aa17b31fca777bf3064b8d491",
     "grade": true,
     "grade_id": "q2_1",
     "locked": true,
     "points": 3,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres53\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@48f724de"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "assertPassed(plusSuite)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be1d876b-25dc-451a-86db-ed1cf1fed54e",
   "metadata": {},
   "source": [
    "## Run-Time Library\n",
    "\n",
    "Most languages come with a standard library with support for things like\n",
    "data structures, mathematical operators, string processing, etc.\n",
    "Standard library functions may be implemented in the object language\n",
    "(perhaps for portability) or the meta language (perhaps for\n",
    "implementation efficiency).\n",
    "\n",
    "For this question, we will implement some library functions in Scala,\n",
    "our meta language, that we can imagine will be part of the run-time for\n",
    "our object language interpreter. In actuality, the main purpose of this\n",
    "exercise is to warm-up with Scala programming.\n",
    "\n",
    "### Q3.1: Write and test a function `abs`\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "3f001698",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "d1bacc19634bfb1bf864bd58b41906c4",
     "grade": false,
     "grade_id": "q3_1_code",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mabs\u001b[39m"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def abs(n: Double): Double = ({\n",
    "    if (n < 0) {\n",
    "        -n\n",
    "    } else {\n",
    "        n\n",
    "    }\n",
    "})"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71c5328d-b26d-497d-adaf-6ef22d22688f",
   "metadata": {},
   "source": [
    "that returns the absolute value of `n`. This a function that takes a\n",
    "value of type `Double` and returns a value of type `Double`. This\n",
    "function corresponds to the JavaScript library function `Math.abs`.\n",
    "\n",
    "#### Notes\n",
    "\n",
    "-   Do not use any Scala library functions.\n",
    "\n",
    "#### Tests\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "d913e614",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 4\u001b[0m\n",
      "\u001b[32mcmd55$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mabs\u001b[0m\n",
      "\u001b[32m- should abs(2) == 2\u001b[0m\n",
      "\u001b[32m- should abs(-2) == 2\u001b[0m\n",
      "\u001b[32m- should abs(0) == 0\u001b[0m\n",
      "\u001b[32m- should abs(1) == 1\u001b[0m\n",
      "\u001b[36mRun completed in 3 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 4\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 4, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mabsSuite\u001b[39m: \u001b[32mAnyFlatSpec\u001b[39m = cmd55$Helper$$anon$1"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val absSuite = new AnyFlatSpec {\n",
    "  \"abs\" should \"abs(2) == 2\" in {\n",
    "     assert(abs(2) == 2)\n",
    "  }\n",
    "  it should \"abs(-2) == 2\" in {\n",
    "     assert(abs(-2) == 2)\n",
    "  }\n",
    "  it should \"abs(0) == 0\" in {\n",
    "     assert(abs(0) === 0)\n",
    "  }\n",
    "  it should \"abs(1) == 1\" in {\n",
    "    assert(abs(1) === 1)\n",
    "  }\n",
    "}\n",
    "report(absSuite)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "1956942b",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "8ae14654f39c831149cca3cd7bc9901f",
     "grade": true,
     "grade_id": "q3_1",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres56\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@4fd24e85"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "assertPassed(absSuite)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21898c2c-2b50-42c1-85f9-df4be93e8284",
   "metadata": {},
   "source": [
    "### Q3.2: Write and test a function `xor`\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "3c119212",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ac179e4aa90d501026fc34ffbf524ab7",
     "grade": false,
     "grade_id": "q3_2_code",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mxor\u001b[39m"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def xor(a: Boolean, b: Boolean): Boolean = a ^ b"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b47755a-a0e7-44ee-acc5-10a06d925697",
   "metadata": {},
   "source": [
    "that returns the exclusive-or of `a` and `b`. The exclusive-or returns\n",
    "`true` if and only if exactly one of `a` or `b` is `true`.\n",
    "\n",
    "#### Notes\n",
    "\n",
    "-   For practice, do not use the Boolean operators. Instead, only use\n",
    "    the `if`- expression and the Boolean literals (i.e., `true` or\n",
    "    `false`).\n",
    "\n",
    "#### Tests\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "f723c395",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 4\u001b[0m\n",
      "\u001b[32mcmd58$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mxor\u001b[0m\n",
      "\u001b[32m- should !xor(true, true)\u001b[0m\n",
      "\u001b[32m- should xor(true, false)\u001b[0m\n",
      "\u001b[32m- should xor(false, true)\u001b[0m\n",
      "\u001b[32m- should !xor(false, false)\u001b[0m\n",
      "\u001b[36mRun completed in 11 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 4\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 4, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mxorSuite\u001b[39m: \u001b[32mAnyFlatSpec\u001b[39m = cmd58$Helper$$anon$1"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val xorSuite = new AnyFlatSpec {\n",
    "  \"xor\" should \"!xor(true, true)\" in {\n",
    "    assert(!xor(true, true))\n",
    "  }\n",
    "  it should \"xor(true, false)\" in {\n",
    "    assert(xor(true, false))\n",
    "  }\n",
    "  it should \"xor(false, true)\" in {\n",
    "    assert(xor(false, true))\n",
    "  }\n",
    "  it should \"!xor(false, false)\" in {\n",
    "    assert(!xor(false, false))\n",
    "  }\n",
    "}\n",
    "report(xorSuite)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "5fc09530",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "475a7a4bd08579befea92b998fc9a712",
     "grade": true,
     "grade_id": "q3_2",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres59\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@2780f927"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "assertPassed(xorSuite)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b0a894d-67f5-480a-bbcb-2abe33b45784",
   "metadata": {},
   "source": [
    "## Imperative Iteration and Complexity\n",
    "\n",
    "### Q4.1: Write a function `filterPairsByBound`\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "a9436132",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ed640d35faac5ce44926effc28995737",
     "grade": false,
     "grade_id": "q4_1_code",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfilterPairsByBound\u001b[39m"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def filterPairsByBound(list: List[(Int, Int)], k: Int): List[(Int, Int)] =\n",
    "    list.filter { // iterate through the tuples in list\n",
    "        case (n1, n2) => // for each pair (n1, n2)...\n",
    "            // return appropriate value when leq k \n",
    "            // using our abs() function from Q3.1\n",
    "            abs(n1 - n2) <= k\n",
    "    }"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d95cdad4-4de8-440e-8a25-b1f9d901091a",
   "metadata": {},
   "source": [
    "that given a list of pairs of integers, for example,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "15116cf9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36minput1_l\u001b[39m: \u001b[32mList\u001b[39m[(\u001b[32mInt\u001b[39m, \u001b[32mInt\u001b[39m)] = \u001b[33mList\u001b[39m(\n",
       "  (\u001b[32m1\u001b[39m, \u001b[32m5\u001b[39m),\n",
       "  (\u001b[32m2\u001b[39m, \u001b[32m7\u001b[39m),\n",
       "  (\u001b[32m15\u001b[39m, \u001b[32m14\u001b[39m),\n",
       "  (\u001b[32m18\u001b[39m, \u001b[32m19\u001b[39m),\n",
       "  (\u001b[32m14\u001b[39m, \u001b[32m28\u001b[39m),\n",
       "  (\u001b[32m0\u001b[39m, \u001b[32m0\u001b[39m),\n",
       "  (\u001b[32m35\u001b[39m, \u001b[32m24\u001b[39m)\n",
       ")"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val input1_l = List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46a2bbe6-ac0c-4fd1-a4e2-15f66b895bf8",
   "metadata": {},
   "source": [
    "output a list consisting of just those pairs $(n_1, n_2)$ in the\n",
    "original list wherein $|n_1 - n_2| \\leq k$ where $k$ is an integer given\n",
    "as input. Ensure that the order of the elements in the output list is\n",
    "the same as that in the input list.\n",
    "\n",
    "For the list `input1`, the expected output, with `k == 1`, the expected\n",
    "output is as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "c378241a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36minput1_k\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m1\u001b[39m\n",
       "\u001b[36moutput1\u001b[39m: \u001b[32mList\u001b[39m[(\u001b[32mInt\u001b[39m, \u001b[32mInt\u001b[39m)] = \u001b[33mList\u001b[39m((\u001b[32m15\u001b[39m, \u001b[32m14\u001b[39m), (\u001b[32m18\u001b[39m, \u001b[32m19\u001b[39m), (\u001b[32m0\u001b[39m, \u001b[32m0\u001b[39m))"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val input1_k = 1\n",
    "val output1 = List( (15,14), (18,19), (0,0) )\n",
    "assert(filterPairsByBound(input1_l, input1_k) == output1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b55b49e4-2a4b-4dc6-80de-c600151fcf5a",
   "metadata": {},
   "source": [
    "With `k == 4`, the expected output is as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "d05fe5b9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36minput2_k\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m4\u001b[39m\n",
       "\u001b[36moutput2\u001b[39m: \u001b[32mList\u001b[39m[(\u001b[32mInt\u001b[39m, \u001b[32mInt\u001b[39m)] = \u001b[33mList\u001b[39m((\u001b[32m1\u001b[39m, \u001b[32m5\u001b[39m), (\u001b[32m15\u001b[39m, \u001b[32m14\u001b[39m), (\u001b[32m18\u001b[39m, \u001b[32m19\u001b[39m), (\u001b[32m0\u001b[39m, \u001b[32m0\u001b[39m))"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val input2_k = 4\n",
    "val output2 = List( (1, 5), (15, 14), (18, 19), (0,0) )\n",
    "assert(filterPairsByBound(input1_l, input2_k) == output2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "984c452b-5302-48a6-8fe1-e1a1ff22cbaa",
   "metadata": {},
   "source": [
    "#### Notes\n",
    "\n",
    "-   Your function must be called `filterPairsByBound` with two\n",
    "    arguments: (1) a list of pairs of integers, and (2) the $k$ value.\n",
    "    It must return a list of pairs of integers.\n",
    "-   You can use `for`-loops (or `foreach`) and the following operators\n",
    "    for concatenating elements to a list:\n",
    "    -   `:+` appends an element to the back of a list.\n",
    "    -   `:::` concatenates two lists together.\n",
    "    -   `::` prepends an element to the front of a list.\n",
    "-   You can use the `List` API method `reverse`. You may also use the\n",
    "    `Int` `abs` method to obtain the absolute value of an integer (or\n",
    "    use your `abs` function above).\n",
    "-   You should not use any other `List` API functions including\n",
    "    `filter`, `map`, `foldLeft`, `foldRight`, etc. Plenty of time to\n",
    "    learn them properly later on.\n",
    "-   Do not try to convert your list to an array or vector so that you\n",
    "    can mutate it.\n",
    "-   If you are unable to solve the problem without violating the\n",
    "    restrictions or unsure, ask us.\n",
    "-   You will need to use `var` given the above restrictions.\n",
    "\n",
    "#### Hints\n",
    "\n",
    "-   In Scala, pairs of integers have the type `(Int, Int)`.\n",
    "-   A list containing pairs of integers has the type `List[(Int, Int)]`.\n",
    "-   Recall from the notes, here is how one iterates over the elements of\n",
    "    a list in Scala:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "757f5f83",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mlist\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m3\u001b[39m)"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val list = List(1, 2, 3)\n",
    "\n",
    "for (elt <- list) {\n",
    "  // do stuff with elt\n",
    "  println(elt)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8155fd8-8f76-4131-86e7-3d9bc3f583b4",
   "metadata": {},
   "source": [
    "-   Append an element to the end of a list and update a `var`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "d20926f0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"jp-RenderedText\">\n",
       "<pre><code><span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">resultList</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">List</span></span>[<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span>] = <span style=\"color: yellow\"><span class=\"ansi-yellow-fg\">List</span></span>(<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">1</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">2</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">3</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span>)\n",
       "<span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">elt</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span> = <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span></code></pre>\n",
       "</div>"
      ],
      "text/plain": [
       "\u001b[36mresultList\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m3\u001b[39m, \u001b[32m42\u001b[39m)\n",
       "\u001b[36melt\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m42\u001b[39m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "var resultList = List(1, 2, 3)\n",
    "val elt = 42\n",
    "\n",
    "resultList = resultList :+ elt"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5143c58d-3849-4d7c-ad58-7021e92a1a92",
   "metadata": {},
   "source": [
    "-   Or, append an element to the end of a list using list concatenation\n",
    "    and update a `var`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "6b76748c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"jp-RenderedText\">\n",
       "<pre><code><span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">resultList</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">List</span></span>[<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span>] = <span style=\"color: yellow\"><span class=\"ansi-yellow-fg\">List</span></span>(<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">1</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">2</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">3</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span>)\n",
       "<span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">elt</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span> = <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span></code></pre>\n",
       "</div>"
      ],
      "text/plain": [
       "\u001b[36mresultList\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m3\u001b[39m, \u001b[32m42\u001b[39m)\n",
       "\u001b[36melt\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m42\u001b[39m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "var resultList = List(1, 2, 3)\n",
    "val elt = 42\n",
    "\n",
    "resultList = resultList ::: List(elt)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0cf8d689-25e9-4899-b369-228fb4a60c06",
   "metadata": {},
   "source": [
    "-   Prepend an element and update a `var`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "a223964a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"jp-RenderedText\">\n",
       "<pre><code><span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">resultList</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">List</span></span>[<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span>] = <span style=\"color: yellow\"><span class=\"ansi-yellow-fg\">List</span></span>(<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">1</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">2</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">3</span></span>)\n",
       "<span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">elt</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span> = <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span></code></pre>\n",
       "</div>"
      ],
      "text/plain": [
       "\u001b[36mresultList\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m42\u001b[39m, \u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m3\u001b[39m)\n",
       "\u001b[36melt\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m42\u001b[39m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "var resultList = List(1, 2, 3)\n",
    "val elt = 42\n",
    "\n",
    "resultList = elt :: resultList"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7cadcb01-c735-4b13-8c34-ed06fefe0e39",
   "metadata": {},
   "source": [
    "-   *Warning*: The `:+`, `:::`, or other operations appending operations\n",
    "    take linear $O(n)$ time where $n$ is the length of the (left) list.\n",
    "    Thus, we will often try to avoid using these operations, but it is\n",
    "    ok to use it for this particular part.\n",
    "\n",
    "#### Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "40a6d538",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "c9601d100de72d011a23f82aa2e58a37",
     "grade": true,
     "grade_id": "q4_1",
     "locked": true,
     "points": 5,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 6\u001b[0m\n",
      "\u001b[32mcmd68$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mfilterPairsByBound\u001b[0m\n",
      "\u001b[32m- should test1\u001b[0m\n",
      "\u001b[32m- should test2\u001b[0m\n",
      "\u001b[32m- should test3\u001b[0m\n",
      "\u001b[32m- should test4\u001b[0m\n",
      "\u001b[32m- should test5\u001b[0m\n",
      "\u001b[32m- should test6\u001b[0m\n",
      "\u001b[36mRun completed in 9 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 6\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 6, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mres68\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@d75bc07"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  \"filterPairsByBound\" should \"test1\" in {\n",
    "    val lst1 = List((1,1), (-1,1), (1,-1))\n",
    "    assertResult( List((1,1)) ){ filterPairsByBound(lst1,1) }\n",
    "   }\n",
    "\n",
    "  it should \"test2\" in {\n",
    "    val lst2 = List((1,2), (2,1), (1,0), (0,1), (1,1))\n",
    "    assertResult( lst2 ){ filterPairsByBound(lst2,1) }\n",
    "  }\n",
    "\n",
    "  it should \"test3\" in {\n",
    "    val lst3 = List((1,5), (5,1))\n",
    "    assertResult( Nil ){ filterPairsByBound(lst3,1) }\n",
    "  }\n",
    "\n",
    "  it should \"test4\" in {\n",
    "    val lst4 = List((2,5), (1,2), (-5,-4), (4,1))\n",
    "    assertResult( List((1,2), (-5,-4)) ){ filterPairsByBound(lst4,1) }\n",
    "  }\n",
    "\n",
    "  it should \"test5\" in {\n",
    "    val lst5 = List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) )\n",
    "    assertResult( List((1, 5), (15, 14), (18, 19), (0,0)) ){ filterPairsByBound(lst5,4) }\n",
    "  }\n",
    "\n",
    "  it should \"test6\" in {\n",
    "    val lst6 = List((1, 2), (2, 1), (1,0), (0,1), (1,1))\n",
    "    assertResult( List((1,1)) ){ filterPairsByBound(lst6,0) }\n",
    "  }\n",
    "})"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5712b57c-1bd3-41a8-9c55-722b85829805",
   "metadata": {},
   "source": [
    "### Q4.2: Write a function `filterPairsByBoundLinearTime`\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "fadb020d",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "8725d2da34598302b7ff7ab5876da03b",
     "grade": false,
     "grade_id": "q4_2_code",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfilterPairsByBoundLinearTime\u001b[39m"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def filterPairsByBoundLinearTime(list: List[(Int, Int)], k: Int): List[(Int, Int)] = {\n",
    "    // helper function to recursively process appropriate elements in list\n",
    "    def filterHelper(remaining: List[(Int, Int)], result: List[(Int, Int)]): List[(Int, Int)] = remaining match {\n",
    "        case Nil => // Nil represents empty set - do nothing\n",
    "            result\n",
    "        // iterate through list beginning at start (or rather current) element\n",
    "        case (n1, n2) :: tail =>\n",
    "            if (abs(n1 - n2) <= k)\n",
    "                // if necessary condition is met, prepend to result\n",
    "                filterHelper(tail, (n1, n2) :: result)\n",
    "            else\n",
    "                // otherwise continue to next element\n",
    "                filterHelper(tail, result)\n",
    "    }\n",
    "    filterHelper(list, Nil).reverse\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0fa83488-63be-43d5-9905-3f2b4706318d",
   "metadata": {},
   "source": [
    "If you followed the hint and ignored the linear-time warning in the\n",
    "previous part\n",
    "<a href=\"#sec-filterPairsByBound\" class=\"quarto-xref\">Section 4.1</a>,\n",
    "then you would have used the `:+` or `:::` operation to append an\n",
    "element to the end of a list at each step.\n",
    "\n",
    "``` scala\n",
    "for (... <- list) {\n",
    "  // iterate over a loop\n",
    "  ...\n",
    "  newList = newList :+ newElement // This takes O(length of newList).\n",
    "}\n",
    "```\n",
    "\n",
    "Each `:+` or `:::` operation requires a full list traversal to find the\n",
    "end of `newList` and then append to it. The overall algorithm thus\n",
    "requires $O(n^2)$ time where is the length of the original `list` (also\n",
    "the number of loop iterations).\n",
    "\n",
    "To illustrate, cut-and-paste and then run this code in a new test cell.\n",
    "Just remember to delete that cell before you submit. It will take a long\n",
    "time to run.\n",
    "\n",
    "``` scala\n",
    "// Create a list of 1,000,000 pairs\n",
    "val longTestList = (1 to 1000000).map(x => (x, x - 1)).toList\n",
    "// Run the function you wrote\n",
    "filterPairsByBound(longTestList, 1)\n",
    "// This will take a long time to finish.\n",
    "```\n",
    "\n",
    "In this problem, we wish to implement a function\n",
    "`filterPairsByBoundLinearTime` that solves the exact same problem as the\n",
    "previous part\n",
    "<a href=\"#sec-filterPairsByBound\" class=\"quarto-xref\">Section 4.1</a>\n",
    "but takes time linear in the size of the input list.\n",
    "\n",
    "To do so, we would like you to use the `::` (read “cons”) operator on a\n",
    "list that prepends an element to the front of a list, instead of `:+` or\n",
    "`:::` that appends to the back of a list.\n",
    "\n",
    "You will want to use the `List` `reverse` API method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "e3731008",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mlist\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m5\u001b[39m, \u001b[32m6\u001b[39m, \u001b[32m7\u001b[39m, \u001b[32m8\u001b[39m)\n",
       "\u001b[36mr\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m8\u001b[39m, \u001b[32m7\u001b[39m, \u001b[32m6\u001b[39m, \u001b[32m5\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m1\u001b[39m)"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val list = List(1, 2, 5, 6, 7, 8)\n",
    "val r = list.reverse"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f9f4725-99b1-41e4-88a5-174ad8818a50",
   "metadata": {},
   "source": [
    "The `r` has the reverse of `list`, and it works in linear time in the\n",
    "length of `list`.\n",
    "\n",
    "The restrictions remain the same as the previous part\n",
    "<a href=\"#sec-filterPairsByBound\" class=\"quarto-xref\">Section 4.1</a>,\n",
    "but we would like you to focus on ensuring that your solution runs in\n",
    "linear time.\n",
    "\n",
    "#### Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "90d2d800",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "c1afc073bb37fd79685ece1caf82e854",
     "grade": true,
     "grade_id": "q4_2",
     "locked": true,
     "points": 7,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 6\u001b[0m\n",
      "\u001b[32mcmd71$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mfilterPairsByBoundLinearTime\u001b[0m\n",
      "\u001b[32m- should test1\u001b[0m\n",
      "\u001b[32m- should test2\u001b[0m\n",
      "\u001b[32m- should test3\u001b[0m\n",
      "\u001b[32m- should test4\u001b[0m\n",
      "\u001b[32m- should test5\u001b[0m\n",
      "\u001b[32m- should test6\u001b[0m\n",
      "\u001b[36mRun completed in 4 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 6\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 6, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mres71\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@41a47f32"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  \"filterPairsByBoundLinearTime\" should \"test1\" in {\n",
    "    val lst1 = List((1,1), (-1,1), (1,-1))\n",
    "    assertResult( List((1,1)) ){ filterPairsByBoundLinearTime(lst1,1) }\n",
    "   }\n",
    "\n",
    "  it should \"test2\" in {\n",
    "    val lst2 = List((1,2), (2,1), (1,0), (0,1), (1,1))\n",
    "    assertResult( lst2 ){ filterPairsByBoundLinearTime(lst2,1) }\n",
    "  }\n",
    "\n",
    "  it should \"test3\" in {\n",
    "    val lst3 = List((1,5), (5,1))\n",
    "    assertResult( Nil ){ filterPairsByBoundLinearTime(lst3,1) }\n",
    "  }\n",
    "\n",
    "  it should \"test4\" in {\n",
    "    val lst4 = List((2,5), (1,2), (-5,-4), (4,1))\n",
    "    assertResult( List((1,2), (-5,-4)) ){ filterPairsByBoundLinearTime(lst4,1) }\n",
    "  }\n",
    "\n",
    "  it should \"test5\" in {\n",
    "    val lst5 = List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) )\n",
    "    assertResult( List((1, 5), (15, 14), (18, 19), (0,0)) ){ filterPairsByBoundLinearTime(lst5,4) }\n",
    "  }\n",
    "\n",
    "  it should \"test6\" in {\n",
    "    val lst6 = List((1, 2), (2, 1), (1,0), (0,1), (1,1))\n",
    "    assertResult( List((1,1)) ){ filterPairsByBoundLinearTime(lst6,0) }\n",
    "  }\n",
    "})"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c75c291-9711-4901-92f6-ef093fb92a6a",
   "metadata": {},
   "source": [
    "## Submission\n",
    "\n",
    "#### Submission Instructions\n",
    "\n",
    "If you are a University of Colorado Boulder student, we use Gradescope\n",
    "for assignment submission. In summary,\n",
    "\n",
    "-   [ ] Work on a copy of this Jupyter notebook.\n",
    "-   [ ] Submit it to the corresponding Gradescope assignment entry for\n",
    "    grading.\n",
    "\n",
    "#### GitHub and Gradescope\n",
    "\n",
    "We use GitHub Classroom for assignment distribution, which gives you a\n",
    "private GitHub repository to work on your assignment. While using GitHub\n",
    "is perhaps overkill for this assignment, it does give you the ability to\n",
    "version and save incremental progress on GitHub (lest your laptop fails)\n",
    "and makes it easier to get help from the course staff. It will also\n",
    "become particularly useful when more files are involved, and it is never\n",
    "too early to get used to the workflow professional software engineers\n",
    "use with Git.\n",
    "\n",
    "To use use GitHub and Gradescope,\n",
    "\n",
    "-   [ ] Create a private GitHub repository by clicking on a GitHub\n",
    "    Classroom link from the corresponding Canvas assignment entry.\n",
    "-   [ ] Clone your private GitHub repository to your development\n",
    "    environment (using the `<> Code` button on GitHub to get the\n",
    "    repository URL).\n",
    "-   [ ] Work on the copy of this Jupyter notebook from your cloned\n",
    "    repository. Use Git to save versions on GitHub (e.g., `git add`,\n",
    "    `git commit`, `git push` on the command line, via JupyterLab, or via\n",
    "    VSCode).\n",
    "-   [ ] Submit to the corresponding Gradescope assignment entry for\n",
    "    grading by choosing GitHub as the submission method.\n",
    "\n",
    "You need to have a GitHub identity and must have your full name in your\n",
    "GitHub profile in case we need to associate you with your submissions."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala",
   "language": "scala",
   "name": "scala"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".sc",
   "mimetype": "text/x-scala",
   "name": "scala",
   "nbconvert_exporter": "script",
   "version": "2.13.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}