{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [] }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" } }, "cells": [ { "cell_type": "markdown", "source": [ "# CC3001 Algoritmos y Estructuras de Datos\n", "\n", "**Auxiliares: Alonso Almendras, Albani Olivieri, Vicente Olivares, Ricardo Valdivia, Sebastián Acuña, Martín Paredes
\n", "Profesores: Iván Sipirán, Nelson Baloian, Patricio Poblete
**" ], "metadata": { "id": "KK9G0JFuK__O" } }, { "cell_type": "markdown", "source": [ "## Problema 1: Chequeando secuencias de paréntesis" ], "metadata": { "id": "jTy3BzV1LRBN" } }, { "cell_type": "markdown", "source": [ "En primer lugar, creamos la clase Pila con los métodos:\n", "\n", "* *push*: Ingresar un elemento \n", "* *pop*: Sacar último elemento\n", "* *is_empty*: Verificar si la pila está vacía\n", "\n", "\n", "\n" ], "metadata": { "id": "OsKW7uyfuY7_" } }, { "cell_type": "code", "source": [ "class Pila:\n", " def __init__(self):\n", " self.s = []\n", " def push(self, x):\n", " self.s.append(x)\n", " def pop(self):\n", " assert len(self.s) > 0\n", " return self.s.pop()\n", " def is_empty(self):\n", " return len(self.s)==0" ], "metadata": { "id": "ANd5RofMpVMn" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "### Solución\n", "\n", "Ahora programamos la función *chequea_balance*, la cual chequeará si un string tiene los paréntesis balanceados. " ], "metadata": { "id": "25NBPsyju6Iz" } }, { "cell_type": "code", "source": [ "def chequea_balance(s): # paréntesis permitidos = '([{<', ')]}>'\n", " abre = \"([{<\"\n", " cierra = \")]}>\"\n", " stack = Pila()\n", " for simbolo in s:\n", " for i in range(len(abre)):\n", " if simbolo == abre[i]: \n", " stack.push(simbolo)\n", " break\n", " elif simbolo == cierra[i]:\n", " if stack.is_empty():\n", " return False\n", " else: \n", " d = stack.pop()\n", " if d != abre[i]: \n", " return False\n", " if stack.is_empty(): \n", " return True\n", " return False" ], "metadata": { "id": "e5ZoP5sspJmA" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "### Solución alternativa ocupando función `index` de Python" ], "metadata": { "id": "01oZtEmNAVes" } }, { "cell_type": "code", "source": [ "def chequea_balance(s): # paréntesis permitidos = '([{<', ')]}>'\n", " abre = \"([{<\"\n", " cierra = \")]}>\"\n", " stack = Pila()\n", " for simbolo in s:\n", " if simbolo in abre: # Notamos que hay un tipo de parentesis de apertura\n", " stack.push(simbolo) # se guarda en la pila\n", " elif simbolo in cierra: \n", " # Si no se ha abierto ningun parentesis de apertura no puede estar\n", " # balanceado\n", " if stack.is_empty(): \n", " return False\n", " else: \n", " d = stack.pop()\n", " # vemos si el parentesis de cierre coincide con el\n", " # parentesis de apertura\n", " if d != abre[cierra.index(simbolo)]:\n", " return False\n", " # Para que este balanceado el string, la Pila debe terminar vacia\n", " if stack.is_empty(): \n", " return True\n", " return False" ], "metadata": { "id": "W_FoiTyMpSSf" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Probemos ahora la solución:" ], "metadata": { "id": "STugcHJMpp6N" } }, { "cell_type": "code", "source": [ "print(chequea_balance(\"(()())\")) # debe retornar True\n", "print(chequea_balance(\"{([]{()})}\")) # debe retornar True\n", "print(chequea_balance(\"{([]()})}\")) # debe retornar False\n", "print(chequea_balance(\"{<{<>}>}\")) # debe retornar True\n", "print(chequea_balance(\"{<{<>>}>}\")) # debe retornar False" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "XFm6ygVTpxtM", "outputId": "08431668-7018-46be-92a9-c252b1b22750" }, "execution_count": null, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "True\n", "True\n", "False\n", "True\n", "False\n" ] } ] }, { "cell_type": "markdown", "source": [ "## Problema 2: Gatito en el árbol\n", "\n", "Los nodos creados por la clase `NodoG` son iguales a los nodos de árbol común, salvo que tiene el parámetro `gatito` y `data`. Si `gatito=True`, el gatito se encuentra en esa rama. El atributo `data` nos servirá para dibujar un gatito en el nodo en que se encuentra perdido." ], "metadata": { "id": "FMdjtEPMUvE3" } }, { "cell_type": "code", "source": [ "!pip install aed-utilities\n", "import aed_utilities as aed" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "ZgfMGAhxvqsx", "outputId": "18403fd2-92e5-4090-9a72-9850e1da5402" }, "execution_count": null, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n", "Collecting aed-utilities\n", " Downloading aed_utilities-0.5.5.tar.gz (4.3 kB)\n", " Preparing metadata (setup.py) ... \u001b[?25l\u001b[?25hdone\n", "Collecting validators\n", " Downloading validators-0.20.0.tar.gz (30 kB)\n", " Preparing metadata (setup.py) ... \u001b[?25l\u001b[?25hdone\n", "Requirement already satisfied: beautifulsoup4 in /usr/local/lib/python3.10/dist-packages (from aed-utilities) (4.11.2)\n", "Requirement already satisfied: soupsieve>1.2 in /usr/local/lib/python3.10/dist-packages (from beautifulsoup4->aed-utilities) (2.4.1)\n", "Requirement already satisfied: decorator>=3.4.0 in /usr/local/lib/python3.10/dist-packages (from validators->aed-utilities) (4.4.2)\n", "Building wheels for collected packages: aed-utilities, validators\n", " Building wheel for aed-utilities (setup.py) ... \u001b[?25l\u001b[?25hdone\n", " Created wheel for aed-utilities: filename=aed_utilities-0.5.5-py3-none-any.whl size=4564 sha256=bfaeb5ecf7cf8c64efc5cb0c9fe98fd0bdaa345913a6427d0a72afa6b0f530f1\n", " Stored in directory: /root/.cache/pip/wheels/8d/2d/83/17dfcc243b9d622367c0fee80f8c55c5793e9c461630a761b3\n", " Building wheel for validators (setup.py) ... \u001b[?25l\u001b[?25hdone\n", " Created wheel for validators: filename=validators-0.20.0-py3-none-any.whl size=19579 sha256=1d369ee0581c84186172b067adcf4ffcb20a1da849f365de6fcadccd4ad78fb9\n", " Stored in directory: /root/.cache/pip/wheels/f2/ed/dd/d3a556ad245ef9dc570c6bcd2f22886d17b0b408dd3bbb9ac3\n", "Successfully built aed-utilities validators\n", "Installing collected packages: validators, aed-utilities\n", "Successfully installed aed-utilities-0.5.5 validators-0.20.0\n" ] } ] }, { "cell_type": "code", "source": [ "class NodoG:\n", " def __init__(self, ID_nodo, gatito, izq=None, der=None):\n", " self.gatito = gatito # True si está el gatito, False si no\n", " self.id = str(ID_nodo) + ' 😿' if gatito else str(ID_nodo)\n", " self.izq = izq\n", " self.der = der\n", "\n", "class Arbol:\n", " def __init__(self,raiz=None):\n", " self.raiz=raiz\n", " def dibujar(self):\n", " btd = aed.BinaryTreeDrawer(fieldData=\"id\", fieldLeft=\"izq\", fieldRight=\"der\")\n", " btd.draw_tree(self, \"raiz\")\n", "\n", "arbol = Arbol(NodoG(42, False, NodoG(21, False, NodoG(15, False, NodoG(4, True)),\n", " NodoG(27, False)),\n", " NodoG(78, False,\n", " NodoG(49, False, None, NodoG(57, False)), None)))" ], "metadata": { "id": "kd_jCJODUjiv" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "arbol.dibujar()" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 254 }, "id": "szfoZYu2V1Qa", "outputId": "e6f3916d-8fe3-4410-9c07-07b52260b045" }, "execution_count": null, "outputs": [ { "output_type": "display_data", "data": { "text/plain": [ "" ], "image/svg+xml": "\n\nArbol\n\n\n\nnode0\n\n4 😿\n\n\n\nnode1\n\n15\n\n\n\nnode1--node0\n\n\n\n\nnode3\n\n21\n\n\n\nnode3--node1\n\n\n\n\nnode2\n\n27\n\n\n\nnode3--node2\n\n\n\n\nnode7\n\n42\n\n\n\nnode7--node3\n\n\n\n\nnode6\n\n78\n\n\n\nnode7--node6\n\n\n\n\nnode5\n\n49\n\n\n\nnode4\n\n57\n\n\n\nnode5--node4\n\n\n\n\nnode6--node5\n\n\n\n" }, "metadata": {} } ] }, { "cell_type": "markdown", "source": [ "La parte más baja del árbol es el nodo 42 pues estamos viéndolo cabeza abajo. El gatito está en el nodo 4 (como se puede apreciar por el *emoji*, donde el gatito está triste porque no lo han encontrado)." ], "metadata": { "id": "aOitZ5BUV_Nu" } }, { "cell_type": "markdown", "source": [ "Crearemos ahora la clase ````Cola````.\n", "\n", "Nos ha de dar lo mismo la implementación, sólo nos importa que las colas tengan los métodos para:\n", "- ***enqueue***: *encolar*, poner un objeto nuevo en la cola.\n", "- ***dequeue***: *desencolar*, quitar el objeto más viejo de la cola.\n", "- ***isEmpty***: preguntar si la cola está vacía." ], "metadata": { "id": "pNHB61j8Xqoo" } }, { "cell_type": "code", "source": [ "class Cola:\n", " def __init__(self):\n", " self.q=[]\n", " def enqueue(self,x):\n", " self.q.insert(0,x)\n", " def dequeue(self):\n", " assert len(self.q)>0\n", " return self.q.pop()\n", " def is_empty(self):\n", " return len(self.q)==0" ], "metadata": { "id": "ZWK1uDSHV42q" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Para buscar el gatito de forma segura, utilizamos una instancia de la clase `Cola` para recorrerlo nivel por nivel, desde el más bajo al más alto, y nos detenemos en cuanto lo encontremos.\n", "\n", "Partimos metiendo la raíz del árbol a la cola.\n", "Siempre que la cola no esté vacía, vamos a desencolar un nodo, y:\n", "- mostramos su información\n", "- si está el gatito, terminamos de buscar\n", "- si tiene hijos izquierdo y derecho, los encolamos **en ese orden** (estamos recorriendo de izquierda a derecha en cada nivel)" ], "metadata": { "id": "as_XVbIdYXcY" } }, { "cell_type": "code", "source": [ "def buscar_gatito(arbol):\n", " q = Cola()\n", " q.enqueue(arbol.raiz)\n", " while not q.is_empty():\n", " rama = q.dequeue()\n", " print(rama.id, end=' ')\n", " if rama.gatito:\n", " print('-> 😺')\n", " return\n", " if rama.izq != None:\n", " q.enqueue(rama.izq)\n", " if rama.der != None:\n", " q.enqueue(rama.der)" ], "metadata": { "id": "jmOiN6dUYW8D" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "buscar_gatito(arbol)" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "tOHPQ3guYVm9", "outputId": "e34bde4b-9ef4-4a85-e720-8f6eb052051a" }, "execution_count": null, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "42 21 78 15 27 49 4 😿 -> 😺\n" ] } ] }, { "cell_type": "markdown", "source": [ "Ahora el gatito está feliz." ], "metadata": { "id": "13nKC6anrT6a" } }, { "cell_type": "markdown", "source": [ "## Pregunta 3: Máxima área contenida\n", "\n" ], "metadata": { "id": "GKdSJ4db0Kbq" } }, { "cell_type": "markdown", "source": [ "### Parte a)\n", "\n", "Implementando un algoritmo por fuerza bruta, calculamos el área de todos los rectángulos que se pueden generar en el histograma y nos quedamos con el mayor." ], "metadata": { "id": "E7sYkz6b0fXG" } }, { "cell_type": "code", "source": [ "import numpy as np" ], "metadata": { "id": "eG216OmcBTl-" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "def max_area_bruta(arr):\n", " area = 0\n", " izq = der = 0\n", " for i in range(0, len(arr)): #indice izquierdo\n", " for j in range(i+1, len(arr)): #indice derecho \n", " ancho = (j-i+1)\n", " alto = np.amin(arr[i:j+1])\n", " if ancho*alto > area:\n", " area = ancho*alto\n", " izq = i # representa la posición de la barra más a la izquierda\n", " der = j # representa la posición de la barra más a la derecha\n", " return (area,izq,der)" ], "metadata": { "id": "f9Wst5yU0QCI" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "arr = np.array([6, 2, 5, 4, 5, 1, 6])\n", "datos_maxima_area = max_area_bruta(arr)\n", "print(\"Area máxima:\", datos_maxima_area[0])\n", "print(\"Izq:\", datos_maxima_area[1], \" der: \", datos_maxima_area[2]) # por claridad mostramos en qué rango de barras se encuentra el área máxima" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "N6oUjH1MDgV7", "outputId": "5fb0a2cf-878d-4c3b-bef2-b4d17e822db6" }, "execution_count": null, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "Area máxima: 12\n", "Izq: 2 der: 4\n" ] } ] }, { "cell_type": "markdown", "source": [ "La cantidad de iteraciones que aplican los `for` anidados, se puede calcular matemáticamente:\n", "\n", "$$\\sum_{i=0}^{n-1}\\sum_{j=i+1}^{n-1} = \\frac{n^2-n}{2} = \\Theta(n^2)$$\n", "\n", "Como cada iteración realiza operaciones a tiempo constante, tenemos que la complejidad del algoritmo es \n", "\n", "$$O(n^2) \\cdot O(1) = O(n^2)$$" ], "metadata": { "id": "X--CHHwjOb3D" } }, { "cell_type": "markdown", "source": [ "### Parte b)\n", "\n", "Primeramente implementamos la clase Pila que se encuentra en el apunte, pero donde agregaremos una función auxiliar llamada `show_top`, que nos mostrará el primer elemento de la pila pero sin quitarlo." ], "metadata": { "id": "k-gfnEMu0nLx" } }, { "cell_type": "code", "source": [ "class Pila:\n", " def __init__(self):\n", " self.s = []\n", " def push(self, x):\n", " self.s.append(x)\n", " def pop(self):\n", " assert len(self.s) > 0\n", " return self.s.pop()\n", " def is_empty(self):\n", " return len(self.s)==0\n", " def __len__(self):\n", " return len(self.s)\n", " def show_top(self):\n", " return self.s[-1]" ], "metadata": { "id": "CmJINYRt0QDt" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Ahora implementamos el algoritmo que calcula el área del rectángulo mayor contenido en un histograma. Se realizará un recorrido lineal por las barras del histograma y para entender cómo funciona el algoritmo, notemos algunas cosas importantes:\n", "\n", "* Si una barra es más alta que la anterior, necesariamente el rectángulo que está contenido entre esas dos barras es de mayor área que el formado por la barra anterior en solitario.\n", "\n", "* En la pila guardaremos los índices de las barras. Como el recorrido es lineal, iremos poniendo índices en orden ascendente.\n", "\n", "* Sólo pondremos un índice en la pila si el último índice que está en ella representa a una barra de menor altura. De este modo, tenemos como invariante que siempre los índices de la pila representan a barras en orden ascendente por altura, no sólo por el índice mismo. Si por el contrario una barra es de menor tamaño que la representada por el último índice de la pila, entonces quitaremos ese índice de la pila (que llamamos `top`) y calcularemos el área que contemple `altura[top]` como largo y la **distancia en barras entre el índice que estamos revisando y el nuevo índice que está en la parte alta de la pila** como ancho. \n", "\n", "* Para mostrar un ejemplo del invariante, si en la pila está escrito $[1,4,5]$, entonces la barra con índice 1 es más pequeña que la barra con índice 4, y esta a su vez es más pequeña que la barra con índice 5. Por otro lado, esto nos dice que las barras con los índices 2 y 3 son más grandes que la barra con índice 4." ], "metadata": { "id": "EWhKbI5-OKRz" } }, { "cell_type": "code", "source": [ "def max_area_optimizada(alturas):\n", " stack = Pila() \n", " area_maxima = 0 # Correspondiente a un histograma vacío\n", " i = 0 # Este contador recorre el arreglo y también delimitará el extremo derecho del rectángulo\n", " n = len(alturas)\n", " inicio = fin = -1 # Estas variables contabilizan el rango de barras que determinan el ancho del rectángulo\n", " while i < n:\n", " #Si la barra es más alta que la correspondiente al top o si el stack está vacío, la pusheamos pues aumenta el área\n", " if stack.is_empty() or alturas[stack.show_top()] <= alturas[i]:\n", " stack.push(i)\n", " i += 1\n", " # Si esta barra es más pequeña que el top del stack \n", " # calculamos el área del rectángulo usando la altura del top como el largo, \n", " # 'i' como el límite derecho y el anterior al top como índice izquierdo.\n", " # Notar que mientras la pila siga teniendo barras más altas, entonces calculamos áreas con todas ellas como alturas.\n", " else:\n", " top = stack.pop()\n", " largo = alturas[top]\n", " if not stack.is_empty(): # Hay una barra de menor tamaño en el stack\n", " # Esta ecuación es simplificable, pero ilustra mejor el rango de barras que estamos considerando\n", " ancho = (i - 1) - (stack.show_top() + 1) + 1 \n", " else:\n", " ancho = i # No había barras en la pila, lo que se puede interpretar como \"stack.show_top() = -1\"\n", " area_con_top = largo * ancho\n", " if area_maxima < area_con_top:\n", " area_maxima = area_con_top\n", " fin = i - 1\n", " if stack.is_empty(): # Si está vacio el stack no hay nada a la izquierda\n", " inicio = i - 1\n", " else:\n", " inicio = stack.show_top() + 1 \n", " \n", " # Este es el caso en que nos quedaron barras en la pila y por lo tanto, áreas por calcular.\n", " while not stack.is_empty():\n", " top = stack.pop()\n", " largo = alturas[top]\n", " if not stack.is_empty(): \n", " ancho = (i - 1) - (stack.show_top() + 1) + 1\n", " else:\n", " ancho = i\n", " area_con_top = largo * ancho \n", " if area_maxima < area_con_top:\n", " area_maxima = area_con_top\n", " fin = i - 1\n", " if stack.is_empty(): # Si está vacio el stack no hay nada a la izquierda\n", " inicio = i - 1\n", " else:\n", " inicio = stack.show_top() + 1\n", " return area_maxima, inicio, fin" ], "metadata": { "id": "D8mXT9pL0cWJ" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "arr = np.array([6, 2, 5, 4, 5, 1, 6])\n", "print(\"Area max:\", max_area_optimizada(arr)[0], \"Izq:\", max_area_optimizada(arr)[1], \"Der:\",max_area_optimizada(arr)[2])\n", "arr = np.array([6, 2, 5, 4, 5, 1, 6, 6, 7])\n", "print(\"Area max:\", max_area_optimizada(arr)[0], \"Izq:\", max_area_optimizada(arr)[1], \"Der:\",max_area_optimizada(arr)[2])" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "WVDHCIE4rID5", "outputId": "c5892a27-5ead-425a-ea29-8af192a8ab97" }, "execution_count": null, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "Area max: 12 Izq: 2 Der: 4\n", "Area max: 18 Izq: 6 Der: 8\n" ] } ] } ] }