CSCI3155_Assignment5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "6a3575958dc77c3cec8d44edb8f99479",
     "grade": false,
     "grade_id": "cell-4dfd42d74736d7f0",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Before you turn this problem in, make sure everything runs as expected. **Restart the kernel and run all cells** (in the menubar, select Kernel$\\rightarrow$Restart & Run All).\n",
    "\n",
    "Make sure you fill in any place that says `YOUR CODE HERE ???` or \"YOUR ANSWER HERE\". Code cells are autograded, and if the test cells don't run all the way to the line that  prints \"Tests Passed (# points)\", you will not recieve any point for that test."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "4df85f20298c52cd3bc2ab3294e0294f",
     "grade": false,
     "grade_id": "cell-554205c9fbf8e007",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CSCI 3155: Assignment 5\n",
    "\n",
    "Topics Covered: Operations on inductive definitions, building an interpreter, big step operational semantics and using map, foldLeft and filter functions to replace loops."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Name__: Lucas Laughlin"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "75eb79a0577aaad1ab57992c3b3d9b45",
     "grade": false,
     "grade_id": "cell-523e63f33a38d446",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mpassed\u001b[39m"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// TEST HELPER\n",
    "def passed(points: Int) {\n",
    "    require(points >=0)\n",
    "    if (points == 1) print(s\"Tests Passed (1 point)\")\n",
    "    else print(s\"Tests Passed ($points points)\") \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "a542d3ae63e7a0081383673b67f6713c",
     "grade": false,
     "grade_id": "cell-86df80222a5e29f3",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Problem 1: Manipulating ASTs, Inference Rules (30 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "a44e45ed35b38ceed5884f1ec993b4dc",
     "grade": false,
     "grade_id": "cell-7b3432cb0c0460ce",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### 1A: Derivatives of Expressions (20 points)\n",
    "\n",
    "We have defined a grammar for arithmetic expressions in our class notes. For this problem, you will be writing an _automatic differentiation_ method that, given an expression `e` which involves just a single identifier `x` (no need to check this fact), will return an expression for `de/dx`, the derivative of `e` with respect to `x`.\n",
    "\n",
    "Eg., `e = Sine(Mult(Identifier(\"x\"), Const(2.0)))` should return `Mult(Const(2.0), Cosine(  Mult(Identifier(\"x\"), Const(2.0)))`.  In plain math, $\\frac{d \\sin(2x)}{dx} = 2 \\cos( 2x) $\n",
    "\n",
    "We will write down the inference rules for derivative, as follows.\n",
    "\n",
    "A rule for constants ($\\frac{dc}{dx} = 0, c \\in \\mathbb{R}$)\n",
    "\n",
    "$\\begin{array}{c}\n",
    "\\\\\n",
    "\\hline \n",
    "\\text{derivative}( \\texttt{Const(f)} , x) = \\texttt{Const(0.0)} \\\\\n",
    "\\end{array} \\mathbf{(Constant)}$      \n",
    "\n",
    "A rule for identifiers $\\frac{dx}{dx} = 1, \\frac{dy}{dx} = 0$ for $y \\not= x$.\n",
    "\n",
    "$\\begin{array}{c}\n",
    "\\\\\n",
    "\\hline \n",
    "\\text{derivative}( \\texttt{Ident(s)} , x) = \\left\\{ \\begin{array}{ll} \\texttt{Const(1.0)} & x == s \\\\\n",
    "\\texttt{Const(0.0)} & \\text{otherwise} \\end{array} \\right.\\\\\n",
    "\\end{array} \\mathbf{(Identifier)}  \\;\\;\\;\n",
    "$\n",
    "\n",
    "A rule for plus $\\frac{d}{dx} (e_1 + e_2) = \\frac{de_1}{dx} + \\frac{de_2}{dx}$.\n",
    "\n",
    "$ \\begin{array}{c}\n",
    "\\text{derivative}(\\texttt{e1}, x) = \\texttt{f1},\\;\\;\\text{derivative}(\\texttt{e2}, x) = \\texttt{f2}\\\\\n",
    "\\hline\n",
    "\\text{derivative}(\\texttt{Plus(e1, e2)}, x) = \\texttt{Plus(f1, f2)} \\\\\n",
    "\\end{array} \\mathbf{(Plus)} $\n",
    "\n",
    "A rule for multiplication: $\\frac{d}{dx} (e_1 e_2) = e_2 \\frac{de_1}{dx} + e_1 \\frac{de_2}{dx}$.\n",
    "\n",
    "$ \\begin{array}{c}\n",
    "\\text{derivative}(\\texttt{e1}, x) = \\texttt{f1},\\;\\;\\text{derivative}(\\texttt{e2}, x) = \\texttt{f2}\\\\\n",
    "\\hline\n",
    "\\text{derivative}(\\texttt{Mult(e1, e2)}, x) = \\texttt{Plus(Mult(f1, e2), Mult(f2, e1))} \\\\\n",
    "\\end{array} \\mathbf{(Mult)} $\n",
    "\n",
    "A rule for division $\\frac{d}{dx} \\left(\\frac{e_1}{e_2}\\right) = \\frac{\\frac{de_1}{dx}}{e_2} - \\frac{e_1 \\frac{d e_2}{dx}}{e_2^2}$\n",
    "\n",
    "$ \\begin{array}{c}\n",
    "\\text{derivative}(\\texttt{e1}, x) = \\texttt{f1},\\;\\;\\text{derivative}(\\texttt{e2}, x) = \\texttt{f2}\\\\\n",
    "\\hline\n",
    "\\text{derivative}(\\texttt{Div(e1, e2)}, x) = \\texttt{Minus(Div(f1, e2), Div(Mult(e1, f2), Mult(e2, e2)))} \\\\\n",
    "\\end{array} \\mathbf{(Div)} $\n",
    "\n",
    "A rule for exponentiation $\\frac{d}{dx} \\left(e^{e_1}\\right) = e^{e_1} \\frac{de_1}{dx}$\n",
    "\n",
    "$ \\begin{array}{c}\n",
    "\\text{derivative}(\\texttt{e1}, x) = \\texttt{f1}\\\\\n",
    "\\hline\n",
    "\\text{derivative}(\\texttt{Exp(e1)}, x) = \\texttt{Mult(Exp(e1), f1)} \\\\\n",
    "\\end{array} \\mathbf{(Exp)} $\n",
    "\n",
    "The rules for $\\mathbf{Minus}$, $\\mathbf{Sine}$, and $\\mathbf{Cosine}$ are left for you to write.\n",
    "You do not need to write your solution for these rules in this notebook, __but__, you do need to give them in code below.\n",
    "(Don't forget about the chain rule!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "02c64445eae9901295238649bbb28e54",
     "grade": false,
     "grade_id": "cell-5a6ded9a6f746cee",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mExpr\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mConst\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mIdent\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mPlus\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mMinus\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mMult\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mDiv\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mSine\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mCosine\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mExp\u001b[39m"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait Expr\n",
    "case class Const(f: Double) extends Expr\n",
    "case class Ident(s: String) extends Expr\n",
    "case class Plus(e1: Expr, e2: Expr) extends Expr\n",
    "case class Minus(e1: Expr, e2: Expr) extends Expr\n",
    "case class Mult(e1: Expr, e2: Expr) extends Expr\n",
    "case class Div(e1: Expr, e2: Expr) extends Expr\n",
    "case class Sine(e: Expr) extends Expr\n",
    "case class Cosine(e: Expr) extends Expr\n",
    "case class Exp(e: Expr) extends Expr\n",
    "// We will skip over Log(e: Expr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "3ef175a900ea13a88766e4a65bdf8944",
     "grade": false,
     "grade_id": "cell-3856b2383d61965d",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Write a function `derivativeExpr` that calculates the derivative of an expression\n",
    "`e` w.r.t a given identifier as a string `x`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "6ff055b85255d75ac73cebc86333267b",
     "grade": false,
     "grade_id": "2a-answer",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mderivativeExpr\u001b[39m"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def derivativeExpr(e: Expr, x: String): Expr =\n",
    "    e match{\n",
    "        case Const(f) => return Const(0.0)\n",
    "        case Ident(s) if (s==x) => return Const(1.0)\n",
    "        case Ident(s) if (s!=x) => return Const(0.0)\n",
    "        case Plus(e1, e2) => return Plus(derivativeExpr(e1, x),derivativeExpr(e2, x))\n",
    "        case Minus(e1, e2) => return Minus(derivativeExpr(e1, x),derivativeExpr(e2, x))\n",
    "        case Sine(e) => return Cosine(e)\n",
    "        case Cosine(e) => return Minus(Const(0),Sine(e))\n",
    "        case Exp(e1) => return Mult(derivativeExpr(e1, x),Exp(e1))\n",
    "        case Mult(e1, e2) => return Plus(Mult(derivativeExpr(e1, x), e2), Mult(derivativeExpr(e2, x), e1))\n",
    "        case Div(e1, e2) => return Minus(Div(derivativeExpr(e1, x), e2), Div(Mult(e1, derivativeExpr(e2, x)), Mult(e2, e2)))\n",
    "    }\n",
    "       \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "9d0d058206486a5847bd484cc9ee3bed",
     "grade": false,
     "grade_id": "cell-5ebe5c717def6816",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mevalExpr\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mtestExpressions\u001b[39m\n",
       "\u001b[36mallVals\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mDouble\u001b[39m] = \u001b[33mList\u001b[39m(\n",
       "  \u001b[32m-5.0\u001b[39m,\n",
       "  \u001b[32m-4.5\u001b[39m,\n",
       "  \u001b[32m-4.0\u001b[39m,\n",
       "  \u001b[32m-3.5\u001b[39m,\n",
       "  \u001b[32m-3.0\u001b[39m,\n",
       "  \u001b[32m-2.5\u001b[39m,\n",
       "  \u001b[32m-1.9\u001b[39m,\n",
       "  \u001b[32m-1.4\u001b[39m,\n",
       "  \u001b[32m-1.0\u001b[39m,\n",
       "  \u001b[32m-0.5\u001b[39m,\n",
       "  \u001b[32m0.1\u001b[39m,\n",
       "  \u001b[32m0.5\u001b[39m,\n",
       "  \u001b[32m1.0\u001b[39m,\n",
       "  \u001b[32m1.5\u001b[39m,\n",
       "  \u001b[32m2.0\u001b[39m,\n",
       "  \u001b[32m2.5\u001b[39m,\n",
       "  \u001b[32m3.0\u001b[39m,\n",
       "  \u001b[32m3.5\u001b[39m,\n",
       "  \u001b[32m4.0\u001b[39m,\n",
       "  \u001b[32m4.5\u001b[39m,\n",
       "  \u001b[32m5.0\u001b[39m\n",
       ")"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// BEGIN TESTS\n",
    "\n",
    "// TEST HELPERS\n",
    "def evalExpr (e: Expr, env: Map[String, Double]): Double = e match {\n",
    "    case Const (f) => f\n",
    "    case Ident (str) => { if (env.contains(str)){\n",
    "                                env(str)\n",
    "                            } else {\n",
    "        throw new IllegalArgumentException(s\"Environment does not contain mapping for $str\")\n",
    "    }\n",
    "                        }\n",
    "    case Plus(e1, e2) => {\n",
    "        (evalExpr(e1, env)) + (evalExpr(e2, env))\n",
    "    }\n",
    "    \n",
    "    case Minus(e1, e2) => {\n",
    "        (evalExpr(e1, env)) - (evalExpr(e2, env))\n",
    "    }\n",
    "    \n",
    "    case Mult(e1, e2) => {\n",
    "        (evalExpr(e1, env)) * (evalExpr(e2, env))\n",
    "    }\n",
    "    \n",
    "    case Div(e1, e2) => {\n",
    "        (evalExpr(e1, env)) / (evalExpr(e2, env))\n",
    "    }\n",
    "    \n",
    "    case Exp(e) => math.exp( evalExpr(e, env))\n",
    "    \n",
    "    case Sine(e) => math.sin( evalExpr(e, env))\n",
    "    \n",
    "    case Cosine(e) => math.cos(evalExpr(e, env))\n",
    "}\n",
    "\n",
    "def testExpressions(exp: Expr, deriv_expected: Expr, testVals: List[Double]): Boolean = {\n",
    "    val tol: Double = 1E-06\n",
    "    val deriv_act = derivativeExpr(exp, \"x\")\n",
    "    testVals forall { \n",
    "            x => {\n",
    "              val res = math.abs( evalExpr(deriv_act, Map(\"x\"-> x)) - evalExpr(deriv_expected, Map(\"x\" -> x)) ) <= tol\n",
    "              if (!res) { println(s\"Failed at $x\")}\n",
    "              res\n",
    "            }\n",
    "    }\n",
    "}\n",
    "\n",
    "val allVals = List(-5.0, -4.5, -4.0, -3.5, -3.0, -2.5, -1.9, -1.4, -1.0, -0.5, 0.1, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5, 5.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "d5cfdeed2d1e9f8ea0840d539e4688e5",
     "grade": true,
     "grade_id": "2a-test-ident_plus_const",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tests Passed (5 points)"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36me1\u001b[39m: \u001b[32mPlus\u001b[39m = \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m2.0\u001b[39m))"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val e1 = Plus(Ident(\"x\"), Const(2.0))\n",
    "assert(testExpressions(e1, Const(1.0), allVals ), s\"Test 1 Failed -- Input: $e1 \")\n",
    "\n",
    "passed(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ac714ecfc2bc24ba724aae240f231a0e",
     "grade": true,
     "grade_id": "2a-test-minus_trig",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tests Passed (5 points)"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36me2\u001b[39m: \u001b[32mPlus\u001b[39m = \u001b[33mPlus\u001b[39m(\u001b[33mCosine\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)), \u001b[33mSine\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))\n",
       "\u001b[36med2\u001b[39m: \u001b[32mMinus\u001b[39m = \u001b[33mMinus\u001b[39m(\u001b[33mCosine\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)), \u001b[33mSine\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val e2 = Plus(Cosine(Ident(\"x\")), Sine(Ident(\"x\")))\n",
    "val ed2 = Minus(Cosine(Ident(\"x\")), Sine(Ident(\"x\")))\n",
    "assert(testExpressions(e2, ed2, allVals), s\"Test 2 Failed: Input is $e2\")\n",
    "\n",
    "passed(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "30d239b4c5fd9ab434be2210110c57c1",
     "grade": true,
     "grade_id": "2a-test-exp_mult",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tests Passed (5 points)"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mx\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)\n",
       "\u001b[36me3\u001b[39m: \u001b[32mExp\u001b[39m = \u001b[33mExp\u001b[39m(\u001b[33mMult\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))\n",
       "\u001b[36med3\u001b[39m: \u001b[32mMult\u001b[39m = \u001b[33mMult\u001b[39m(\n",
       "  \u001b[33mMult\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m2.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)),\n",
       "  \u001b[33mExp\u001b[39m(\u001b[33mMult\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))\n",
       ")"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val x = Ident(\"x\")\n",
    "val e3 = Exp(Mult(x, x))\n",
    "val ed3 = Mult(Mult(Const(2.0), x), e3)\n",
    "assert(testExpressions(e3, ed3, allVals), s\"Test 3 Failed: Input is $e3\")\n",
    "\n",
    "passed(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "8bc4e683d9a853baaa10566d4d5f78ba",
     "grade": true,
     "grade_id": "cell-98105bfe539405d9",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tests Passed (5 points)"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36me4\u001b[39m: \u001b[32mDiv\u001b[39m = \u001b[33mDiv\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m2.0\u001b[39m)))\n",
       "\u001b[36med4\u001b[39m: \u001b[32mDiv\u001b[39m = \u001b[33mDiv\u001b[39m(\n",
       "  \u001b[33mConst\u001b[39m(\u001b[32m2.0\u001b[39m),\n",
       "  \u001b[33mMult\u001b[39m(\u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m2.0\u001b[39m)), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m2.0\u001b[39m)))\n",
       ")\n",
       "\u001b[36me5\u001b[39m: \u001b[32mSine\u001b[39m = \u001b[33mSine\u001b[39m(\n",
       "  \u001b[33mMult\u001b[39m(\n",
       "    \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mCosine\u001b[39m(\u001b[33mDiv\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))), \u001b[33mCosine\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m1.0\u001b[39m)))),\n",
       "    \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)\n",
       "  )\n",
       ")\n",
       "\u001b[36med5\u001b[39m: \u001b[32mCosine\u001b[39m = \u001b[33mCosine\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val e4 = Div(x, Plus(x, Const(2.0)))\n",
    "val ed4 = Div(Const(2.0), Mult(Plus(x, Const(2.0)), Plus(x, Const(2.0))) )\n",
    "assert(testExpressions(e4, ed4, allVals), s\"Test 4 Failed: Input is $e4\")\n",
    "\n",
    "\n",
    "val e5 = Sine(Mult(Exp(Minus( Cosine(Div(x,x)), Cosine(Const(1.0)) )), x))\n",
    "val ed5 = Cosine(x)\n",
    "assert(testExpressions(e5, ed5, allVals), s\"Test 5 Failed: Input is $e5\")\n",
    "\n",
    "passed(5)\n",
    "// END TESTS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "fd82910cdc248d45d6ce06c20c010530",
     "grade": false,
     "grade_id": "cell-c9182e4cf28a06d9",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### 1B: Newton's Algorithm Reloaded (10 points)\n",
    "\n",
    "Let's revisit problem 5 from assignment 1. Back in assignment 1, we hard coded the\n",
    "expression and its derivative. Here, we will use our `Expr` abstract syntax to \n",
    "define expressions and use the function you wrote in 2A to compute derivatives.\n",
    "You may also use the `evalExpr` function provided below.\n",
    "\n",
    "Newton invented the Newton-Raphson method for solving an equation. \n",
    "We are going to ask you to write some code to solve equations.\n",
    "\n",
    "`solveEquation(e: Expr, x0: Double, maxIters: Int = 1000)`\n",
    "\n",
    "Assume that the input expression has involves just one variable \"x\".\n",
    "\n",
    "To solve an equation of the form\n",
    "\n",
    "$$ x^2 - 3x + 2 == 0$$\n",
    "\n",
    "with initial guess at the solution: say $$x_0 = 4.5$$,\n",
    "\n",
    "We will input `val e = Plus(Minus(Mult(Ident(\"x\"), Ident(\"x\")), Mult(Const(3.0), Ident(\"x\"))), Const(2.0))`\n",
    "into the function\n",
    "\n",
    "`solveEquation( e, 1.5, 1000)`\n",
    "\n",
    "Each time we have the $i^{th}$ guess $x_i$, we update it as\n",
    "\n",
    "$$ x_{i+1} = x_i - \\frac{f(x_i)}{f'(x_i)} $$\n",
    "\n",
    "For our equation, $f(x) = x^2 - 3x +2$ and $f'(x) = 2 x - 3$ ( $f'$ is the derivative of $f$).\n",
    "\n",
    "Thus, our update equation is \n",
    "$$ x_{i+1} = x_i - \\frac{x_i^2 - 3 x_i + 2}{2 x_i - 3}$$.\n",
    "\n",
    "We stop whenever $|f(x_i)| \\leq 10^{-8}$ : i.e, we are very close to a root of the function\n",
    "_or_ $ i \\geq \\text{maxIters}$. \n",
    "\n",
    "Gory details are here:\n",
    "http://www.math.ubc.ca/~anstee/math104/newtonmethod.pdf\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "4f9451bf212f34911173618ed2c26edf",
     "grade": false,
     "grade_id": "cell-818418bd7ec6d27e",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mevalExpr\u001b[39m"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def evalExpr (e: Expr, env: Map[String, Double]): Double = e match {\n",
    "    case Const (f) => f\n",
    "    case Ident (str) => { if (env.contains(str)){\n",
    "                                env(str)\n",
    "                            } else {\n",
    "        throw new IllegalArgumentException(s\"Environment does not contain mapping for $str\")\n",
    "    }\n",
    "                        }\n",
    "    case Plus(e1, e2) => {\n",
    "        (evalExpr(e1, env)) + (evalExpr(e2, env))\n",
    "    }\n",
    "    \n",
    "    case Minus(e1, e2) => {\n",
    "        (evalExpr(e1, env)) - (evalExpr(e2, env))\n",
    "    }\n",
    "    \n",
    "    case Mult(e1, e2) => {\n",
    "        (evalExpr(e1, env)) * (evalExpr(e2, env))\n",
    "    }\n",
    "    \n",
    "    case Div(e1, e2) => {\n",
    "        (evalExpr(e1, env)) / (evalExpr(e2, env))\n",
    "    }\n",
    "    \n",
    "    case Exp(e) => math.exp( evalExpr(e, env))\n",
    "    \n",
    "    case Sine(e) => math.sin( evalExpr(e, env))\n",
    "    \n",
    "    case Cosine(e) => math.cos(evalExpr(e, env))\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "9d838f72967241caec1467266d844202",
     "grade": false,
     "grade_id": "2b-answer",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msolveEquation\u001b[39m"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def solveEquation(e: Expr, x0: Double, maxIters:Int = 1000): Double  = {\n",
    "    \n",
    "    val nextX = x0 - evalExpr(Div(e, derivativeExpr(e, \"x\")), Map(\"x\" -> x0))\n",
    "    \n",
    "    if (Math.abs(evalExpr(e, Map(\"x\" -> nextX))) < scala.math.pow(10, -8)) return nextX\n",
    "    else return solveEquation( e, nextX, maxIters-1)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "c94f6e98d82a028be2e0c67e63453d05",
     "grade": true,
     "grade_id": "2b-test",
     "locked": true,
     "points": 10,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tests Passed (10 points)"
     ]
    },
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mcheckSolution\u001b[39m\n",
       "\u001b[36me1\u001b[39m: \u001b[32mPlus\u001b[39m = \u001b[33mPlus\u001b[39m(\n",
       "  \u001b[33mMinus\u001b[39m(\u001b[33mMult\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)), \u001b[33mMult\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m3.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))),\n",
       "  \u001b[33mConst\u001b[39m(\u001b[32m2.0\u001b[39m)\n",
       ")\n",
       "\u001b[36mv1\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m2.000000000000081\u001b[39m\n",
       "\u001b[36mx\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)\n",
       "\u001b[36me2\u001b[39m: \u001b[32mMinus\u001b[39m = \u001b[33mMinus\u001b[39m(\u001b[33mSine\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)), \u001b[33mPlus\u001b[39m(\u001b[33mCosine\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))\n",
       "\u001b[36mv2\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m-1.2587281774926768\u001b[39m\n",
       "\u001b[36me3\u001b[39m: \u001b[32mMinus\u001b[39m = \u001b[33mMinus\u001b[39m(\u001b[33mExp\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)), \u001b[33mConst\u001b[39m(\u001b[32m5.0\u001b[39m))\n",
       "\u001b[36mv3\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m1.6094379124370815\u001b[39m\n",
       "\u001b[36me4\u001b[39m: \u001b[32mMinus\u001b[39m = \u001b[33mMinus\u001b[39m(\n",
       "  \u001b[33mPlus\u001b[39m(\u001b[33mExp\u001b[39m(\u001b[33mSine\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))), \u001b[33mExp\u001b[39m(\u001b[33mCosine\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "  \u001b[33mConst\u001b[39m(\u001b[32m2.0\u001b[39m)\n",
       ")\n",
       "\u001b[36mv4\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m2.6608333315872805\u001b[39m\n",
       "\u001b[36me5\u001b[39m: \u001b[32mMinus\u001b[39m = \u001b[33mMinus\u001b[39m(\n",
       "  \u001b[33mMult\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mSine\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))),\n",
       "  \u001b[33mPlus\u001b[39m(\u001b[33mCosine\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)), \u001b[33mConst\u001b[39m(\u001b[32m5.0\u001b[39m))\n",
       ")\n",
       "\u001b[36mv5\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m21.80586857241418\u001b[39m"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// BEGIN TESTS\n",
    "def checkSolution(e: Expr, v: Double): Boolean = {\n",
    "    val y = evalExpr(e, Map{\"x\" -> v}) \n",
    "    math.abs(y) <= 1e-08\n",
    "}\n",
    "\n",
    "val e1 = Plus(Minus(Mult(Ident(\"x\"), Ident(\"x\")), Mult(Const(3.0), Ident(\"x\"))), Const(2.0))\n",
    "val v1 = solveEquation(e1, 10.0, 1000)\n",
    "\n",
    "assert(checkSolution(e1, v1), s\"Test 1 failed: $e1 == 0, your code returned $v1 with f(x) = ${evalExpr(e1, Map{\"x\" -> v1}) }\")\n",
    "\n",
    "// Sine(x)  - Cos(x) - x == 0\n",
    "val x = Ident(\"x\")\n",
    "val e2 = Minus(Sine(x), Plus(Cosine(x), x))\n",
    "val v2 = solveEquation(e2, 1.4)\n",
    "assert(checkSolution(e2, v2), s\"Test 2 failed: $e2 == 0, your code returned $v2 with f(x) = ${evalExpr(e2, Map{\"x\" -> v2}) }\")\n",
    "\n",
    "// e^x - 5.0 = 0\n",
    "val e3 = Minus(Exp(x), Const(5.0))\n",
    "val v3 = solveEquation(e3, 2.0)\n",
    "assert(checkSolution(e3, v3), s\"Test 3 failed: $e3 == 0, your code returned $v3 with f(x) = ${evalExpr(e3, Map{\"x\" -> v3}) }\")\n",
    "\n",
    "// e^cos(x) + e^sin(x) - 2.0 = 0\n",
    "\n",
    "val e4 = Minus(Plus(Exp(Sine(x)), Exp(Cosine(x))), Const(2.0))\n",
    "val v4 = solveEquation(e4, 1.8)\n",
    "assert(checkSolution(e4, v4), s\"Test 3 failed: $e4 == 0, your code returned $v4 with f(x) = ${evalExpr(e4, Map{\"x\" -> v4}) }\")\n",
    "\n",
    "\n",
    "// x sin(x) -  cos(x) - 5.0\n",
    "val e5 = Minus(Mult(x, Sine(x)), Plus(Cosine(x), Const(5.0)))\n",
    "val v5 = solveEquation(e5, 1.8)\n",
    "assert(checkSolution(e5, v5), s\"Test 3 failed: $e5 == 0, your code returned $v5 with f(x) = ${evalExpr(e5, Map{\"x\" -> v5}) }\")\n",
    "\n",
    "passed(10)\n",
    "// END TESTS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "bb4d1f6c23e25e5dfcc5e36c4ea64152",
     "grade": false,
     "grade_id": "cell-c90311f0f12f79f2",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Problem 2: map, filter, reduce on containers (25 points)\n",
    "\n",
    "Solve the problems using a combination of map, filter and foldLeft/foldRight opertions over lists. The use of mutables, recursion, For/While loops is forbidden for this problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "cd04a1864fb152c8eb50d0008aee3e32",
     "grade": false,
     "grade_id": "cell-57eb1b5c1720b797",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "\n",
    "### 2A: Count how many whitespaces in a string (5 points)\n",
    "\n",
    "Write a function `countWhiteSpaces` that will count how many characters in a string are white spaces ` ` or `\\t`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "251ed8d85f5d1d4253ef2b85a1c7d905",
     "grade": false,
     "grade_id": "cell-d07d79524c90fd4e",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mcountWhiteSpaces\u001b[39m"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def countWhiteSpaces(s: String): Int =\n",
    "    s.filter(x => x==' ').foldLeft(0)((acc, x)=> acc+1)\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "f12f54f2a742949f78dd8a79f9172d87",
     "grade": true,
     "grade_id": "cell-054acf67575fc99c",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tests Passed (5 points)"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mt1\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m0\u001b[39m\n",
       "\u001b[36mt2\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m5\u001b[39m\n",
       "\u001b[36mt3\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m6\u001b[39m\n",
       "\u001b[36mt4\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m6\u001b[39m"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// BEGIN TESTS\n",
    "val t1  = countWhiteSpaces(\"Hello\")\n",
    "assert(t1 == 0, s\"Test1: String whould have 0 white spaces. Your code returned $t1\")\n",
    "val t2 = countWhiteSpaces(\"Hello World this is Sriram Speaking\")\n",
    "assert(t2 ==5, \"Test 2: String should have 5 white spaces.Your code returned $t2 \")\n",
    "val t3 = countWhiteSpaces(\"No Non Nons Nonse Nonsen Nonsens Nonsense!!\")\n",
    "assert(t3 ==6, \"Test 3\")\n",
    "val t4 = countWhiteSpaces(\"      \")\n",
    "assert(t4==6, s\"Test 4: String  (6spaces) should have  white spaces.Your code returned $t4 \")\n",
    "\n",
    "passed(5)\n",
    "// END TESTS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "edaa421f8cd291f025a4e3b55683bc38",
     "grade": false,
     "grade_id": "cell-cce284d399573f50",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### 2B: Sum of Even  Elements Minus Sum of Odd Elements (5 points)\n",
    "\n",
    "Given a list of length n, write a function that returns the sum of even elements minus sum of odd elements of a list. It must return $0$ for the empty list.\n",
    "\n",
    "eg., input `List(1, 3, 5, 4, 5, 2, 1, 0)`. Output `  (4 + 2 + 0) - (1 + 3 + 5 + 5 + 1) = -9`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "22dc8410a26c77261eb6cf91c799bb1b",
     "grade": false,
     "grade_id": "cell-332c55ac9d70c435",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msumOfEvenMinusOdd\u001b[39m"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sumOfEvenMinusOdd(l: List[Int]) : Int = l.filter(x => x%2 == 0).sum - l.filter(x => Math.abs(x%2) == 1).sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "5cafad4d0086d47c0e69a6244235ec63",
     "grade": true,
     "grade_id": "cell-b37de6cd26982543",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tests Passed (5 points)"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mi1\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m-9\u001b[39m\n",
       "\u001b[36mi2\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m18\u001b[39m\n",
       "\u001b[36mi3\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m-133\u001b[39m"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// BEGIN TESTS\n",
    "val i1 = sumOfEvenMinusOdd(List(1,3,5,4,5,2,1,0))\n",
    "assert(i1 == -9, \"Test 1 Failed\")\n",
    "\n",
    "val i2 = sumOfEvenMinusOdd(List(2,4,5,6,7,8,10))\n",
    "assert(i2 == 18, \"Test 2 Failed\")\n",
    "\n",
    "val i3 = sumOfEvenMinusOdd(List(109, 19, 12, 1, -5, -120, -15, 30,-33,-13, 12, 19, 3, 18, 1, -1))\n",
    "assert(i3 == -133, \"Test 3 Failed\")\n",
    "\n",
    "passed(5)\n",
    "// END TESTS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "f45c848fd82a3da3f54e4dfa7c963f43",
     "grade": false,
     "grade_id": "cell-1de14d7f940a930f",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### 2C: sum of odd index elements - sum of even index elements in a list (5 points)\n",
    "\n",
    "Given a list $L= [a(1), ..., a(n)]$ of $n$ integers, find the  the sum\n",
    "of elements at even positions (a[0], a[2], ..., ) minus the sum of elements at\n",
    "odd positions (a[1], a[3], ... ) :\n",
    "(a[0] + a[2]+a[4] + .... ) - (a[1] + a[3]  + .... )\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "577851f9108a29a9dc306671dfac9cf7",
     "grade": false,
     "grade_id": "cell-0c984f492b25b8b4",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msumOfEvenIndicesMinusOdd\u001b[39m"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sumOfEvenIndicesMinusOdd(l: List[Int]): Int = {\n",
    "    l.foldLeft((0, 0)) { case ((sum, index), x) =>\n",
    "        if(index%2==0) (sum+x, index+1)\n",
    "        else (sum-x, index+1)\n",
    "        }._1\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "7325864ab4cbbd0ad4343f1309134532",
     "grade": true,
     "grade_id": "cell-8c49d31044f1e0ae",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tests Passed (5 points)"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mt1\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m-3\u001b[39m\n",
       "\u001b[36mt2\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m-190\u001b[39m\n",
       "\u001b[36mt3\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m0\u001b[39m\n",
       "\u001b[36mt4\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m0\u001b[39m\n",
       "\u001b[36mt5\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m10\u001b[39m"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// BEGIN TESTS\n",
    "val t1 = sumOfEvenIndicesMinusOdd(List(1, 2, 3, 4, 5, 6))\n",
    "assert(t1 == -3, \"Test 1 failed\")\n",
    "val t2 = sumOfEvenIndicesMinusOdd(List(10, 200))\n",
    "assert(t2 == -190, \"Test 2 failed\")\n",
    "val t3 = sumOfEvenIndicesMinusOdd(List(0, 20, 0, 20, 0, 20, 20, 0, 20, 0, 20, 0))\n",
    "assert(t3 == 0, \"Test 3 failed\")\n",
    "val t4 = sumOfEvenIndicesMinusOdd(List())\n",
    "assert(t4 == 0, \"Test 4 failed\")\n",
    "val t5 = sumOfEvenIndicesMinusOdd(List(10))\n",
    "assert(t5 == 10, \"Test 5 failed\")\n",
    "\n",
    "passed(5)\n",
    "// END TESTS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "821215983b87369f9204bdc79be0c412",
     "grade": false,
     "grade_id": "cell-0272d508d2481088",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### 2D: Loop → FoldLeft (10 points)\n",
    "Eliminate the for loop and mutable variables in the code below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ee230ce635395d4d8fd4cee14b3d7eee",
     "grade": false,
     "grade_id": "cell-02bc224733c77bc0",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mimperativeFun\u001b[39m"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def imperativeFun(lst: List[Int]): Int = {\n",
    "    var minSoFar = Int.MaxValue // 2^32-1\n",
    "    var maxDiff = 0\n",
    "    for (x <- lst) {\n",
    "        if (x <= minSoFar){\n",
    "            minSoFar = x\n",
    "        }\n",
    "        if (x - minSoFar > maxDiff){\n",
    "            maxDiff = x - minSoFar\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    return maxDiff\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "833709007dac7119ad8b2e440e11d1de",
     "grade": false,
     "grade_id": "cell-61ba46072b910129",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfunUsingFoldLeft\u001b[39m"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def funUsingFoldLeft(lst: List[Int]): Int = {\n",
    "    if (lst.length<=1) return 0\n",
    "    else\n",
    "        lst.foldLeft((lst.head, 0)) { case ((minSoFar, maxDiff), x) =>\n",
    "            if (x <= minSoFar && x - minSoFar > maxDiff) (x, x-minSoFar) \n",
    "            else if (x <= minSoFar) (x, maxDiff)\n",
    "            else if (x - minSoFar > maxDiff) (minSoFar, x-minSoFar)\n",
    "            else (minSoFar, maxDiff)\n",
    "          }._2\n",
    "        }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "74224c25087fad0f6bf23612f31466dd",
     "grade": true,
     "grade_id": "cell-b766aa2568f6e251",
     "locked": true,
     "points": 10,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tests Passed (10 points)"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36ml1\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[32m-1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m5\u001b[39m, \u001b[32m18\u001b[39m, \u001b[32m19\u001b[39m, \u001b[32m1\u001b[39m, \u001b[32m0\u001b[39m, \u001b[32m-12\u001b[39m, \u001b[32m2\u001b[39m)\n",
       "\u001b[36ml2\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m2\u001b[39m)\n",
       "\u001b[36ml3\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mNothing\u001b[39m] = \u001b[33mList\u001b[39m()\n",
       "\u001b[36ml4\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m3\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m1\u001b[39m, \u001b[32m0\u001b[39m)\n",
       "\u001b[36ml5\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m-1\u001b[39m, \u001b[32m-12\u001b[39m, \u001b[32m-22\u001b[39m, \u001b[32m-54\u001b[39m, \u001b[32m-89\u001b[39m, \u001b[32m90\u001b[39m)"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// BEGIN TESTS\n",
    "val l1 = List(1, 2, 3, -1, 2, 5, 18, 19, 1, 0, -12, 2)\n",
    "assert(imperativeFun(l1) == funUsingFoldLeft(l1), \"Test 1 failed\")\n",
    "\n",
    "val l2 = List(2)\n",
    "assert(imperativeFun(l2) == funUsingFoldLeft(l2), \"Test 2 failed\")\n",
    "\n",
    "val l3 = List()\n",
    "assert(imperativeFun(l3) == funUsingFoldLeft(l3), \"Test 3 failed\")\n",
    "\n",
    "val l4 = List(3, 2, 1, 0)\n",
    "assert(imperativeFun(l4) == funUsingFoldLeft(l4), \"Test 4 failed\")\n",
    "\n",
    "val l5 = List( -1,  -12, -22, -54, -89, 90)\n",
    "assert(imperativeFun(l5) == funUsingFoldLeft(l5), \"Test 5 failed\")\n",
    "\n",
    "passed(10)\n",
    "// END TESTS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala",
   "language": "scala",
   "name": "scala"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".scala",
   "mimetype": "text/x-scala",
   "name": "scala",
   "nbconvert_exporter": "script",
   "version": "2.12.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}