{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "defined-element",
   "metadata": {},
   "source": [
    "# Documentation, Testing, Decorators (24/3 - 2021)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cosmetic-aging",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Create a method ``rank(x, L)`` that returns the number of elements in a sorted list of integers ``L`` \n",
    "that are less than or equal to ``x``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "banner-ceiling",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "def rank(x, L):\n",
    "    pass\n",
    "\n",
    "print(rank(7, [3, 5, 8, 7, 12]))  # test input does not satisfy input condition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "plastic-insight",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "def rank(x, L):\n",
    "#    return sum([1 if y <= x else 0 for y in L])\n",
    "    return sum([y <= x for y in L])  # slow solution, does not exploit L is sorted\n",
    "\n",
    "print(rank(7, [3, 5, 8, 7, 12]))  # test input does not satisfy input condition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "duplicate-bacteria",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum([False, False, True])  # False considered = 0, True = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "italic-guitar",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add doc string\n",
    "# add exception for checking output correct\n",
    "# add exceptions for checking input satisfies input assumptions\n",
    "# one liner\n",
    "# binary search\n",
    "# add post condition after loop\n",
    "# add assertion for loop invariant\n",
    "# add assertion for advancing low and high\n",
    "\n",
    "CHECK_INPUT_CONDITIONS = True\n",
    "\n",
    "def rank(x, L):\n",
    "    '''\n",
    "    Returns number of elements in L that are <= x.\n",
    "    \n",
    "    Assumes L is a sorted list of integers, and x is an integer.\n",
    "    Returns integer i, where 0 <= i <= len(L), such that all elements\n",
    "    in L[:i] are less than or equal to x, and all elements in L[i:]\n",
    "    are larger than x.\n",
    "    '''\n",
    "    \n",
    "    if CHECK_INPUT_CONDITIONS:\n",
    "        # Check if input satisfies input conditions (inefficient)\n",
    "        assert isinstance(x, int)\n",
    "        assert all([isinstance(y, int) for y in L])\n",
    "        # assert all([x <= y for x, y in zip(L, L[1:])])  # apparently faster than for i in range(...)\n",
    "        assert all([L[i] <= L[i + 1] for i in range(len(L) - 1)]), \\\n",
    "               'input L is not sorted'\n",
    "    \n",
    "    #i = sum([y <= x for y in L])  # slow solution, does not exploit L is sorted\n",
    "    \n",
    "    # Binary search solution\n",
    "    \n",
    "    # L = [y, y, y, y, y, y, y, y, y]\n",
    "    #            ^              ^\n",
    "    #           low            high\n",
    "    #      ---| <= x            |----- > x\n",
    "    \n",
    "    low = 0\n",
    "    high  = len(L)\n",
    "    \n",
    "    while low < high:\n",
    "        assert low == 0 or L[low - 1] <= x\n",
    "        assert high == len(L) or L[high] > x\n",
    "        \n",
    "        mid = (low + high) // 2\n",
    "        \n",
    "        if L[mid] <= x:\n",
    "            assert low <= mid  # incorrect put < in first try\n",
    "            low = mid + 1  # omit +1 in first try...\n",
    "        else:\n",
    "            assert mid < high\n",
    "            high = mid      \n",
    "    \n",
    "    assert 0 <= low == high <= len(L)\n",
    "    \n",
    "    i = low    \n",
    "    \n",
    "    # Check if output is correct\n",
    "    #if i < 0 or i > len(L):\n",
    "    #    raise ValueError('i outside range(len(L))')  # could use exception\n",
    "    #if i < 0 or i > len(L):\n",
    "    #    raise AssertionError('i outside range(len(L))')  # AssertionError would be more appropriate\n",
    "    #assert 0 <= i <= len(L), 'i outside range(len(L))'\n",
    "    assert 0 <= i <= len(L)\n",
    "    assert i == 0 or L[i - 1] <= x\n",
    "    assert i == len(L) or x < L[i]\n",
    "    \n",
    "    return i\n",
    "\n",
    "#print(rank(7, [3, 5, 8, 7, 12]))  # test input does not satisfy input condition\n",
    "#print(rank(7, [3, 5, 8, 10, 12]))  # test input does not satisfy input condition\n",
    "\n",
    "# Test on some cases\n",
    "\n",
    "assert rank(7, []) == 0\n",
    "assert rank(500, list(range(1, 1001))) == 500\n",
    "assert rank(500, list(range(1, 1001, 2))) == 250\n",
    "assert rank(5, [1, 2, 3, 6, 8, 10]) == 3\n",
    "\n",
    "assert rank(-10, [1, 2, 3, 6, 8, 10]) == 0\n",
    "assert rank(10, [1, 2, 3, 6, 8, 10]) == 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "married-bulgarian",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.767421099999865\n",
      "1.0792551999998068\n"
     ]
    }
   ],
   "source": [
    "from timeit import timeit\n",
    "\n",
    "print(timeit('all([x <= y for x, y in zip(L,L[1:])])', setup='L = list(range(1_000))', number=10_000))\n",
    "print(timeit('all([L[i] <= L[i + 1] for i in range(len(L) - 1)])', setup='L = list(range(1_000))', number=10_000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "excellent-generation",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on function rank in module __main__:\n",
      "\n",
      "rank(x, L)\n",
      "    Return number of elements in L that are <= x.\n",
      "    \n",
      "    Assumes L is a sorted list of integers, and x is an integer.\n",
      "    Returns integer i, where 0 <= i <= len(L), such that all elements\n",
      "    in L[:i] are less than or equal to x, and all elements in L[i:]\n",
      "    are larger than x.\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(rank)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "id": "color-contact",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Automatic test many random instances\n",
    "\n",
    "from random import randint\n",
    "\n",
    "for _ in range(10000):\n",
    "    L = [randint(1, 100) for _ in range(100)]\n",
    "    L.sort()\n",
    "    x = randint(-10, 110)\n",
    "    \n",
    "    assert rank(x, L) == sum([y <= x for y in L])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "id": "wrapped-october",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Trying:\n",
      "    rank(7, [])\n",
      "Expecting:\n",
      "    0\n",
      "ok\n",
      "Trying:\n",
      "    rank(6, [1, 2, 3, 6, 8, 10])\n",
      "Expecting:\n",
      "    4\n",
      "ok\n",
      "Trying:\n",
      "    rank(5, [1, 2, 3, 6, 8, 10])\n",
      "Expecting:\n",
      "    3\n",
      "ok\n",
      "Trying:\n",
      "    rank(-10, [1, 2, 3, 6, 8, 10])\n",
      "Expecting:\n",
      "    0\n",
      "ok\n",
      "1 items had no tests:\n",
      "    __main__\n",
      "1 items passed all tests:\n",
      "   4 tests in __main__.rank\n",
      "4 tests in 2 items.\n",
      "4 passed and 0 failed.\n",
      "Test passed.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "TestResults(failed=0, attempted=4)"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def rank(x, L):\n",
    "    '''\n",
    "    Returns number of elements in L that are <= x.\n",
    "    \n",
    "    Assumes L is a sorted list of integers, and x is an integer.\n",
    "    Returns integer i, where 0 <= i <= len(L), such that all elements\n",
    "    in L[:i] are less than or equal to x, and all elements in L[i:]\n",
    "    are larger than x.\n",
    "\n",
    "    >>> rank(7, [])\n",
    "    0\n",
    "    >>> rank(6, [1, 2, 3, 6, 8, 10])\n",
    "    4\n",
    "    >>> rank(5, [1, 2, 3, 6, 8, 10])\n",
    "    3\n",
    "    >>> rank(-10, [1, 2, 3, 6, 8, 10])\n",
    "    0\n",
    "    '''\n",
    "    \n",
    "    # Binary search\n",
    "    \n",
    "    # L = [y, y, y, y, y, y, y, y, y]\n",
    "    #            ^              ^\n",
    "    #           low            high\n",
    "    #      ---| <= x            |----- > x\n",
    "    \n",
    "    low = 0\n",
    "    high  = len(L)\n",
    "    while low < high:\n",
    "        mid = (low + high) // 2\n",
    "        if L[mid] <= x:\n",
    "            low = mid + 1\n",
    "        else:\n",
    "            high = mid      \n",
    "        \n",
    "    return low\n",
    "\n",
    "\n",
    "import doctest\n",
    "doctest.testmod(verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "running-april",
   "metadata": {},
   "source": [
    "## Exercise \n",
    "\n",
    "Create a decorator ``add_noise`` to add random noise to the output of a function returning a float."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "id": "nervous-unknown",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n",
      "9\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "def square(x):\n",
    "    return x ** 2\n",
    "\n",
    "print(square(3))\n",
    "print(square(3))\n",
    "print(square(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "blond-haiti",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n",
      "9\n",
      "9\n",
      "9.027782053486606\n",
      "8.978278456944059\n",
      "8.967190900667639\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "def add_noise(v):\n",
    "    return v + 0.1 * (random.random() - 0.5)\n",
    "\n",
    "def square(x):\n",
    "    return x ** 2\n",
    "\n",
    "print(square(3))\n",
    "print(square(3))\n",
    "print(square(3))\n",
    "\n",
    "print(add_noise(square(3)))\n",
    "print(add_noise(square(3)))\n",
    "print(add_noise(square(3)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "id": "single-journalism",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9.007015265195312\n",
      "9.004795504427216\n",
      "8.982547139362651\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "def add_noise(v):\n",
    "    return v + 0.1 * (random.random() - 0.5)\n",
    "\n",
    "def square(x):\n",
    "    return add_noise(x ** 2)\n",
    "\n",
    "print(square(3))\n",
    "print(square(3))\n",
    "print(square(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "id": "military-builder",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9.029778109332343\n",
      "8.991004647840848\n",
      "8.994255803767748\n",
      "8.98037816577688\n",
      "9.018795197594168\n",
      "8.968761150920107\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "def add_noise(f):\n",
    "    def noisy_f(x):\n",
    "        return f(x) + 0.1 * (random.random() - 0.5)\n",
    "\n",
    "    return noisy_f\n",
    "    \n",
    "def square(x):\n",
    "    return x ** 2\n",
    "\n",
    "noisy_square = add_noise(square)\n",
    "\n",
    "print(noisy_square(3))\n",
    "print(noisy_square(3))\n",
    "print(noisy_square(3))\n",
    "\n",
    "print(add_noise(square)(3))\n",
    "print(add_noise(square)(3))\n",
    "print(add_noise(square)(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "southwest-binding",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8.975885452081005\n",
      "9.016593818864244\n",
      "9.040268684649\n",
      "8.981011383988381\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "def add_noise(f):\n",
    "    def noisy_f(x):\n",
    "        return f(x) + 0.1 * (random.random() - 0.5)\n",
    "\n",
    "    return noisy_f\n",
    "    \n",
    "def square(x):\n",
    "    return x ** 2\n",
    "\n",
    "square = add_noise(square)  # could use same name\n",
    "\n",
    "print(square(3))\n",
    "print(square(3))\n",
    "print(square(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "id": "exposed-alert",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9.04281528238194\n",
      "9.040425808628004\n",
      "9.025657247733735\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "# decorator\n",
    "def add_noise(f):\n",
    "    def noisy_f(x):\n",
    "        return f(x) + 0.1 * (random.random() - 0.5)\n",
    "\n",
    "    return noisy_f\n",
    "    \n",
    "@add_noise  # apply a decorator\n",
    "def square(x):\n",
    "    return x ** 2\n",
    "\n",
    "print(square(3))\n",
    "print(square(3))\n",
    "print(square(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "id": "front-merit",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8.999848592220417\n",
      "9.000451061303028\n",
      "8.99953553765607\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "# decorator\n",
    "def add_noise(width):\n",
    "    def noise_decorator(f):\n",
    "        def noisy_f(x):\n",
    "            return f(x) + width * (random.random() - 0.5)\n",
    "\n",
    "        return noisy_f\n",
    "    return noise_decorator\n",
    "    \n",
    "@add_noise(0.001)  # apply a decorator\n",
    "def square(x):\n",
    "    return x ** 2\n",
    "\n",
    "print(square(3))\n",
    "print(square(3))\n",
    "print(square(3))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}