Ayudantías/T1b/Ayudantía T1b.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Pauta taller T1b\n",
    "\n",
    "\n",
    "## IIC2115 - Programación Como Herramienta para la Ingeniería\n",
    "\n",
    "## Ayudante: Matías Villafranca - mavillafranca@uc.cl"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Definimos la función verificador lista"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Aca trabajo con la lista arcos sin alterar\n",
    "class Verificador_Lista: \n",
    "    \n",
    "    def __init__(self, arcos):\n",
    "        self.arcos = arcos\n",
    "        self.contador = 0\n",
    "        \n",
    "    def existe_camino(self,camino):\n",
    "        for i in range(1,len(camino)):\n",
    "            #veo los nodos que quiero conectar\n",
    "            Origen=camino[i-1]\n",
    "            Destino=camino[i]\n",
    "            Estan_conectados=False\n",
    "            j=0\n",
    "            while Estan_conectados==False:\n",
    "                #reviso_los_arcos uno por uno (podria ser un for tambien)\n",
    "                Arco=self.arcos[j]\n",
    "                self.contador += 1\n",
    "                #si estan conectados, paso a ver el siguiente par de nodos que deseo conectar cambio la variable\n",
    "                if (Origen,Destino)==Arco:\n",
    "                    Estan_conectados=True\n",
    "                elif (Destino,Origen)==Arco:\n",
    "                    self.contador += 1\n",
    "                    Estan_conectados=True\n",
    "                #sino, veo el siguiente arco de los posibles\n",
    "                else:\n",
    "                    self.contador += 1\n",
    "                    #Si ya revise todos los arcos y ninguno conecta, entrego que no es posible hacer el camino\n",
    "                    if j==len(self.arcos)-1:\n",
    "                        return (False,self.contador)\n",
    "                    j +=1\n",
    "        \n",
    "        return (True,self.contador)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Probamos nuestro verificador de listas con la instancia de ejemplo del taller"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(True, 39)\n"
     ]
    }
   ],
   "source": [
    "#Traten de usar el if __name__=='__main__' al probar sus instancias. Sera necesario en proximos capitulos\n",
    "if __name__=='__main__':\n",
    "    arcos = [(\"A\",\"B\"), (\"A\",\"E\"),(\"A\",\"C\"), (\"B\",\"D\"),(\"B\",\"E\"),\n",
    "    (\"C\",\"F\"),(\"C\",\"G\"), (\"D\",\"E\"), (\"E\",\"F\")]\n",
    "    camino = [\"A\",\"C\",\"F\",\"E\",\"A\",\"B\"]\n",
    "    verificador = Verificador_Lista(arcos)\n",
    "    res = verificador.existe_camino(camino)\n",
    "    print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Aca tengo un diccionario que guarda los arcos\n",
    "class Verificador_Diccionario: \n",
    "    \n",
    "    def __init__(self, arcos):\n",
    "        self.arcos = arcos\n",
    "        self.contador = 0\n",
    "        self.diccionario={}\n",
    "    \n",
    "    def llenado_diccionario(self):\n",
    "        for i in range(len(self.arcos)):\n",
    "            Arco=self.arcos[i]\n",
    "            self.diccionario[Arco]=True  #puede ser cualquier value\n",
    "    \n",
    "    def existe_camino(self,camino):\n",
    "        self.llenado_diccionario()\n",
    "        for i in range(1,len(camino)):\n",
    "            Origen=camino[i-1]\n",
    "            Destino=camino[i]\n",
    "            self.contador +=2\n",
    "            if (Origen,Destino) not in self.diccionario and (Destino,Origen) not in self.diccionario:\n",
    "                return(False, self.contador)\n",
    "            \n",
    "        #Si recorri mi for y siempre estuve conectado\n",
    "        return  (True, self.contador)\n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Probamos el verificador de diccionarion con el ejemplo del enunciado"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(True, 10)\n"
     ]
    }
   ],
   "source": [
    "if __name__=='__main__':\n",
    "    arcos = [(\"A\",\"B\"), (\"A\",\"E\"),(\"A\",\"C\"), (\"B\",\"D\"),(\"B\",\"E\"),\n",
    "    (\"C\",\"F\"),(\"C\",\"G\"), (\"D\",\"E\"), (\"E\",\"F\")]\n",
    "    camino = [\"A\",\"C\",\"F\",\"E\",\"A\",\"B\"]\n",
    "    verificador = Verificador_Diccionario(arcos)\n",
    "    res = verificador.existe_camino(camino)\n",
    "    print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Misma estructura de diccionario que el anterior, salvo que ahora en vez de usar un True entrega cuantas veces use el arco\n",
    "class Verificador_Diccionario_opcional: \n",
    "    \n",
    "    def __init__(self, arcos):\n",
    "        self.arcos = arcos\n",
    "        self.contador = 0\n",
    "        self.diccionario={}\n",
    "    \n",
    "    def llenado_diccionario(self):\n",
    "        for i in range(len(self.arcos)):\n",
    "            Arco=self.arcos[i]\n",
    "            self.diccionario[Arco]=0\n",
    "    \n",
    "    def existe_camino(self,camino):\n",
    "        self.llenado_diccionario()\n",
    "        for i in range(1,len(camino)):\n",
    "            Origen=camino[i-1]\n",
    "            Destino=camino[i]\n",
    "            self.contador +=1\n",
    "            if (Origen, Destino) in self.diccionario:\n",
    "                self.diccionario[(Origen,Destino)]+=1\n",
    "                \n",
    "            elif (Destino,Origen) in self.diccionario:\n",
    "                self.contador +=1\n",
    "                self.diccionario[(Destino,Origen)] +=1\n",
    "            else:\n",
    "                self.contador +=1\n",
    "                return (False,self.contador)\n",
    "        \n",
    "        #el ultimo elemento de la tupla (el max), entrega uno de los arcos mas utilizados\n",
    "        return  (True, self.contador,max(self.diccionario.items(), key=lambda k: k[1])[0])\n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Por último, probamos que este metodo entregue el arco más utilizado"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(True, 7, ('A', 'B'))\n"
     ]
    }
   ],
   "source": [
    "if __name__=='__main__':\n",
    "    arcos = [(\"A\",\"B\"), (\"A\",\"E\"),(\"A\",\"C\"), (\"B\",\"D\"),(\"B\",\"E\"),\n",
    "    (\"C\",\"F\"),(\"C\",\"G\"), (\"D\",\"E\"), (\"E\",\"F\")]\n",
    "    camino = [\"A\",\"C\",\"F\",\"E\",\"A\",\"B\"]\n",
    "    verificador = Verificador_Diccionario_opcional(arcos)\n",
    "    res = verificador.existe_camino(camino)\n",
    "    print(res)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conclusiones\n",
    "\n",
    "Si bien, dependiendo del que se considera una verificación o como se hace el código, el número de verificaciones cambia. Lo que si se mantiene, es lo menor que es el número de verificaciones al utilizar diccionario, lo que evidencia una clara ventaja a la hora de escogerlo por sobre una lista (por lo menos para este tipo de pregunta). Quizas ahora, no se nota mucho la relevancia, pero al momento resolver problemas muchos más grandes y complejos la diferencia es mucho mayor y por lo tanto el tiempo que requiere cada código.\n",
    "\n",
    "### ¿Por qué no usar un in en la lista?\n",
    "\n",
    "Quizas más de alguno, se preguntará eso ahora, pero dado que la lista se compone de una secuencia, cada vez que se aplica un in, en verdad (internamente) se buscará un elemento de manera similar a como lo hicimos en verificaciones lista. Por lo que el número de verificaciones sería el mismo. Por lo que no se permitió el uso del in, para poder apreciar de mejor manera la diferencia que se tiene utilizar un tipo de objeto.\n",
    "\n",
    "Ojo esto no significa que siempre hay que usar diccionario y nunca lista (cada uno tiene sus ventajas y desventajas). Pero si queda más o menos claro la ventaja del diccionario en este problema o similares."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def eliminar_duplicados(n):\n",
    "    codigo=str(n)\n",
    "    numeros_entontrados = {}\n",
    "    numero_final=0\n",
    "    for numero in codigo:\n",
    "        if numero not in numeros_entontrados:\n",
    "            numeros_entontrados[numero]=True\n",
    "            numero_final *=10\n",
    "            numero_final += int(numero)\n",
    "    return numero_final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "124\n"
     ]
    }
   ],
   "source": [
    "if __name__=='__main__':\n",
    "    n = 1242241\n",
    "    n_ = eliminar_duplicados(n)\n",
    "    print(n_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def eliminar_duplicados(n): #version usando str\n",
    "    codigo=str(n)\n",
    "    numeros_entontrados = {}\n",
    "    numero_final=''\n",
    "    for numero in codigo:\n",
    "        if numero not in numeros_entontrados:\n",
    "            numeros_entontrados[numero]=True\n",
    "            numero_final +=numero\n",
    "    return numero_final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "124\n"
     ]
    }
   ],
   "source": [
    "if __name__=='__main__':\n",
    "    n = 1242241\n",
    "    n_ = eliminar_duplicados(n)\n",
    "    print(n_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}