D_Yarema_Taras-Laboratori_9-ElementsPic.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "SrFZrrckp0_4"
   },
   "source": [
    "# <span class=\"tema\">(Ordenar i cerca)</span> Elements pic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "gR8Y-Xkqp0_6"
   },
   "source": [
    "Donada una llista d’enters en la que mai trobem dos elements consecutius del mateix valor, trobar **un** dels elements pic. Un enter serà un element pic si els seus veïns immediats són menors que ell. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "zOrn1a7qp0_7"
   },
   "source": [
    "### Conceptualització problema\n",
    "\n",
    "Pensa en les diferents formes (creixent i decreixent) que tindria una funció en la que la llista fos la y, i en cada cas on se situarien els elements pic i com els identificaries. \n",
    "\n",
    "<img src=\"https://github.com/algorismica2019/problemes/blob/master/elementsPic.png?raw=1\" alt=\"quatre patrons que pot tenir la llista, creixent, decreixent, un sol pic i més d'un pic\" />\n",
    "\n",
    "Imagina't que mires l'element central de la llista, on està el pic? com ho saps? quin serà el següent pas?\n",
    "\n",
    "#### Pensa si hi ha algun algorisme vist a teoria aplicable en aquest cas.\n",
    "\n",
    "Si, l'algoritme **binary search**. \n",
    "És aplicable donat que només ens fa falta trobar el primer pic relatiu de la llista.\n",
    "En cas de voler trobar un pic absolut, aquest algoritme no sería viable.\n",
    "\n",
    "#### Explica els passos que fa l'algorisme en el cas `elementsPic([3, 1, 5, 2, 7, 8])`\n",
    "\n",
    "Els passos són els següents:\n",
    "\n",
    "**Iteració 1**\n",
    "1. Es calcula `mid = len([3, 1, 5, 2, 7, 8]) // 2 = 3`\n",
    "1. Donat que `len(llista[:mid]) = len([3, 1, 5]) = 3 > 0`, s'entra en el primer `if`:\n",
    "    1. Es crida `elementsPic(llista[:mid], left, llista[mid]) = elementsPic([3, 1, 5], None, 2)`\n",
    "    1. Es torna al pas 1\n",
    "\n",
    "**Iteració 2**\n",
    "1. Es calcula `mid = len([3, 1, 5]) // 2 = 1`\n",
    "1. Donat que `len(llista[:mid]) = len([3]) = 3 > 0`, s'entra en el primer `if`:\n",
    "    1. Es crida `elementsPic(llista[:mid], left, llista[mid]) = elementsPic([3], None, 1)`\n",
    "    1. Es torna al pas 1\n",
    "\n",
    "**Iteració 3**\n",
    "1. Donat que `len(llista) = len([1]) == 1` s'entra en el condicional dels casos base\n",
    "1. Tenim que `left = None`, per tant, s'entra en el primer `if`\n",
    "    1. Donat que `llista[0] = 3 > right = 1`, hem trobat un pic relatiu de la llista original, per tant retornem\n",
    "    \n",
    "**Iteració 1.2**\n",
    "1. L'algoritme retorna recursivament el *string* fins a la primera iteració a la variable `ret`\n",
    "1. Donat que `ret` no és del tipus `NoneType`, retornem aquest valor i finalitza l'execució\n",
    "\n",
    "El número de recursions ha sigut 3.\n",
    "\n",
    "\n",
    "#### Calcula la complexitat de l'algorisme amb el teorema del màster\n",
    "\n",
    "Donat que l'algoritme emprat és recursiu, podem utilitzar el Master Theorem per trobar-ne la complexitat:\n",
    "\n",
    "$$\n",
    "T(n) = a \\cdot T\\left(\\frac{n}{b}\\right) + O\\left(n^d\\right)\n",
    "$$\n",
    "\n",
    "El nombre d'operacions en cada iteració és un nombre fixat, condicionals ($11$) i una divisió, com a màxim $12$.\n",
    "Per tant, $d=0$.\n",
    "\n",
    "Per altra banda, el número de recursivitats és una, $a=1$. \n",
    "Finalment, dividim $n$ entre $2$ cada cop, ja que és una modificació del algoritme de cerca binària, per tant $b=2$.\n",
    "\n",
    "Juntant-ho tot, tenim que $\\log_b (a) = \\log_2 (1) = 0 = d$ i, per tant, la comlexitat final de l'algoritme és\n",
    "\n",
    "$$\n",
    "T(n) = O(\\log n)\n",
    "$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementació"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "3sQon8CFp0_8"
   },
   "outputs": [],
   "source": [
    "def elementsPic(llista: list, left=None, right=None):\n",
    "    \"\"\"\n",
    "    Funció recursiva que serveix per trobar\n",
    "    el primer pic relatiu d'una llista d'enters\n",
    "    (o qualsevol objecte comparable de Python)\n",
    "    sense repeticions consecutives.\n",
    "    \n",
    "    L'algoritme no funciona si hi han repeticions\n",
    "    d'elements consecutius donat que les desigualtats són estrictes.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "        llista, list\n",
    "            Llista d'objectes.\n",
    "        \n",
    "    Returns\n",
    "    -------\n",
    "        str\n",
    "            Primer pic trobat.\n",
    "        None\n",
    "            Si no s'ha trobat el pic.\n",
    "    \"\"\"\n",
    "    \n",
    "    # Si la llista es buida, retornem error\n",
    "    \n",
    "    if len(llista) == 0:\n",
    "        return None\n",
    "    \n",
    "    # Si la llista actual te un únic element,\n",
    "    # comparem amb els elements left i right\n",
    "    # descendent, en cas de que sigui un màxim\n",
    "    # local, podem asegurar que és un màxim\n",
    "    # relatiu de la llista inicial\n",
    "    \n",
    "    if len(llista) == 1:\n",
    "        \n",
    "        # Cas en que un, o bé els dos,\n",
    "        # dels extrems descendent són nuls,\n",
    "        # es a dir que corresponen a algun extrem\n",
    "        # de la llista inicial\n",
    "        \n",
    "        if left is None or right is None: \n",
    "            if left is None:\n",
    "                if llista[0] > right:\n",
    "                    return f\"Un dels elements pic és el {llista[0]}\"\n",
    "\n",
    "            if right is None:\n",
    "                if llista[0] > left:\n",
    "                    return f\"Un dels elements pic és el {llista[0]}\"\n",
    "            \n",
    "            return None\n",
    "        \n",
    "        # Cas en que ens trobem amb algun element\n",
    "        # estrictament intern de la llista inicial\n",
    "        \n",
    "        if llista[0] > left and llista[0] > right:\n",
    "            return f\"Un dels elements pic és el {llista[0]}\"\n",
    "        \n",
    "        return None\n",
    "        \n",
    "    # Dividim la llista en dues part\n",
    "    # i cridem recursivament aquesta funció\n",
    "    # de manera que la part de l'esquerra\n",
    "    # hereda l'extrem esquerra (left)\n",
    "    # i la part de la dreta hereda l'extrem\n",
    "    # de la dreta (right)\n",
    "    \n",
    "    mid = len(llista) // 2\n",
    "    \n",
    "    if len(llista[:mid]) > 0:\n",
    "        ret = elementsPic(llista[:mid], left, llista[mid])\n",
    "        \n",
    "        if ret is not None:\n",
    "            return ret\n",
    "    \n",
    "    if len(llista[mid:]) > 0:\n",
    "        ret = elementsPic(llista[mid:], llista[mid-1], right)\n",
    "        \n",
    "        if ret is not None:\n",
    "            return ret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La versió *pretty* de la funció és ella mateixa, ja que el format de retorna ja és prou \"*agradable*\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testeig\n",
    "\n",
    "Defineix aquí diversos exemples d'execucions que cobreixin els casos que pot presentar l'algorisme\n",
    "\n",
    "#### Atenció\n",
    "Les següents llistes no serien vàlides ja que tenen un mateix valor repetit de manera consecutiva , i podem suposar que l'usuari ja no les introdueix `[3, 3, 5, 2, 7, 8]`, `[3, 5, 2, 7, 7, 8]`.\n",
    "\n",
    "#### Exemple\n",
    "\n",
    "- `elementsPic([3, 1, 5, 2, 7, 8])`        => Ha de retornar `\"Un dels elements pic és el 3\"`.\n",
    "En aquesta llista en realitat hi ha diversos elements pic: el 3, el 5 i el 8, l'algorisme només n'ha de tornar un\n",
    "\n",
    "- `elementsPic([9, 5, 2])`              => Ha de retornar `\"Un dels elements pic és el 9\"`.\n",
    "En una llista ordenada en ordre descendent, l'element pic sempre serà el primer enter.\n",
    "\n",
    "- `elementsPic([1, 2, 7, 8])`            => Ha de retornar `\"Un dels elements pic és el 8\"`.\n",
    "En una llista ordenada en ordre ascendent, l'element pic sempre serà el darrer enter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Unit tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ran 3 tests ... OK!\n"
     ]
    }
   ],
   "source": [
    "list_a = [3, 1, 5, 2, 7, 8]\n",
    "list_b = [9, 5, 2]\n",
    "list_c = [1, 2, 7, 8]\n",
    "\n",
    "assert elementsPic(list_a) == \"Un dels elements pic és el 3\"\n",
    "assert elementsPic(list_b) == \"Un dels elements pic és el 9\"\n",
    "assert elementsPic(list_c) == \"Un dels elements pic és el 8\"\n",
    "print(\"Ran 3 tests ... OK!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "btl0jscup1AA"
   },
   "source": [
    "### Avaluació (0 a 10 punts)\n",
    "\n",
    "\n",
    "Concepte | Puntuació \n",
    "--- | --- \n",
    "Solució correcta de complexitat O(n) | **7** punts\n",
    "Càlcul de la complexitat correcte | **+2** punts\n",
    "Solució correcta de complexitat >= O(n) | **2** punts \n",
    "Codi comentat i seguint estàndar PEP8 | **+1** punt \n",
    "S'ofereix una funció adicional per mostrar la solució elegantment| **+0.5** punts \n",
    "L'algorisme falla repetidament | **-7** punts \n",
    "L'algorisme falla en algun cas excepcional | **-4** punt\n",
    "No es donen prous exemples d'execució | **-1** punt\n",
    "Codi, noms de variables, solució o comentaris no prou clars | **-1** punt\n",
    "La funció o els paràmetres no s'anomenen com a l'exemple | **-1** punt"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "ElementsPic.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}