Clases/Clase_14_Caso_de_Estudio_2.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "colab": {
      "name": "Clase_14_Caso_de_Estudio_2.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/bpoblete/CC1002/blob/master/Clases/Clase_14_Caso_de_Estudio_2.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IpyVe9uJQovD"
      },
      "source": [
        "# Caso de Estudio 2: Traductor AI2E (Abreviación de Internet a Español)\n",
        "\n",
        "Con el uso constante de abreviaciones en redes sociales y mensajes de texto, es común (al menos para el profesor Alejandro) tener que averiguar qué significa una abreviación recibida por mensaje de texto.\n",
        "\n",
        "Haremos un programa que nos permita guardar abreviaciones y su significado, y dada una abreviación, buscar su significado.\n",
        "Por ejemplo, si tenemos la abreviación \"`lol`\" nos gustaría poder encontrar \"`riéndome`\".\n",
        "Guardaremos esta información en una agenda.\n",
        "\n",
        "Descomposición funcional:\n",
        "\n",
        "- Buscar abreviación y entregar significado\n",
        "- Agregar abreviación y significado\n",
        "- Borrar un abreviación\n",
        "- Cambiar significado de una abreviación\n",
        "\n",
        "**Nota.** Por simplicidad, no se aceptan abreviaciones repetidas.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hJnEaVHrQovF"
      },
      "source": [
        "\n",
        "## Solución con Listas\n",
        "### Estructura de datos: lista ordenada de registros con abreviaciones y significados"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "uBm3_AjtQovH"
      },
      "source": [
        "#registro: abrev(str) sig(str)\n",
        "import estructura\n",
        "estructura.crear(\"registro\",\"abrev sig\")\n",
        "\n",
        "#agenda: lista(registro)\n",
        "from lista import *\n",
        "#ejemplo\n",
        "agenda= lista(registro(\"afk\",\"lejos del teclado\"),\\\n",
        "         lista(registro(\"omg\",\"sorprendido\"),\\\n",
        "           lista(registro(\"rofl\",\"riendome\"),None)))\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yKivIsIQQovV"
      },
      "source": [
        "### Buscar por abreviacion en una lista ordenada y entregar significado"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RMTn6sSqQovW"
      },
      "source": [
        "#buscar: str lista(registro) -> str\n",
        "#buscar abreviacion en agenda y devolver significado \n",
        "#(None si no está)\n",
        "#ej: buscar(\"rofl\",agenda)->\"riendome\"\n",
        "#ej: buscar(\"vip\",agenda)->None\n",
        "def buscar(abr,agenda):\n",
        "    \n",
        "    assert agenda==None or type(agenda)==lista\n",
        "    \n",
        "    if agenda==None: \n",
        "        return None\n",
        "\n",
        "    reg=cabeza(agenda)\n",
        "    if reg.abrev==abr: \n",
        "        return reg.sig\n",
        "\n",
        "    if reg.abrev > abr:  \n",
        "        return None\n",
        "    \n",
        "    return buscar(abr,cola(agenda))\n",
        "\n",
        "assert buscar(\"rofl\",agenda)==\"riendome\"\n",
        "assert buscar(\"vip\",agenda)==None\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tLsU8Iz2Qovd"
      },
      "source": [
        "### Agregar nueva abreviación y significado\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9fzqHh3UQovf"
      },
      "source": [
        "#agregar: str str lista(registro) -> lista(registro)\n",
        "#devuelve una copia de la agenda donde se ha agregado \n",
        "#la nueva abreviacion y significado \n",
        "#(retorna misma agenda si abreviacion ya existia en la agenda)\n",
        "#ej: agregar(\"wtf\",\"confundido\",agenda)->\n",
        "#    lista(registro(\"afk\",\"lejos del teclado\"), \\ \n",
        "#    lista(registro(\"omg\",\"sorprendido\"), \\ \n",
        "#    lista(registro(\"rofl\",\"riendome\"), \\\n",
        "#    lista(registro(\"wtf\",\"confundido\"),None))))\n",
        "def agregar(abr,sig,agenda):\n",
        "    assert agenda==None or type(agenda)==lista\n",
        "    \n",
        "    if agenda==None: \n",
        "        return lista(registro(abr,sig),None)\n",
        "\n",
        "    #caso no es vacia la lista\n",
        "    reg=cabeza(agenda)\n",
        "    \n",
        "    # 3 casos: 1) ya existe abr, 2)reg.abrev es mayor, y 3)reg.abrev es menor\n",
        "    if reg.abrev==abr: #ya tenemos esta abreviacion\n",
        "        return agenda\n",
        "\n",
        "    if reg.abrev > abr:\n",
        "        return lista(registro(abr,sig),agenda) # lo agrego al ppio de la lista\n",
        "\n",
        "    return lista(reg,agregar(abr,sig,cola(agenda))) # tengo que agregarlo en la cola\n",
        "\n",
        "# Tests\n",
        "nueva_agenda = lista(registro(\"afk\",\"lejos del teclado\"), \\\n",
        "    lista(registro(\"omg\",\"sorprendido\"), \\\n",
        "    lista(registro(\"rofl\",\"riendome\"), \\\n",
        "    lista(registro(\"wtf\",\"confundido\"),None))))\n",
        "assert agregar(\"wtf\",\"confundido\",agenda)== nueva_agenda"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hixzRVc8Qovl"
      },
      "source": [
        "### Borrar un abreviación"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6h7cmeuwQovn"
      },
      "source": [
        "#borrar: str lista(registro)->lista(registro)\n",
        "#devuelve una nueva agenda igual a la dada pero borra el registro con abrev (si existe)\n",
        "#ej: borrar(\"omg\",agenda)-> \n",
        "# lista(registro(\"afk\",\"lejos del teclado\"),lista(registro(\"rofl\",\"riendome\"),None))\n",
        "\n",
        "def borrar(abr,agenda):\n",
        "    assert agenda==None or type(agenda)==lista\n",
        "    \n",
        "    if agenda==None: \n",
        "        return None\n",
        "    reg=cabeza(agenda)\n",
        "    # 3 casos posibles\n",
        "    if reg.abrev==abr: # es la cabeza\n",
        "        return cola(agenda)\n",
        "    \n",
        "    if reg.abrev>abr: #no esta\n",
        "        return agenda\n",
        "    \n",
        "    return lista(reg,borrar(abr,cola(agenda)))#tengo que borrarlo de la cola\n",
        "\n",
        "assert borrar(\"omg\",agenda)== \\\n",
        "  lista(registro(\"afk\",\"lejos del teclado\"), \\\n",
        "    lista(registro(\"rofl\",\"riendome\"),None))\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TBJ7AofnQovs"
      },
      "source": [
        "### Cambiar el significado de una abreviación"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CLsSAB8VQovt"
      },
      "source": [
        "#cambiar: str str lista(registro)->lista(registro)\n",
        "#Retorna una copia de la agenda pero donde se ha cambiado el significado \n",
        "#de la abreviacion (si existia)\n",
        "#ej: cambiar(\"omg\",\"impactado\",agenda)->lista(registro(\"afk\",\"lejos del teclado\"),\n",
        "#  lista(registro(\"omg\",\"impactado\"),lista(registro(\"rofl\",\"riendome\"),None)))\n",
        "\n",
        "def cambiar(abr,sig,agenda):\n",
        "    assert agenda==None or type(agenda)==lista\n",
        "    \n",
        "    if buscar(abr,agenda)==None: \n",
        "        return agenda\n",
        "    \n",
        "    return agregar(abr,sig,borrar(abr,agenda))\n",
        "  \n",
        "assert cambiar(\"omg\",\"impactado\",agenda)==\\\n",
        "  lista(registro(\"afk\",\"lejos del teclado\"), \\\n",
        "    lista(registro(\"omg\",\"impactado\"), \\\n",
        "    lista(registro(\"rofl\",\"riendome\"),None)))\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ryNgxAnMQov1"
      },
      "source": [
        "\n",
        "## Solución con ABB\n",
        "### Estructura de datos: ABB de registros con abreviaciones y significados"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7ogotDfRQov2"
      },
      "source": [
        "#Arbol Binario\n",
        "#AB: valor(any), izq(AB), der(AB)\n",
        "estructura.crear(\"AB\",\"valor izq der\")\n",
        "\n",
        "#esArbol: AB->bool\n",
        "#devuelve True si es AB y False si no\n",
        "#ej...(completar)\n",
        "def esArbol(A):\n",
        "    return A==None or type(A)==AB\n",
        "#test..(completar)\n",
        "\n",
        "\n",
        "#registro: abrev(str) sig(str)\n",
        "import estructura\n",
        "estructura.crear(\"registro\",\"abrev sig\")\n",
        "\n",
        "#agenda: AB(registro)\n",
        "\n",
        "agenda=AB(registro(\"omg\",\"sorprendido\"), \\\n",
        "          AB(registro(\"afk\",\"lejos del teclado\"),None,None), \\\n",
        "          AB(registro(\"rofl\",\"riendome\"),None,None))\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ld3E8YNdQov5"
      },
      "source": [
        "### Buscar por abreviación en ABB y entregar significado"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DaBvL-TcQov6"
      },
      "source": [
        "#buscar: str AB(registro) -> str\n",
        "#buscar abreviacion en agenda y devolver significado\n",
        "#(None si no esta)\n",
        "#ej: buscar(\"rofl\",agenda)->\"riendome\"\n",
        "#ej: buscar(\"vip\",agenda)->None\n",
        "def buscar(abr,agenda):\n",
        "    assert esArbol(agenda)\n",
        "    \n",
        "    if agenda==None: \n",
        "        return None\n",
        "    \n",
        "    reg_actual = agenda.valor\n",
        "    if abr < reg_actual.abrev: \n",
        "        return buscar(abr,agenda.izq)\n",
        "    \n",
        "    if abr > reg_actual.abrev: \n",
        "        return buscar(abr,agenda.der)\n",
        "    \n",
        "    return reg_actual.sig #son iguales\n",
        "\n",
        "assert buscar(\"rofl\",agenda)==\"riendome\"\n",
        "assert buscar(\"vip\",agenda)==None\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "srwckp78Qov_"
      },
      "source": [
        "### Agregar un registro en un ABB"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jU0Lm-lTQov_"
      },
      "source": [
        "#agregar: str str AB(registro) -> AB(registro) \n",
        "#devuelve una copia de la agenda donde se ha agregado \n",
        "#la nueva abreviacion y significado \n",
        "#(retorna misma agenda si abreviacion ya existia en la agenda)\n",
        "#ej: agregar(\"wtf\",\"confundido\",agenda)->\n",
        "#    AB(registro(\"omg\",\"sorpendido\"), \\\n",
        "#    AB(registro(\"afk\",\"lejos del teclado\"), None,None)), \\\n",
        "#    AB(registro(\"rofl\",\"riendome\"),\n",
        "#          None, \\\n",
        "#          AB(registro(\"wtf\",\"confundido\"),None,None))) \\\n",
        "\n",
        "def agregar(abrev,sig,agenda):\n",
        "    assert esArbol(agenda)\n",
        "    if agenda==None: \n",
        "        return AB(registro(abrev,sig),None,None)\n",
        "\n",
        "    reg_actual=agenda.valor\n",
        "    \n",
        "    if abrev < reg_actual.abrev:\n",
        "        return AB(reg_actual,agregar(abrev,sig,agenda.izq),agenda.der)\n",
        "    \n",
        "    if abrev > reg_actual.abrev:\n",
        "        return AB(reg_actual,agenda.izq,agregar(abrev,sig,agenda.der))\n",
        "    \n",
        "    return agenda #si ya existe, dejar igual\n",
        "\n",
        "# Tests\n",
        "nueva_agenda = AB(registro(\"omg\",\"sorprendido\"), \\\n",
        "         AB(registro(\"afk\",\"lejos del teclado\"), None,None), \\\n",
        "         AB(registro(\"rofl\",\"riendome\"),\n",
        "            None, \\\n",
        "            AB(registro(\"wtf\",\"confundido\"),None,None)))\n",
        "assert agregar(\"wtf\",\"confundido\",agenda) == nueva_agenda\n",
        "      \n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QhKu8VH6QowF"
      },
      "source": [
        "### Borrar un registro de un ABB"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7_2To34VQowG"
      },
      "source": [
        "#borrar: str AB(registro) -> AB(registro)\n",
        "#devuelve una nueva agenda igual a la dada pero borra el registro con abrev (si existe)\n",
        "#ej: borrar(\"afk\",agenda)-> \n",
        "#    AB(registro(\"omg\",\"sorprendido\"),\\\n",
        "#       None, \\\n",
        "#       AB(registro(\"rofl\",\"riendome\"),None,None))\n",
        "\n",
        "def borrar(abr,agenda):\n",
        "    assert esArbol(agenda)\n",
        "    if agenda==None: return None\n",
        "\n",
        "    reg_actual=agenda.valor\n",
        "\n",
        "    if abr < reg_actual.abrev:\n",
        "        return AB(reg_actual, borrar(abr,agenda.izq), agenda.der)\n",
        "\n",
        "    if abr > reg_actual.abrev:\n",
        "        return AB(reg_actual, agenda.izq, borrar(abr,agenda.der))\n",
        "    \n",
        "    #Lo encontramos en la raiz, es decir, abr==reg.abrev\n",
        "\n",
        "    #caso 1: si arbol izquierdo vacio, devolver derecho\n",
        "    if agenda.izq==None: return agenda.der\n",
        "\n",
        "    #caso 2: si arbol derecho vacio, devolver izquierdo\n",
        "    if agenda.der==None: return agenda.izq\n",
        "\n",
        "    #caso 3: si arboles izquierdo y derecho no vacios\n",
        "    #reemplazar por mayor del arbol izquierdo\n",
        "    #y borrar mayor del arbol izquierdo\n",
        "    reg_actual=mayorABB(agenda.izq)\n",
        "    return AB(reg_actual,borrar(reg_actual.abrev,agenda.izq),agenda.der)\n",
        "\n",
        "# Tests\n",
        "nueva_agenda = AB(registro(\"omg\",\"sorprendido\"),\\\n",
        "           None, \\\n",
        "           AB(registro(\"rofl\",\"riendome\"),None,None))\n",
        "assert borrar(\"afk\",agenda) == nueva_agenda\n",
        "        "
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "d7o7054FQowK"
      },
      "source": [
        "### Encontrar el mayor elemento en un ABB"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rGGkcU-yQowM"
      },
      "source": [
        "#mayorABB: AB(any) -> any\n",
        "#mayor valor de ABB A\n",
        "#ej: mayorABB(abb)->\"C“\n",
        "\n",
        "def mayorABB(A):\n",
        "    assert type(A)==AB #por lo menos un valor\n",
        "    if A.der==None: return A.valor\n",
        "    return mayorABB(A.der)\n",
        "\n",
        "#Tests\n",
        "abb=AB(\"B\",AB(\"A\",None,None),AB(\"C\",None,None))\n",
        "assert mayorABB(abb)==\"C\"\n"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}