D_Yarema_Taras-Laboratori_8.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ddyYpknBpkOX"
   },
   "source": [
    "# <span class=\"tema\">(Ordenar i cerca)</span> Xifres i lletres"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "U5Koa2eepkOY"
   },
   "source": [
    "Escriu una funció no recursiva anomenada ``xifresLletres`` tal que donada una llista amb cadenes formades per xifres exclusivament o per lletres exclusivament retorni la mateixa llista amb les cadenes de xifres  al capdavant i les cadenes de lletres al darrera.  \n",
    "\n",
    "No importa que les xifres o lletres canviin d'ordre entre elles. Però no podem usar llistes auxiliars\n",
    "\n",
    "**Atenció**: Aquest algorisme no retorna res, simplement modifica la llista d'entrada\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "YvMepk2gpkOY"
   },
   "source": [
    "### Conceptualització problema\n",
    "\n",
    "#### Com es representen les lletres i els números a l'ordinador. Pot ajudar-nos a resoldre el problema?\n",
    "\n",
    "Per a poder diferenciar lletres de números, python ofereix dos mètodes especials per a la classe `str`:\n",
    "- `string.isalpha()` comprova si `string` està format per caràcters alfabétics.\n",
    "- `string.isdigit()` comprova si `string` està format per dígits, i.e. números.\n",
    "\n",
    "\n",
    "#### Quins algorismes  podem aplicar? N'hi ha algun que pugui ser més eficient que l'altre?\n",
    "\n",
    "L'algoritme empleat té complexitat, en el pitjor cas, $O(n^2 m)$, on $n$ denota la llargada de la llista i $m$ la llargada de la cadena més llarga de la llista. La complexitat espaial es $O(1)$, donat que no s'utilitzen variables auxiliars.\n",
    "\n",
    "\n",
    "La idea és dividir la llista en dues particions, les cadenes formades per xifres al començament i les formades per lletres al final. D'aquesta manera, només ens hem de preocupar d'anar enviant cada element a l'inici o al final de la cua.\n",
    "\n",
    "Les complexitats de les operacions emprades són [1] les següents:\n",
    "\n",
    "|        | Complexitat |\n",
    "| ------ | ----------- |\n",
    "| `str.isdigit()` | $O(m)$ |\n",
    "| `str.isalpha()` | $O(m)$ |\n",
    "| `list.insert()` | $O(n)$ |\n",
    "| `list.append()` | $O(1)$ |\n",
    "| `list.pop()` | $O(1)$ |\n",
    "\n",
    "\n",
    "La complexitat temporal es pot optimitzar usant dues llistes auxiliars, de manera que només s'ha de fer un `append()` en cada iteració i, finalment, juntar les dues llistes. La complexitat d'aquest cas seria $O(n m)$. \n",
    "\n",
    "El problema de realitzar la ordenació *in situ* és que les operació `insert()` per a elements intermitgos no és $O(1)$. \n",
    "Es podria utilitzar cues lincades dobles (`collections.deque`) però acabes tenint el mateix problema amb l'operació `remove()` d'aquesta.\n",
    "\n",
    "#### Referències\n",
    "\n",
    "[1] [Python: Time complexity](https://wiki.python.org/moin/TimeComplexity). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementació"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "CdOIQym-pkOZ"
   },
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "def xifresLletres(cadena: list) -> None:\n",
    "    \"\"\"\n",
    "    Sorts a list of strings based on\n",
    "    the alphanumeric parity of the string. \n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "        cadena, list[str]    \n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "        None\n",
    "    \"\"\"\n",
    "    \n",
    "    # We will loop over the array and\n",
    "    # filter it's elements, reodering them\n",
    "    \n",
    "    for i, e in enumerate(cadena):\n",
    "        if e.isdigit():\n",
    "            # If the current element is digit based\n",
    "            # we add it to the beginning\n",
    "            \n",
    "            cadena.insert(0, cadena.pop(i))\n",
    "            \n",
    "        elif e.isalpha():\n",
    "            # If the current element is letter based\n",
    "            # we add it to the end\n",
    "            \n",
    "            cadena.append(cadena.pop(i))\n",
    "            \n",
    "        else:\n",
    "            # Raise an exception if we encounter \n",
    "            # a malformed string \n",
    "            \n",
    "            raise Exception(f\"Malformed string: {e}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def xifresLletresPretty(cadena: list) -> None:\n",
    "    \"\"\"\n",
    "    Prints the pretty version of xifresLletres.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "        cadena, list[str]    \n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "        None\n",
    "    \"\"\"\n",
    "    \n",
    "    print(f\"{cadena} -> \", end=\"\")\n",
    "    xifresLletres(cadena)\n",
    "    print(f\"{cadena}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testeig"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['123', 'abc', '1337', 'def', '0'] -> ['123', '1337', '0', 'def', 'abc']\n"
     ]
    }
   ],
   "source": [
    "test_list = [\n",
    "    \"123\",\n",
    "    \"abc\",\n",
    "    \"1337\",\n",
    "    \"def\",\n",
    "    \"0\"\n",
    "]\n",
    "\n",
    "xifresLletresPretty(test_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "yc7eKBrhpkOc"
   },
   "source": [
    "### Avaluació (0 a 10 punts)\n",
    "\n",
    "\n",
    "Concepte | Puntuació \n",
    "--- | --- \n",
    "Solució correcta i amb el màxim d'eficiència | **9** punts\n",
    "Solució correcta eficient | **5** punts\n",
    "Solució correcta ineficient | **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": "XifresiLletres.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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}