{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d3d5587c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# the Python operator \"//\" (remainder after division) \n",
    "# shows the desired behaviour:\n",
    "#\n",
    "print(5.4 - 5.4//1)\n",
    "print(-5.4 - (-5.4//1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "307cd9e5",
   "metadata": {},
   "outputs": [],
   "source": [
    "# function that returns x if it has\n",
    "# a greater fractional part than y,\n",
    "# and otherwise returns y\n",
    "#\n",
    "# x and y are assumed to be floating-point numbers (not strings, etc.)\n",
    "#\n",
    "def grtfrac(x, y):\n",
    "    if (x - x//1) > (y - y//1):\n",
    "        return x\n",
    "    else:\n",
    "        return y\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "20ecc41d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# validation based on the user requirements\n",
    "#\n",
    "print(grtfrac(2.7, 3.6))\n",
    "print(grtfrac(-2.7, -1.8))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c601dd6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# precondition: x is a list of natural numbers, y is a natural number.\n",
    "#\n",
    "# if any a + b = y exist such that a and b are both elements of x, where a != b,\n",
    "# the function returns [a, b]; if none such a and b exist, the empty set is returned.\n",
    "#\n",
    "# the content of the list object from the calling method may not be altered.\n",
    "#\n",
    "# note: this is done with a list only for demonstration purposes;\n",
    "# normally, among the data structures form Python, we would preferably use a set.\n",
    "#\n",
    "def natmatch_iter(x, y):\n",
    "    for i in range(len(x)):\n",
    "        for j in range(i+1, len(x)):\n",
    "            if (x[i]+x[j] == y) and (x[i] != x[j]):\n",
    "                return [x[i], x[j]]\n",
    "    return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e1cbe712",
   "metadata": {},
   "outputs": [],
   "source": [
    "# same as above, one of the two loops is replaced by a recursion\n",
    "#\n",
    "# there is a third argument, l, which the external caller should provide as len(x)\n",
    "# all elements with an index greater or equal to l are ignored\n",
    "#\n",
    "def natmatch_recur_core(x, y, l):\n",
    "    if 1 >= l:\n",
    "        return []\n",
    "    else:\n",
    "        for i in range(l-1):  # run from index 1 to l-2 and match each against index l-1\n",
    "            if (x[i]+x[l-1] == y) and (x[i] != x[l-1]):\n",
    "                return [x[i], x[l-1]]\n",
    "        return natmatch_recur_core(x, y, l-1)\n",
    "\n",
    "# wrapper around the function above, providing the same interface as natmatch_iter\n",
    "def natmatch_recur(x, y):\n",
    "    return natmatch_recur_core(x, y, len(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2bc8a105",
   "metadata": {},
   "outputs": [],
   "source": [
    "testlist = [3*i+2 for i in range(10)]\n",
    "for i in range(10):\n",
    "    testlist.append((i*i)//3 + 2)\n",
    "print(\"List:\", testlist)\n",
    "print(\"Iterative function:\", natmatch_iter(testlist, 21))\n",
    "print(\"Recursive function:\", natmatch_recur(testlist, 21))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "353f2fdf",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import random\n",
    "\n",
    "step = 20\n",
    "kmax = 1500\n",
    "repetitions = 200\n",
    "\n",
    "perf_iter = {}\n",
    "perf_recur = {}\n",
    "random.seed()\n",
    "\n",
    "for k in range(0, kmax+1, step):\n",
    "    start = time.time()\n",
    "    matches_iter = 0\n",
    "    for i in range(repetitions):\n",
    "        k_input = [random.randrange(k*k) for j in range(k)]\n",
    "        if len(natmatch_iter(k_input, k*k)) > 1:\n",
    "            matches_iter += 1\n",
    "    end = time.time()\n",
    "    perf_iter[k] = (end - start)/repetitions\n",
    "\n",
    "    start = time.time()\n",
    "    matches_recur = 0\n",
    "    for i in range(repetitions):\n",
    "        k_input = [random.randrange(k*k) for j in range(k)]\n",
    "        if len(natmatch_recur(k_input, k*k)) > 1:\n",
    "            matches_recur += 1\n",
    "    end = time.time()\n",
    "    perf_recur[k] = (end - start)/repetitions\n",
    "    \n",
    "    print(k, perf_iter[k], perf_recur[k], matches_iter/repetitions, matches_recur/repetitions, sep='\\t')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e477dc28",
   "metadata": {},
   "outputs": [],
   "source": [
    "import seaborn as sbn\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "keylist_iter = list(perf_iter.keys())\n",
    "vallist_iter = list(perf_iter.values())\n",
    "\n",
    "keylist_recur = list(perf_recur.keys())\n",
    "vallist_recur = list(perf_recur.values())\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "fig.set_size_inches(15, 9)\n",
    "plt.xticks(fontsize=18, color=\"#322300\")\n",
    "plt.yticks(fontsize=18, color=\"#322300\")\n",
    "ax.set_xlabel(\"input list size\", fontsize=24, color=\"#322300\")\n",
    "ax.set_ylabel(\"average runtime in seconds\", fontsize=24, color=\"#322300\")\n",
    "\n",
    "sbn.regplot(x=keylist_iter, y=vallist_iter, color='#005528', order=2)\n",
    "sbn.regplot(x=keylist_recur, y=vallist_recur, color='#002855', order=2)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}