commit 554726b69f9fd8f76f69f122873f9fc2d472988a from: ale date: Sat Aug 1 06:46:36 2026 UTC Remove Python exercises notebook and add Julia visualization script - Add `test_visualizaciones.jl` with examples using Plots+GR, UnicodePlots, and CairoMakie - Generate PNG outputs with Gruvbox color palette and transparent backgrounds commit - 675eb05ce95d9b4a2e5df7050cb05f48182b26ac commit + 554726b69f9fd8f76f69f122873f9fc2d472988a blob - 2e03d47a6b7b7d5b2fdcefe2a6b91db66b0d950e (mode 644) blob + /dev/null --- Programing/Ejercicios_Programacion.ipynb +++ /dev/null @@ -1,1165 +0,0 @@ -{ - "cells": [ - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "# Ejercicios de Programación en Python\n", - "\n", - "Este notebook contiene explicaciones detalladas y soluciones paso a paso para tres ejercicios de programación clásicos:\n", - "\n", - "1. **Descompresión de cadenas comprimidas**\n", - "2. **Implementación del juego Buscaminas**\n", - "3. **Encontrar la palabra más larga como subsecuencia**\n", - "\n", - "Cada sección incluye:\n", - "- Explicación del problema\n", - "- Análisis de la solución\n", - "- Código Python comentado\n", - "- Ejemplos de prueba\n", - "- Análisis de complejidad" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "---\n", - "\n", - "## Ejercicio 1: Descompresión de Cadenas Comprimidas\n", - "\n", - "### Descripción del Problema\n", - "\n", - "Dado una cadena comprimida en el formato `número[string]`, debemos descomprimirla expandiendo la cadena el número de veces especificado.\n", - "\n", - "**Ejemplo:**\n", - "- Entrada: `3[abc]4[ab]c`\n", - "- Salida: `abcabcabcababababc`\n", - "\n", - "**Reglas importantes:**\n", - "- Los números pueden tener más de un dígito (ej: `10[a]` = `aaaaaaaaaa`)\n", - "- Las repeticiones pueden estar anidadas (ej: `2[3[a]b]` = `aaabaaab`)\n", - "- Solo contiene dígitos, letras minúsculas y corchetes\n", - "\n", - "### Enfoque de Solución\n", - "\n", - "Usaremos un **enfoque con pila (stack)** que es eficiente en memoria:\n", - "1. Iteramos a través de cada carácter\n", - "2. Cuando encontramos un `[`, guardamos el número y la cadena actual en la pila\n", - "3. Cuando encontramos un `]`, sacamos de la pila y expandimos\n", - "4. Los dígitos se acumulan para formar números de múltiples dígitos" - ] - }, - { - "cell_type": "code", - "metadata": { - "ExecuteTime": { - "end_time": "2026-07-28T05:03:33.793591639Z", - "start_time": "2026-07-28T05:03:33.677498932Z" - } - }, - "source": [ - "def descomprimir_cadena(s):\n", - " \"\"\"\n", - " Descomprime una cadena en formato número[string].\n", - " \n", - " Parámetros:\n", - " s (str): Cadena comprimida\n", - " \n", - " Retorna:\n", - " str: Cadena descomprimida\n", - " \n", - " Complejidad:\n", - " Tiempo: O(n) donde n es la longitud de la cadena descomprimida\n", - " Espacio: O(n) para almacenar la cadena descomprimida\n", - " \"\"\"\n", - " # Pila para almacenar (número, cadena_anterior)\n", - " pila = []\n", - " \n", - " # Cadena actual que estamos construyendo\n", - " cadena_actual = \"\"\n", - " \n", - " # Número actual (puede tener múltiples dígitos)\n", - " numero_actual = 0\n", - " \n", - " # Iteramos a través de cada carácter\n", - " for char in s:\n", - " if char.isdigit():\n", - " # Acumulamos dígitos para formar números de múltiples dígitos\n", - " # Ej: \"10\" se construye como 1 * 10 + 0 = 10\n", - " numero_actual = numero_actual * 10 + int(char)\n", - " \n", - " elif char == '[':\n", - " # Guardamos el estado actual en la pila\n", - " # Guardamos (número, cadena_previa)\n", - " pila.append((numero_actual, cadena_actual))\n", - " \n", - " # Reiniciamos para el siguiente nivel de anidación\n", - " cadena_actual = \"\"\n", - " numero_actual = 0\n", - " \n", - " elif char == ']':\n", - " # Sacamos el estado anterior de la pila\n", - " numero, cadena_previa = pila.pop()\n", - " \n", - " # Expandimos la cadena actual el número de veces\n", - " # y la concatenamos con la cadena previa\n", - " cadena_actual = cadena_previa + numero * cadena_actual\n", - " \n", - " else:\n", - " # Es una letra, simplemente la añadimos\n", - " cadena_actual += char\n", - " \n", - " return cadena_actual\n", - "\n", - "\n", - "# Ejemplos de prueba\n", - "print(\"Ejemplo 1:\")\nprint(f\"Entrada: '3[abc]4[ab]c'\")\nprint(f\"Salida: '{descomprimir_cadena('3[abc]4[ab]c')}'\")\nprint(f\"Esperado: 'abcabcabcababababc'\")\nprint()\n\nprint(\"Ejemplo 2:\")\nprint(f\"Entrada: '2[3[a]b]'\")\nprint(f\"Salida: '{descomprimir_cadena('2[3[a]b]')}'\")\nprint(f\"Esperado: 'aaabaaab'\")\nprint()\n\nprint(\"Ejemplo 3:\")\nprint(f\"Entrada: '10[a]'\")\nprint(f\"Salida: '{descomprimir_cadena('10[a]')}'\")\nprint(f\"Esperado: 'aaaaaaaaaa'\")\nprint()\n\nprint(\"Ejemplo 4:\")\nprint(f\"Entrada: 'a2[b2[c]]d'\")\nprint(f\"Salida: '{descomprimir_cadena('a2[b2[c]]d')}'\")\nprint(f\"Esperado: 'abccbccad'\")" - ], - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "Ejemplo 1:\n", - "Entrada: '3[abc]4[ab]c'\n", - "Salida: 'abcabcabcababababc'\n", - "Esperado: 'abcabcabcababababc'\n", - "\n", - "Ejemplo 2:\n", - "Entrada: '2[3[a]b]'\n", - "Salida: 'aaabaaab'\n", - "Esperado: 'aaabaaab'\n", - "\n", - "Ejemplo 3:\n", - "Entrada: '10[a]'\n", - "Salida: 'aaaaaaaaaa'\n", - "Esperado: 'aaaaaaaaaa'\n", - "\n", - "Ejemplo 4:\n", - "Entrada: 'a2[b2[c]]d'\n", - "Salida: 'abccbccd'\n", - "Esperado: 'abccbccad'\n" - ] - } - ], - "execution_count": 1 - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "### Explicación del Algoritmo Paso a Paso\n", - "\n", - "Veamos cómo funciona con el ejemplo `2[3[a]b]`:\n", - "\n", - "| Paso | Carácter | número_actual | cadena_actual | Pila | Acción |\n", - "|------|----------|---------------|---------------|------|--------|\n", - "| 1 | `2` | 2 | `` | [] | Acumular dígito |\n", - "| 2 | `[` | 0 | `` | [(2, '')] | Guardar estado |\n", - "| 3 | `3` | 3 | `` | [(2, '')] | Acumular dígito |\n", - "| 4 | `[` | 0 | `` | [(2, ''), (3, '')] | Guardar estado |\n", - "| 5 | `a` | 0 | `a` | [(2, ''), (3, '')] | Añadir letra |\n", - "| 6 | `]` | 0 | `aaa` | [(2, '')] | Expandir 3 × 'a' |\n", - "| 7 | `b` | 0 | `aaab` | [(2, '')] | Añadir letra |\n", - "| 8 | `]` | 0 | `aaabaaab` | [] | Expandir 2 × 'aaab' |\n", - "\n", - "**Resultado final:** `aaabaaab` ✓" - ] - }, - { - "cell_type": "code", - "metadata": { - "ExecuteTime": { - "end_time": "2026-02-27T00:24:38.558649160Z", - "start_time": "2026-02-27T00:24:38.494794855Z" - } - }, - "source": [ - "# Pruebas adicionales con casos especiales\n", - "print(\"=\" * 50)\nprint(\"PRUEBAS CON CASOS ESPECIALES\")\nprint(\"=\" * 50)\nprint()\n\n# Caso 1: Sin anidación\nprint(\"Caso 1: Sin anidación\")\nresultado = descomprimir_cadena('3[a]2[b]')\nprint(f\"Entrada: '3[a]2[b]'\")\nprint(f\"Salida: '{resultado}'\")\nprint(f\"Verificación: {resultado == 'aaabb'}\")\nprint()\n\n# Caso 2: Número de múltiples dígitos\nprint(\"Caso 2: Número de múltiples dígitos\")\nresultado = descomprimir_cadena('12[a]')\nprint(f\"Entrada: '12[a]'\")\nprint(f\"Salida: '{resultado}'\")\nprint(f\"Longitud: {len(resultado)} (esperado: 12)\")\nprint()\n\n# Caso 3: Anidación profunda\nprint(\"Caso 3: Anidación profunda\")\nresultado = descomprimir_cadena('2[2[2[a]]]')\nprint(f\"Entrada: '2[2[2[a]]]'\")\nprint(f\"Salida: '{resultado}'\")\nprint(f\"Longitud: {len(resultado)} (esperado: 8)\")\nprint()\n\n# Caso 4: Mezcla de letras y números\nprint(\"Caso 4: Mezcla de letras y números\")\nresultado = descomprimir_cadena('abc3[cd]xyz')\nprint(f\"Entrada: 'abc3[cd]xyz'\")\nprint(f\"Salida: '{resultado}'\")\nprint(f\"Esperado: 'abccdcdcdxyz'\")" - ], - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "==================================================\n", - "PRUEBAS CON CASOS ESPECIALES\n", - "==================================================\n", - "\n", - "Caso 1: Sin anidación\n", - "Entrada: '3[a]2[b]'\n", - "Salida: 'aaabb'\n", - "Verificación: True\n", - "\n", - "Caso 2: Número de múltiples dígitos\n", - "Entrada: '12[a]'\n", - "Salida: 'aaaaaaaaaaaa'\n", - "Longitud: 12 (esperado: 12)\n", - "\n", - "Caso 3: Anidación profunda\n", - "Entrada: '2[2[2[a]]]'\n", - "Salida: 'aaaaaaaa'\n", - "Longitud: 8 (esperado: 8)\n", - "\n", - "Caso 4: Mezcla de letras y números\n", - "Entrada: 'abc3[cd]xyz'\n", - "Salida: 'abccdcdcdxyz'\n", - "Esperado: 'abccdcdcdxyz'\n" - ] - } - ], - "execution_count": 13 - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "---\n", - "\n", - "## Ejercicio 2: Implementar Buscaminas\n", - "\n", - "### Descripción del Problema\n", - "\n", - "Buscaminas es un juego donde:\n", - "- Se tiene una cuadrícula con minas (valor 9) y celdas vacías\n", - "- Cada celda vacía contiene un número que indica cuántas minas hay adyacentes\n", - "- Cuando el jugador hace clic en una celda con 0 minas adyacentes, se revelan automáticamente todas las celdas adyacentes\n", - "- Este proceso continúa recursivamente hasta encontrar celdas con números > 0\n", - "\n", - "### Tareas a Implementar\n", - "\n", - "1. **Generar el tablero**: Colocar minas aleatoriamente\n", - "2. **Calcular números**: Contar minas adyacentes para cada celda\n", - "3. **Revelar celdas**: Implementar el algoritmo de revelación recursiva\n", - "\n", - "### Enfoque de Solución\n", - "\n", - "Usaremos dos matrices:\n", - "- **board**: El tablero real con las minas\n", - "- **display**: Lo que ve el jugador (con celdas ocultas)\n", - "\n", - "Usaremos **BFS (Búsqueda en Amplitud)** para revelar celdas de forma eficiente" - ] - }, - { - "cell_type": "code", - "metadata": { - "ExecuteTime": { - "end_time": "2026-02-27T00:24:38.598602131Z", - "start_time": "2026-02-27T00:24:38.560092792Z" - } - }, - "source": [ - "import random\nfrom collections import deque\n\nclass Buscaminas:\n", - " \"\"\"\n", - " Implementación del juego Buscaminas.\n", - " \n", - " Atributos:\n", - " filas (int): Número de filas del tablero\n", - " columnas (int): Número de columnas del tablero\n", - " minas (int): Número de minas en el tablero\n", - " board (list): Tablero real con las minas (9) y números\n", - " display (list): Tablero mostrado al jugador ('M' = oculto)\n", - " \"\"\"\n", - " \n", - " def __init__(self, filas, columnas, minas):\n", - " \"\"\"\n", - " Inicializa el juego Buscaminas.\n", - " \n", - " Parámetros:\n", - " filas (int): Número de filas\n", - " columnas (int): Número de columnas\n", - " minas (int): Número de minas a colocar\n", - " \"\"\"\n", - " self.filas = filas\n", - " self.columnas = columnas\n", - " self.minas = minas\n", - " \n", - " # Validar que el número de minas sea válido\n", - " total_celdas = filas * columnas\n", - " if minas > total_celdas:\n", - " raise ValueError(f\"No se pueden colocar {minas} minas en {total_celdas} celdas\")\n", - " \n", - " # Inicializar tableros\n", - " self.board = [[0 for _ in range(columnas)] for _ in range(filas)]\n", - " self.display = [['M' for _ in range(columnas)] for _ in range(filas)]\n", - " \n", - " # Generar el tablero\n", - " self._colocar_minas()\n", - " self._calcular_numeros()\n", - " \n", - " def _colocar_minas(self):\n", - " \"\"\"\n", - " Coloca las minas aleatoriamente en el tablero.\n", - " \n", - " Estrategia: Si hay más minas que celdas vacías, es más eficiente\n", - " colocar celdas vacías en lugar de minas.\n", - " \"\"\"\n", - " total_celdas = self.filas * self.columnas\n", - " minas_a_colocar = self.minas\n", - " \n", - " # Si hay más de la mitad de minas, es más eficiente colocar vacías\n", - " if minas_a_colocar > total_celdas // 2:\n", - " # Llenar todo de minas primero\n", - " for i in range(self.filas):\n", - " for j in range(self.columnas):\n", - " self.board[i][j] = 9\n", - " \n", - " # Luego colocar celdas vacías\n", - " vacias_a_colocar = total_celdas - minas_a_colocar\n", - " colocadas = 0\n", - " while colocadas < vacias_a_colocar:\n", - " fila = random.randint(0, self.filas - 1)\n", - " columna = random.randint(0, self.columnas - 1)\n", - " if self.board[fila][columna] == 9:\n", - " self.board[fila][columna] = 0\n", - " colocadas += 1\n", - " else:\n", - " # Colocar minas directamente\n", - " colocadas = 0\n", - " while colocadas < minas_a_colocar:\n", - " fila = random.randint(0, self.filas - 1)\n", - " columna = random.randint(0, self.columnas - 1)\n", - " if self.board[fila][columna] != 9:\n", - " self.board[fila][columna] = 9\n", - " colocadas += 1\n", - " \n", - " def _calcular_numeros(self):\n", - " \"\"\"\n", - " Calcula el número de minas adyacentes para cada celda vacía.\n", - " \n", - " Para cada celda, contamos cuántas minas hay en sus 8 celdas adyacentes.\n", - " \"\"\"\n", - " # Direcciones de las 8 celdas adyacentes (arriba, abajo, izq, der, diagonales)\n", - " direcciones = [\n", - " (-1, -1), (-1, 0), (-1, 1), # Arriba\n", - " (0, -1), (0, 1), # Izquierda y derecha\n", - " (1, -1), (1, 0), (1, 1) # Abajo\n", - " ]\n", - " \n", - " for i in range(self.filas):\n", - " for j in range(self.columnas):\n", - " # Si no es una mina, contar minas adyacentes\n", - " if self.board[i][j] != 9:\n", - " contador_minas = 0\n", - " for di, dj in direcciones:\n", - " ni, nj = i + di, j + dj\n", - " # Verificar que estamos dentro de los límites\n", - " if 0 <= ni < self.filas and 0 <= nj < self.columnas:\n", - " if self.board[ni][nj] == 9:\n", - " contador_minas += 1\n", - " self.board[i][j] = contador_minas\n", - " \n", - " def revelar(self, fila, columna):\n", - " \"\"\"\n", - " Revela una celda y, si es necesario, las adyacentes recursivamente.\n", - " \n", - " Si la celda contiene una mina, el juego termina.\n", - " Si contiene 0, se revelan todas las celdas adyacentes automáticamente.\n", - " \n", - " Parámetros:\n", - " fila (int): Fila de la celda a revelar\n", - " columna (int): Columna de la celda a revelar\n", - " \n", - " Retorna:\n", - " bool: True si el juego continúa, False si se reveló una mina\n", - " \"\"\"\n", - " # Verificar límites\n", - " if not (0 <= fila < self.filas and 0 <= columna < self.columnas):\n", - " return True\n", - " \n", - " # Si ya está revelada, no hacer nada\n", - " if self.display[fila][columna] != 'M':\n", - " return True\n", - " \n", - " # Revelar la celda\n", - " valor = self.board[fila][columna]\n", - " self.display[fila][columna] = str(valor)\n", - " \n", - " # Si es una mina, el juego termina\n", - " if valor == 9:\n", - " return False\n", - " \n", - " # Si es 0, revelar adyacentes usando BFS\n", - " if valor == 0:\n", - " cola = deque([(fila, columna)])\n", - " visitadas = set()\n", - " visitadas.add((fila, columna))\n", - " \n", - " direcciones = [\n", - " (-1, -1), (-1, 0), (-1, 1),\n", - " (0, -1), (0, 1),\n", - " (1, -1), (1, 0), (1, 1)\n", - " ]\n", - " \n", - " while cola:\n", - " f, c = cola.popleft()\n", - " for di, dj in direcciones:\n", - " nf, nc = f + di, c + dj\n", - " if (0 <= nf < self.filas and 0 <= nc < self.columnas and\n", - " (nf, nc) not in visitadas and self.display[nf][nc] == 'M'):\n", - " visitadas.add((nf, nc))\n", - " valor_adyacente = self.board[nf][nc]\n", - " self.display[nf][nc] = str(valor_adyacente)\n", - " # Si es 0, añadir a la cola para procesar sus adyacentes\n", - " if valor_adyacente == 0:\n", - " cola.append((nf, nc))\n", - " \n", - " return True\n", - " \n", - " def mostrar_tablero_real(self):\n", - " \"\"\"Muestra el tablero real (para debugging).\"\"\"\n", - " for fila in self.board:\n", - " print(' '.join(str(x) for x in fila))\n", - " \n", - " def mostrar_tablero_jugador(self):\n", - " \"\"\"Muestra el tablero que ve el jugador.\"\"\"\n", - " for fila in self.display:\n", - " print(' '.join(str(x) for x in fila))\n", - " \n", - " def __str__(self):\n", - " \"\"\"Representación en string del tablero del jugador.\"\"\"\n", - " lineas = []\n", - " for fila in self.display:\n", - " lineas.append(' '.join(str(x) for x in fila))\n", - " return '\\n'.join(lineas)\n\n\n# Ejemplo de uso\nprint(\"=\" * 50)\nprint(\"EJEMPLO DE BUSCAMINAS\")\nprint(\"=\" * 50)\nprint()\n\n# Crear un tablero de 5x5 con 5 minas\njuego = Buscaminas(5, 5, 5)\n\nprint(\"Tablero real (solo para referencia):\")\njuego.mostrar_tablero_real()\nprint()\n\nprint(\"Tablero inicial (lo que ve el jugador):\")\nprint(juego)\nprint()\n\nprint(\"Jugador hace clic en (2, 2)...\")\njuego.revelar(2, 2)\nprint(juego)\nprint()\n\nprint(\"Jugador hace clic en (0, 0)...\")\njuego.revelar(0, 0)\nprint(juego)" - ], - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "==================================================\n", - "EJEMPLO DE BUSCAMINAS\n", - "==================================================\n", - "\n", - "Tablero real (solo para referencia):\n", - "9 3 9 1 0\n", - "2 9 2 1 0\n", - "1 1 1 0 0\n", - "1 2 2 1 0\n", - "1 9 9 1 0\n", - "\n", - "Tablero inicial (lo que ve el jugador):\n", - "M M M M M\n", - "M M M M M\n", - "M M M M M\n", - "M M M M M\n", - "M M M M M\n", - "\n", - "Jugador hace clic en (2, 2)...\n", - "M M M M M\n", - "M M M M M\n", - "M M 1 M M\n", - "M M M M M\n", - "M M M M M\n", - "\n", - "Jugador hace clic en (0, 0)...\n", - "9 M M M M\n", - "M M M M M\n", - "M M 1 M M\n", - "M M M M M\n", - "M M M M M\n" - ] - } - ], - "execution_count": 14 - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "### Análisis del Algoritmo\n", - "\n", - "**Complejidad de colocación de minas:**\n", - "- Si minas < N×M/2: O(2M) en promedio (máximo 2 intentos por mina)\n", - "- Si minas > N×M/2: O(2(N×M - M)) en promedio\n", - "\n", - "**Complejidad de cálculo de números:**\n", - "- O(N×M×8) = O(N×M) - Iteramos cada celda y sus 8 vecinos\n", - "\n", - "**Complejidad de revelación:**\n", - "- O(N×M) - En el peor caso, revelamos todas las celdas\n", - "\n", - "**Ventajas del enfoque BFS:**\n", - "- Más eficiente en memoria que recursión (evita desbordamiento de pila)\n", - "- Fácil de entender y debuggear\n", - "- Garantiza procesar cada celda una sola vez" - ] - }, - { - "cell_type": "code", - "metadata": { - "ExecuteTime": { - "end_time": "2026-02-27T00:24:38.633713742Z", - "start_time": "2026-02-27T00:24:38.603216144Z" - } - }, - "source": [ - "# Prueba adicional: Verificar que el algoritmo revela correctamente\nprint(\"=\" * 50)\nprint(\"PRUEBA: Verificación de revelación correcta\")\nprint(\"=\" * 50)\nprint()\n\njuego2 = Buscaminas(7, 7, 10)\nprint(\"Tablero inicial:\")\nprint(juego2)\nprint()\n\n# Contar celdas ocultas antes\nceldas_ocultas_antes = sum(fila.count('M') for fila in juego2.display)\nprint(f\"Celdas ocultas antes: {celdas_ocultas_antes}\")\n\n# Hacer clic en una esquina\njuego2.revelar(0, 0)\nprint(\"\\nDespués de hacer clic en (0, 0):\")\nprint(juego2)\n\n# Contar celdas ocultas después\nceldas_ocultas_despues = sum(fila.count('M') for fila in juego2.display)\nprint(f\"\\nCeldas ocultas después: {celdas_ocultas_despues}\")\nprint(f\"Celdas reveladas: {celdas_ocultas_antes - celdas_ocultas_despues}\")" - ], - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "==================================================\n", - "PRUEBA: Verificación de revelación correcta\n", - "==================================================\n", - "\n", - "Tablero inicial:\n", - "M M M M M M M\n", - "M M M M M M M\n", - "M M M M M M M\n", - "M M M M M M M\n", - "M M M M M M M\n", - "M M M M M M M\n", - "M M M M M M M\n", - "\n", - "Celdas ocultas antes: 49\n", - "\n", - "Después de hacer clic en (0, 0):\n", - "2 M M M M M M\n", - "M M M M M M M\n", - "M M M M M M M\n", - "M M M M M M M\n", - "M M M M M M M\n", - "M M M M M M M\n", - "M M M M M M M\n", - "\n", - "Celdas ocultas después: 48\n", - "Celdas reveladas: 1\n" - ] - } - ], - "execution_count": 15 - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "---\n", - "\n", - "## Ejercicio 3: Encontrar la Palabra Más Larga como Subsecuencia\n", - "\n", - "### Descripción del Problema\n", - "\n", - "Dado una cadena S y un conjunto de palabras D, encontrar la palabra más larga en D que sea una **subsecuencia** de S.\n", - "\n", - "Una palabra W es subsecuencia de S si podemos obtener W eliminando algunos caracteres de S sin cambiar el orden de los caracteres restantes.\n", - "\n", - "**Ejemplo:**\n", - "- S = \"abppplee\"\n", - "- D = {\"able\", \"ale\", \"apple\", \"bale\", \"kangaroo\"}\n", - "- Resultado: \"apple\"\n", - "\n", - "**Análisis:**\n", - "- \"able\" ✓ es subsecuencia, pero más corta que \"apple\"\n", - "- \"ale\" ✓ es subsecuencia, pero más corta que \"apple\"\n", - "- \"apple\" ✓ es subsecuencia (a-p-p-l-e) - **RESPUESTA**\n", - "- \"bale\" ✗ NO es subsecuencia (b está después de a, pero e está antes de l)\n", - "- \"kangaroo\" ✗ NO es subsecuencia (no contiene k ni n)\n", - "\n", - "### Enfoques de Solución\n", - "\n", - "Mostraremos tres enfoques con complejidades diferentes:" - ] - }, - { - "cell_type": "code", - "metadata": { - "ExecuteTime": { - "end_time": "2026-02-27T00:24:38.664692121Z", - "start_time": "2026-02-27T00:24:38.637733995Z" - } - }, - "source": [ - "# ============================================================================\n", - "# ENFOQUE 1: FUERZA BRUTA CON ALGORITMO GREEDY\n", - "# ============================================================================\n", - "\ndef es_subsecuencia_greedy(s, palabra):\n", - " \"\"\"\n", - " Verifica si 'palabra' es subsecuencia de 's' usando algoritmo greedy.\n", - " \n", - " Algoritmo:\n", - " 1. Escanear S de izquierda a derecha\n", - " 2. Para cada carácter en palabra, buscar su siguiente ocurrencia en S\n", - " 3. Si encontramos todos los caracteres en orden, es subsecuencia\n", - " \n", - " Parámetros:\n", - " s (str): Cadena original\n", - " palabra (str): Palabra a verificar\n", - " \n", - " Retorna:\n", - " bool: True si palabra es subsecuencia de s\n", - " \n", - " Complejidad:\n", - " Tiempo: O(|s| + |palabra|) - Escaneo lineal\n", - " Espacio: O(1) - Sin espacio adicional\n", - " \"\"\"\n", - " indice_s = 0\n", - " \n", - " for char in palabra:\n", - " # Buscar el siguiente carácter en s\n", - " encontrado = False\n", - " while indice_s < len(s):\n", - " if s[indice_s] == char:\n", - " encontrado = True\n", - " indice_s += 1\n", - " break\n", - " indice_s += 1\n", - " \n", - " # Si no encontramos el carácter, no es subsecuencia\n", - " if not encontrado:\n", - " return False\n", - " \n", - " return True\n", - "\n\ndef palabra_mas_larga_enfoque1(s, diccionario):\n", - " \"\"\"\n", - " Encuentra la palabra más larga que es subsecuencia de s.\n", - " Enfoque 1: Fuerza bruta\n", - " \n", - " Complejidad:\n", - " Tiempo: O(N * W) donde N = |s|, W = número de palabras\n", - " Espacio: O(1)\n", - " \"\"\"\n", - " # Ordenar palabras por longitud descendente\n", - " palabras_ordenadas = sorted(diccionario, key=len, reverse=True)\n", - " \n", - " # Verificar cada palabra en orden de longitud\n", - " for palabra in palabras_ordenadas:\n", - " if es_subsecuencia_greedy(s, palabra):\n", - " return palabra\n", - " \n", - " return \"\"\n", - "\n\n# Prueba del Enfoque 1\nprint(\"=\" * 70)\nprint(\"ENFOQUE 1: FUERZA BRUTA CON ALGORITMO GREEDY\")\nprint(\"=\" * 70)\nprint()\n\ns = \"abppplee\"\ndiccionario = {\"able\", \"ale\", \"apple\", \"bale\", \"kangaroo\"}\n\nprint(f\"Cadena S: '{s}'\")\nprint(f\"Diccionario: {diccionario}\")\nprint()\n\n# Verificar cada palabra\nfor palabra in sorted(diccionario, key=len, reverse=True):\n es_subseq = es_subsecuencia_greedy(s, palabra)\n print(f\"¿'{palabra}' es subsecuencia? {es_subseq}\")\n\nprint()\nresultado = palabra_mas_larga_enfoque1(s, diccionario)\nprint(f\"Palabra más larga: '{resultado}'\")\nprint()\n\n# Pruebas adicionales\nprint(\"Pruebas adicionales:\")\nprint()\n\ntest_cases = [\n (\"ace\", {\"a\", \"b\", \"c\"}, \"a\"),\n (\"abpcplea\", {\"ale\", \"apple\", \"monkey\", \"plea\"}, \"apple\"),\n (\"xyz\", {\"abc\", \"def\"}, \"\"),\n]\n\nfor s_test, dict_test, esperado in test_cases:\n resultado = palabra_mas_larga_enfoque1(s_test, dict_test)\n estado = \"✓\" if resultado == esperado else \"✗\"\n print(f\"{estado} S='{s_test}', D={dict_test}\")\n print(f\" Resultado: '{resultado}', Esperado: '{esperado}'\")\n print()" - ], - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "======================================================================\n", - "ENFOQUE 1: FUERZA BRUTA CON ALGORITMO GREEDY\n", - "======================================================================\n", - "\n", - "Cadena S: 'abppplee'\n", - "Diccionario: {'able', 'ale', 'apple', 'kangaroo', 'bale'}\n", - "\n", - "¿'kangaroo' es subsecuencia? False\n", - "¿'apple' es subsecuencia? True\n", - "¿'able' es subsecuencia? True\n", - "¿'bale' es subsecuencia? False\n", - "¿'ale' es subsecuencia? True\n", - "\n", - "Palabra más larga: 'apple'\n", - "\n", - "Pruebas adicionales:\n", - "\n", - "✓ S='ace', D={'a', 'b', 'c'}\n", - " Resultado: 'a', Esperado: 'a'\n", - "\n", - "✓ S='abpcplea', D={'monkey', 'apple', 'plea', 'ale'}\n", - " Resultado: 'apple', Esperado: 'apple'\n", - "\n", - "✓ S='xyz', D={'def', 'abc'}\n", - " Resultado: '', Esperado: ''\n", - "\n" - ] - } - ], - "execution_count": 16 - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "### Análisis del Enfoque 1\n", - "\n", - "**Ventajas:**\n", - "- Muy simple de implementar\n", - "- Espacio O(1) - sin estructuras de datos adicionales\n", - "- Bueno cuando el diccionario es pequeño\n", - "\n", - "**Desventajas:**\n", - "- Complejidad O(N×W) puede ser lenta si W es grande\n", - "- En el peor caso (todas las palabras son subsecuencias), verifica todas\n", - "\n", - "**Cuándo usar:**\n", - "- Diccionario pequeño\n", - "- Cadena S no muy larga" - ] - }, - { - "cell_type": "code", - "metadata": { - "ExecuteTime": { - "end_time": "2026-02-27T00:24:38.698656185Z", - "start_time": "2026-02-27T00:24:38.666329640Z" - } - }, - "source": [ - "# ============================================================================\n", - "# ENFOQUE 2: PREPROCESAMIENTO CON BÚSQUEDA BINARIA\n", - "# ============================================================================\n", - "\ndef palabra_mas_larga_enfoque2(s, diccionario):\n", - " \"\"\"\n", - " Encuentra la palabra más larga que es subsecuencia de s.\n", - " Enfoque 2: Preprocesamiento de S + Búsqueda binaria\n", - " \n", - " Idea: Crear un mapa de cada carácter -> lista de índices donde aparece.\n", - " Luego, para cada palabra, usar búsqueda binaria para encontrar rápidamente\n", - " el siguiente carácter.\n", - " \n", - " Complejidad:\n", - " Tiempo: O(N + L*log(N)) donde N = |s|, L = total caracteres en diccionario\n", - " Espacio: O(N) para el mapa de índices\n", - " \"\"\"\n", - " import bisect\n", - " \n", - " # Preprocesar S: crear mapa de carácter -> lista de índices\n", - " mapa_indices = {}\n", - " for i, char in enumerate(s):\n", - " if char not in mapa_indices:\n", - " mapa_indices[char] = []\n", - " mapa_indices[char].append(i)\n", - " \n", - " def es_subsecuencia_binaria(palabra):\n", - " \"\"\"Verifica si palabra es subsecuencia usando búsqueda binaria.\"\"\"\n", - " indice_actual = -1\n", - " \n", - " for char in palabra:\n", - " # Si el carácter no existe en S, no es subsecuencia\n", - " if char not in mapa_indices:\n", - " return False\n", - " \n", - " # Usar búsqueda binaria para encontrar el siguiente índice\n", - " # que sea mayor que indice_actual\n", - " indices = mapa_indices[char]\n", - " pos = bisect.bisect_right(indices, indice_actual)\n", - " \n", - " # Si no hay un índice válido, no es subsecuencia\n", - " if pos == len(indices):\n", - " return False\n", - " \n", - " # Actualizar el índice actual\n", - " indice_actual = indices[pos]\n", - " \n", - " return True\n", - " \n", - " # Ordenar palabras por longitud descendente\n", - " palabras_ordenadas = sorted(diccionario, key=len, reverse=True)\n", - " \n", - " # Verificar cada palabra\n", - " for palabra in palabras_ordenadas:\n", - " if es_subsecuencia_binaria(palabra):\n", - " return palabra\n", - " \n", - " return \"\"\n", - "\n\n# Prueba del Enfoque 2\nprint(\"=\" * 70)\nprint(\"ENFOQUE 2: PREPROCESAMIENTO CON BÚSQUEDA BINARIA\")\nprint(\"=\" * 70)\nprint()\n\ns = \"abppplee\"\ndiccionario = {\"able\", \"ale\", \"apple\", \"bale\", \"kangaroo\"}\n\nprint(f\"Cadena S: '{s}'\")\nprint(f\"Diccionario: {diccionario}\")\nprint()\n\n# Mostrar el preprocesamiento\nimport bisect\nmapa_indices = {}\nfor i, char in enumerate(s):\n if char not in mapa_indices:\n mapa_indices[char] = []\n mapa_indices[char].append(i)\n\nprint(\"Mapa de índices (preprocesamiento):\")\nfor char in sorted(mapa_indices.keys()):\n print(f\" '{char}' -> {mapa_indices[char]}\")\nprint()\n\nresultado = palabra_mas_larga_enfoque2(s, diccionario)\nprint(f\"Palabra más larga: '{resultado}'\")\nprint()\n\n# Pruebas adicionales\nprint(\"Pruebas adicionales:\")\nprint()\n\nfor s_test, dict_test, esperado in test_cases:\n resultado = palabra_mas_larga_enfoque2(s_test, dict_test)\n estado = \"✓\" if resultado == esperado else \"✗\"\n print(f\"{estado} S='{s_test}', D={dict_test}\")\n print(f\" Resultado: '{resultado}', Esperado: '{esperado}'\")\n print()" - ], - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "======================================================================\n", - "ENFOQUE 2: PREPROCESAMIENTO CON BÚSQUEDA BINARIA\n", - "======================================================================\n", - "\n", - "Cadena S: 'abppplee'\n", - "Diccionario: {'able', 'ale', 'apple', 'kangaroo', 'bale'}\n", - "\n", - "Mapa de índices (preprocesamiento):\n", - " 'a' -> [0]\n", - " 'b' -> [1]\n", - " 'e' -> [6, 7]\n", - " 'l' -> [5]\n", - " 'p' -> [2, 3, 4]\n", - "\n", - "Palabra más larga: 'apple'\n", - "\n", - "Pruebas adicionales:\n", - "\n", - "✓ S='ace', D={'a', 'b', 'c'}\n", - " Resultado: 'a', Esperado: 'a'\n", - "\n", - "✓ S='abpcplea', D={'monkey', 'apple', 'plea', 'ale'}\n", - " Resultado: 'apple', Esperado: 'apple'\n", - "\n", - "✓ S='xyz', D={'def', 'abc'}\n", - " Resultado: '', Esperado: ''\n", - "\n" - ] - } - ], - "execution_count": 17 - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "### Análisis del Enfoque 2\n", - "\n", - "**Ventajas:**\n", - "- Más rápido que Enfoque 1 para diccionarios grandes\n", - "- Complejidad O(N + L*log N) es mucho mejor que O(N*W)\n", - "- Bueno cuando L*log(N) << N*W\n", - "\n", - "**Desventajas:**\n", - "- Requiere espacio O(N) para el mapa de índices\n", - "- Más complejo de implementar\n", - "\n", - "**Cuándo usar:**\n", - "- Diccionario grande\n", - "- Cadena S moderadamente larga\n", - "- Palabras del diccionario relativamente cortas" - ] - }, - { - "cell_type": "code", - "metadata": { - "ExecuteTime": { - "end_time": "2026-02-27T00:24:38.751215110Z", - "start_time": "2026-02-27T00:24:38.702304524Z" - } - }, - "source": [ - "# ============================================================================\n", - "# ENFOQUE 3: PROCESAMIENTO SIMULTÁNEO (ÓPTIMO O(N + L))\n", - "# ============================================================================\n", - "\ndef palabra_mas_larga_enfoque3(s, diccionario):\n", - " \"\"\"\n", - " Encuentra la palabra más larga que es subsecuencia de s.\n", - " Enfoque 3: Procesamiento simultáneo de todas las palabras\n", - " \n", - " Idea: En lugar de verificar cada palabra por separado, procesamos\n", - " S una sola vez y actualizamos el progreso de todas las palabras\n", - " simultáneamente.\n", - " \n", - " Complejidad:\n", - " Tiempo: O(N + L) donde N = |s|, L = total caracteres en diccionario\n", - " Espacio: O(L) para almacenar el estado de cada palabra\n", - " \"\"\"\n", - " # Crear tuplas (palabra, índice_actual) para cada palabra\n", - " # El índice indica cuántos caracteres hemos encontrado\n", - " palabras_estado = [(palabra, 0) for palabra in diccionario]\n", - " \n", - " # Agrupar palabras por el siguiente carácter que necesitan\n", - " grupos = {}\n", - " for palabra, indice in palabras_estado:\n", - " if len(palabra) > 0:\n", - " char_siguiente = palabra[indice]\n", - " if char_siguiente not in grupos:\n", - " grupos[char_siguiente] = []\n", - " grupos[char_siguiente].append((palabra, indice))\n", - " \n", - " # Procesar S carácter por carácter\n", - " for char in s:\n", - " if char not in grupos:\n", - " continue\n", - " \n", - " # Procesar todas las palabras que necesitan este carácter\n", - " palabras_actuales = grupos.pop(char)\n", - " nuevos_grupos = {}\n", - " \n", - " for palabra, indice in palabras_actuales:\n", - " nuevo_indice = indice + 1\n", - " \n", - " # Si completamos la palabra, guardarla en \"encontradas\"\n", - " if nuevo_indice == len(palabra):\n", - " if \"_encontradas\" not in nuevos_grupos:\n", - " nuevos_grupos[\"_encontradas\"] = []\n", - " nuevos_grupos[\"_encontradas\"].append(palabra)\n", - " else:\n", - " # Si no, agrupar por el siguiente carácter\n", - " char_siguiente = palabra[nuevo_indice]\n", - " if char_siguiente not in nuevos_grupos:\n", - " nuevos_grupos[char_siguiente] = []\n", - " nuevos_grupos[char_siguiente].append((palabra, nuevo_indice))\n", - " \n", - " # Actualizar los grupos\n", - " for key, value in nuevos_grupos.items():\n", - " if key != \"_encontradas\":\n", - " if key not in grupos:\n", - " grupos[key] = []\n", - " grupos[key].extend(value)\n", - " else:\n", - " if \"_encontradas\" not in grupos:\n", - " grupos[\"_encontradas\"] = []\n", - " grupos[\"_encontradas\"].extend(value)\n", - " \n", - " # Encontrar la palabra más larga entre las encontradas\n", - " encontradas = grupos.get(\"_encontradas\", [])\n", - " if encontradas:\n", - " return max(encontradas, key=len)\n", - " \n", - " return \"\"\n", - "\n\n# Prueba del Enfoque 3\nprint(\"=\" * 70)\nprint(\"ENFOQUE 3: PROCESAMIENTO SIMULTÁNEO (ÓPTIMO)\")\nprint(\"=\" * 70)\nprint()\n\ns = \"abppplee\"\ndiccionario = {\"able\", \"ale\", \"apple\", \"bale\", \"kangaroo\"}\n\nprint(f\"Cadena S: '{s}'\")\nprint(f\"Diccionario: {diccionario}\")\nprint()\n\nresultado = palabra_mas_larga_enfoque3(s, diccionario)\nprint(f\"Palabra más larga: '{resultado}'\")\nprint()\n\n# Pruebas adicionales\nprint(\"Pruebas adicionales:\")\nprint()\n\nfor s_test, dict_test, esperado in test_cases:\n resultado = palabra_mas_larga_enfoque3(s_test, dict_test)\n estado = \"✓\" if resultado == esperado else \"✗\"\n print(f\"{estado} S='{s_test}', D={dict_test}\")\n print(f\" Resultado: '{resultado}', Esperado: '{esperado}'\")\n print()" - ], - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "======================================================================\n", - "ENFOQUE 3: PROCESAMIENTO SIMULTÁNEO (ÓPTIMO)\n", - "======================================================================\n", - "\n", - "Cadena S: 'abppplee'\n", - "Diccionario: {'able', 'ale', 'apple', 'kangaroo', 'bale'}\n", - "\n", - "Palabra más larga: 'apple'\n", - "\n", - "Pruebas adicionales:\n", - "\n", - "✓ S='ace', D={'a', 'b', 'c'}\n", - " Resultado: 'a', Esperado: 'a'\n", - "\n", - "✓ S='abpcplea', D={'monkey', 'apple', 'plea', 'ale'}\n", - " Resultado: 'apple', Esperado: 'apple'\n", - "\n", - "✓ S='xyz', D={'def', 'abc'}\n", - " Resultado: '', Esperado: ''\n", - "\n" - ] - } - ], - "execution_count": 18 - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "### Análisis del Enfoque 3\n", - "\n", - "**Ventajas:**\n", - "- Complejidad óptima O(N + L)\n", - "- Procesa S solo una vez\n", - "- Muy eficiente para diccionarios muy grandes\n", - "\n", - "**Desventajas:**\n", - "- Más complejo de implementar y entender\n", - "- Requiere espacio O(L) para almacenar estado\n", - "\n", - "**Cuándo usar:**\n", - "- Diccionario muy grande\n", - "- Necesitamos máxima eficiencia\n", - "- Procesamiento en tiempo real" - ] - }, - { - "cell_type": "code", - "metadata": { - "ExecuteTime": { - "end_time": "2026-02-27T00:24:38.777769376Z", - "start_time": "2026-02-27T00:24:38.754023156Z" - } - }, - "source": [ - "# ============================================================================\n", - "# COMPARACIÓN DE ENFOQUES\n", - "# ============================================================================\n", - "\nimport time\nimport random\nimport string\n\nprint(\"=\" * 70)\nprint(\"COMPARACIÓN DE COMPLEJIDAD\")\nprint(\"=\" * 70)\nprint()\n\nprint(\"Tabla de Complejidad:\")\nprint()\nprint(\"┌─────────────────────┬────────────────┬──────────────────┐\")\nprint(\"│ Enfoque │ Tiempo │ Espacio │\")\nprint(\"├─────────────────────┼────────────────┼──────────────────┤\")\nprint(\"│ 1. Fuerza Bruta │ O(N × W) │ O(1) │\")\nprint(\"│ 2. Búsqueda Binaria │ O(N + L×log N) │ O(N) │\")\nprint(\"│ 3. Procesamiento │ O(N + L) │ O(L) │\")\nprint(\"│ Simultáneo │ │ │\")\nprint(\"└─────────────────────┴────────────────┴──────────────────┘\")\nprint()\nprint(\"Donde:\")\nprint(\" N = longitud de la cadena S\")\nprint(\" W = número de palabras en el diccionario\")\nprint(\" L = total de caracteres en todas las palabras del diccionario\")\nprint()\n\nprint(\"Recomendaciones:\")\nprint()\nprint(\"1. Usa Enfoque 1 (Fuerza Bruta) cuando:\")\nprint(\" - Diccionario es pequeño (< 100 palabras)\")\nprint(\" - Cadena S es corta\")\nprint(\" - Simplicidad es más importante que velocidad\")\nprint()\nprint(\"2. Usa Enfoque 2 (Búsqueda Binaria) cuando:\")\nprint(\" - Diccionario es mediano (100-10,000 palabras)\")\nprint(\" - Palabras son relativamente cortas\")\nprint(\" - Necesitas balance entre velocidad y complejidad\")\nprint()\nprint(\"3. Usa Enfoque 3 (Procesamiento Simultáneo) cuando:\")\nprint(\" - Diccionario es muy grande (> 10,000 palabras)\")\nprint(\" - Necesitas máxima eficiencia\")\nprint(\" - Procesamiento en tiempo real\")\nprint()" - ], - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "======================================================================\n", - "COMPARACIÓN DE COMPLEJIDAD\n", - "======================================================================\n", - "\n", - "Tabla de Complejidad:\n", - "\n", - "┌─────────────────────┬────────────────┬──────────────────┐\n", - "│ Enfoque │ Tiempo │ Espacio │\n", - "├─────────────────────┼────────────────┼──────────────────┤\n", - "│ 1. Fuerza Bruta │ O(N × W) │ O(1) │\n", - "│ 2. Búsqueda Binaria │ O(N + L×log N) │ O(N) │\n", - "│ 3. Procesamiento │ O(N + L) │ O(L) │\n", - "│ Simultáneo │ │ │\n", - "└─────────────────────┴────────────────┴──────────────────┘\n", - "\n", - "Donde:\n", - " N = longitud de la cadena S\n", - " W = número de palabras en el diccionario\n", - " L = total de caracteres en todas las palabras del diccionario\n", - "\n", - "Recomendaciones:\n", - "\n", - "1. Usa Enfoque 1 (Fuerza Bruta) cuando:\n", - " - Diccionario es pequeño (< 100 palabras)\n", - " - Cadena S es corta\n", - " - Simplicidad es más importante que velocidad\n", - "\n", - "2. Usa Enfoque 2 (Búsqueda Binaria) cuando:\n", - " - Diccionario es mediano (100-10,000 palabras)\n", - " - Palabras son relativamente cortas\n", - " - Necesitas balance entre velocidad y complejidad\n", - "\n", - "3. Usa Enfoque 3 (Procesamiento Simultáneo) cuando:\n", - " - Diccionario es muy grande (> 10,000 palabras)\n", - " - Necesitas máxima eficiencia\n", - " - Procesamiento en tiempo real\n", - "\n" - ] - } - ], - "execution_count": 19 - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "---\n", - "\n", - "## Resumen y Conclusiones\n", - "\n", - "### Ejercicio 1: Descompresión de Cadenas\n", - "\n", - "**Concepto clave:** Uso de **pila (stack)** para manejar anidación\n", - "\n", - "**Puntos importantes:**\n", - "- Acumular dígitos para números de múltiples dígitos\n", - "- Guardar estado en pila cuando encontramos `[`\n", - "- Restaurar y expandir cuando encontramos `]`\n", - "- Complejidad O(n) donde n es la longitud de salida\n", - "\n", - "### Ejercicio 2: Buscaminas\n", - "\n", - "**Concepto clave:** **BFS (Búsqueda en Amplitud)** para revelación automática\n", - "\n", - "**Puntos importantes:**\n", - "- Colocación eficiente de minas (considerar si > 50%)\n", - "- Cálculo de números adyacentes (8 direcciones)\n", - "- BFS para evitar desbordamiento de pila\n", - "- Complejidad O(N×M) para todas las operaciones\n", - "\n", - "### Ejercicio 3: Palabra Más Larga\n", - "\n", - "**Concepto clave:** **Trade-off entre simplicidad y eficiencia**\n", - "\n", - "**Puntos importantes:**\n", - "- Enfoque 1: Simple pero lento (O(N×W))\n", - "- Enfoque 2: Balance (O(N + L×log N))\n", - "- Enfoque 3: Óptimo pero complejo (O(N + L))\n", - "- Elegir según el tamaño del problema\n", - "\n", - "### Lecciones Generales de Programación\n", - "\n", - "1. **Estructuras de datos:** Elegir la correcta (pila, cola, mapa) es crucial\n", - "2. **Algoritmos:** Entender trade-offs entre tiempo y espacio\n", - "3. **Análisis:** Siempre considerar casos especiales y peor caso\n", - "4. **Optimización:** A menudo requiere preprocesamiento inteligente\n", - "5. **Testing:** Incluir casos especiales, límites y anidaciones" - ] - }, - { - "cell_type": "code", - "metadata": { - "ExecuteTime": { - "end_time": "2026-02-27T00:24:38.829628186Z", - "start_time": "2026-02-27T00:24:38.782483135Z" - } - }, - "source": [ - "# ============================================================================\n", - "# PRUEBAS FINALES INTEGRADAS\n", - "# ============================================================================\n", - "\n", - "print(\"=\" * 70)\n", - "print(\"PRUEBAS FINALES INTEGRADAS\")\n", - "print(\"=\" * 70)\n", - "print()\n", - "\n", - "print(\"✓ EJERCICIO 1: DESCOMPRESIÓN\")\n", - "print(\"-\" * 70)\n", - "pruebas_descompresion = [\n", - " (\"3[a]\", \"aaa\"),\n", - " (\"2[abc]3[cd]ef\", \"abcabccdcdcdef\"),\n", - " (\"100[a]\", \"a\" * 100),\n", - " (\"2[2[y]pq4[2[jk]e1[z]]]\", \"yypqjkejkejkejkzjkejkejkejkzyypqjkejkejkejkzjkejkejkejkz\"),\n", - "]\n", - "\n", - "for entrada, esperado in pruebas_descompresion:\n", - " resultado = descomprimir_cadena(entrada)\n", - " estado = \"✓\" if resultado == esperado else \"✗\"\n", - " print(f\"{estado} Entrada: '{entrada[:30]}...' -> Longitud: {len(resultado)}\")\n", - "\n", - "print()\n", - "print(\"✓ EJERCICIO 2: BUSCAMINAS\")\n", - "print(\"-\" * 70)\n", - "juego_test = Buscaminas(5, 5, 3)\n", - "print(f\"✓ Tablero 5x5 con 3 minas creado\")\n", - "print(f\" - Minas colocadas correctamente\")\n", - "print(f\" - Números calculados\")\n", - "print(f\" - Sistema de revelación funcionando\")\n", - "\n", - "print()\n", - "print(\"✓ EJERCICIO 3: PALABRA MÁS LARGA\")\n", - "print(\"-\" * 70)\n", - "s_final = \"abppplee\"\n", - "dict_final = {\"able\", \"ale\", \"apple\", \"bale\", \"kangaroo\"}\n", - "resultado1 = palabra_mas_larga_enfoque1(s_final, dict_final)\n", - "resultado2 = palabra_mas_larga_enfoque2(s_final, dict_final)\n", - "resultado3 = palabra_mas_larga_enfoque3(s_final, dict_final)\n", - "\n", - "print(f\"Enfoque 1 (Fuerza Bruta): '{resultado1}'\")\n", - "print(f\"Enfoque 2 (Búsqueda Binaria): '{resultado2}'\")\n", - "print(f\"Enfoque 3 (Procesamiento Simultáneo): '{resultado3}'\")\n", - "print(f\"\\n✓ Todos los enfoques dan el mismo resultado: {resultado1 == resultado2 == resultado3}\")" - ], - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "======================================================================\n", - "PRUEBAS FINALES INTEGRADAS\n", - "======================================================================\n", - "\n", - "✓ EJERCICIO 1: DESCOMPRESIÓN\n", - "----------------------------------------------------------------------\n", - "✓ Entrada: '3[a]...' -> Longitud: 3\n", - "✓ Entrada: '2[abc]3[cd]ef...' -> Longitud: 14\n", - "✓ Entrada: '100[a]...' -> Longitud: 100\n", - "✗ Entrada: '2[2[y]pq4[2[jk]e1[z]]]...' -> Longitud: 56\n", - "\n", - "✓ EJERCICIO 2: BUSCAMINAS\n", - "----------------------------------------------------------------------\n", - "✓ Tablero 5x5 con 3 minas creado\n", - " - Minas colocadas correctamente\n", - " - Números calculados\n", - " - Sistema de revelación funcionando\n", - "\n", - "✓ EJERCICIO 3: PALABRA MÁS LARGA\n", - "----------------------------------------------------------------------\n", - "Enfoque 1 (Fuerza Bruta): 'apple'\n", - "Enfoque 2 (Búsqueda Binaria): 'apple'\n", - "Enfoque 3 (Procesamiento Simultáneo): 'apple'\n", - "\n", - "✓ Todos los enfoques dan el mismo resultado: True\n" - ] - } - ], - "execution_count": 20 - } - ], - "metadata": { - "kernelspec": { - "display_name": "Python 3", - "language": "python", - "name": "python3" - }, - "language_info": { - "name": "python", - "version": "3.11.0" - } - }, - "nbformat": 4, - "nbformat_minor": 4 -} blob - /dev/null blob + 343a4ee432c8d0784d1b989e0fae988808c14233 (mode 644) Binary files /dev/null and Programing/images/dispersion_cairomakie.png differ blob - /dev/null blob + c8dc137a0a6304f68ce8de6c66cd02456f8b2ee2 (mode 644) Binary files /dev/null and Programing/images/dispersion_gr.png differ blob - /dev/null blob + 00743814c3eef69ca31f65d87586034dc025f3a4 (mode 644) Binary files /dev/null and Programing/images/heatmap_cairomakie.png differ blob - /dev/null blob + 0e13445d7ebe795be49de69aa4e575c596ad8022 (mode 644) Binary files /dev/null and Programing/images/heatmap_gr.png differ blob - /dev/null blob + a3a54a2168735efa669fa59c800b08d1b59783b1 (mode 644) Binary files /dev/null and Programing/images/sinusoides_cairomakie.png differ blob - /dev/null blob + 293c5bf855385d4ac85fb83daa83a6c444cb1734 (mode 644) Binary files /dev/null and Programing/images/sinusoides_gr.png differ blob - /dev/null blob + 9ff0bd7dee3c1700f16e3d90ad4289a335bdeb02 (mode 644) --- /dev/null +++ Programing/test_visualizaciones.jl @@ -0,0 +1,192 @@ +# Script de prueba para visualización en Julia +# Usa ÚNICAMENTE los paquetes disponibles en el entorno global v1.12: +# CairoMakie v0.15.13, GR v0.73.26, Plots v1.41.6, UnicodePlots v3.8.4 +# +# Características: +# - Fondo transparente en los PNG. +# - Paleta de colores inspirada en Gruvbox (dark). +# +# Ejecuta con: +# julia Programing/test_visualizaciones.jl + +# Carpeta donde se guardarán los PNG (subcarpeta images/ junto al script) +outdir = joinpath(dirname(@__FILE__), "images") +mkpath(outdir) + +# --------------------------------------------------------------------------- +# Paleta Gruvbox (dark) +# https://github.com/morhetz/gruvbox +# --------------------------------------------------------------------------- + +const GRUV_BG = :transparent +const GRUV_FG = "#ebdbb2" # blanco suave +const GRUV_RED = "#cc241d" +const GRUV_GREEN = "#98971a" +const GRUV_YELLOW = "#d79921" +const GRUV_BLUE = "#458588" +const GRUV_PURPLE = "#b16286" +const GRUV_AQUA = "#689d6a" +const GRUV_ORANGE = "#d65d0e" +const GRUV_GRAY = "#928374" + +# --------------------------------------------------------------------------- +# 1. Datos de ejemplo +# --------------------------------------------------------------------------- + +using Random +Random.seed!(1234) + +x = 0:0.05:2π +y_sin = sin.(x) +y_cos = cos.(x) + +n = 100 +xx = randn(n) +yy = 2 .* xx .+ randn(n) +mat = [sin(i * j / 50) for i in 1:20, j in 1:20] + +# --------------------------------------------------------------------------- +# 2. Plots.jl con backend GR + fondo transparente + Gruvbox +# --------------------------------------------------------------------------- + +import Plots + +Plots.gr() + +# Configuración por defecto para toda la sesión de Plots +Plots.default( + bg = :transparent, + background_color = :transparent, + foreground_color = GRUV_FG, + gridcolor = GRUV_GRAY, + legendfontcolor = GRUV_FG, + titlefontcolor = GRUV_FG, + guidefontcolor = GRUV_FG, + tickfontcolor = GRUV_FG, + framestyle = :box, + color_palette = [GRUV_YELLOW, GRUV_AQUA, GRUV_RED, GRUV_BLUE, + GRUV_PURPLE, GRUV_GREEN, GRUV_ORANGE], +) + +p1 = Plots.plot(x, y_sin, + label="sin(x)", + linewidth=2, + color=GRUV_YELLOW, + title="Seno y coseno con Plots + GR", + xlabel="x", + ylabel="y") +Plots.plot!(p1, x, y_cos, label="cos(x)", linewidth=2, color=GRUV_AQUA) + +p2 = Plots.scatter(xx, yy, + label="datos", + alpha=0.6, + color=GRUV_YELLOW, + title="Dispersión con ajuste lineal", + xlabel="x", + ylabel="y") +Plots.plot!(p2, xx, 2 .* xx, label="y = 2x", linewidth=2, color=GRUV_RED) + +p3 = Plots.heatmap(mat, + title="Mapa de calor (sin)", + xlabel="j", + ylabel="i", + color=Plots.cgrad([GRUV_BLUE, GRUV_PURPLE, GRUV_YELLOW, GRUV_RED])) + +Plots.savefig(p1, joinpath(outdir, "sinusoides_gr.png")) +Plots.savefig(p2, joinpath(outdir, "dispersion_gr.png")) +Plots.savefig(p3, joinpath(outdir, "heatmap_gr.png")) + +println("✓ Gráficos de Plots+GR guardados como PNG (transparente + Gruvbox)") + +# --------------------------------------------------------------------------- +# 3. UnicodePlots: gráficos directamente en la terminal +# --------------------------------------------------------------------------- + +import UnicodePlots + +println("\n--- Seno con UnicodePlots ---") +print(UnicodePlots.lineplot(x, y_sin, title="sin(x)", name="sin", xlabel="x", ylabel="y")) + +println("\n--- Coseno con UnicodePlots ---") +print(UnicodePlots.lineplot(x, y_cos, title="cos(x)", name="cos", xlabel="x", ylabel="y", color=:red)) + +println("\n--- Dispersión con UnicodePlots ---") +print(UnicodePlots.scatterplot(xx, yy, title="dispersión", xlabel="x", ylabel="y")) + +println("\n--- Histograma con UnicodePlots ---") +print(UnicodePlots.histogram(randn(1000), title="histograma normal")) + +println("\n--- Heatmap en terminal con UnicodePlots ---") +print(UnicodePlots.heatmap(mat, title="sin(i*j/50)")) + +println("\n✓ Bloque de UnicodePlots completado") + +# --------------------------------------------------------------------------- +# 4. CairoMakie: gráficos estáticos + fondo transparente + Gruvbox +# --------------------------------------------------------------------------- + +import CairoMakie + +fig = CairoMakie.Figure(size=(900, 500), backgroundcolor=GRUV_BG) +ax = CairoMakie.Axis(fig[1, 1], + title="Seno y coseno con CairoMakie", + xlabel="x", ylabel="y", + backgroundcolor=GRUV_BG, + titlecolor=GRUV_FG, + xlabelcolor=GRUV_FG, + ylabelcolor=GRUV_FG, + xticklabelcolor=GRUV_FG, + yticklabelcolor=GRUV_FG, + xgridcolor=GRUV_GRAY, + ygridcolor=GRUV_GRAY, + bottomspinecolor=GRUV_FG, + leftspinecolor=GRUV_FG, + topspinecolor=GRUV_FG, + rightspinecolor=GRUV_FG) +CairoMakie.lines!(ax, x, y_sin, label="sin(x)", linewidth=2, color=GRUV_YELLOW) +CairoMakie.lines!(ax, x, y_cos, label="cos(x)", linewidth=2, color=GRUV_AQUA) +CairoMakie.axislegend(ax, labelcolor=GRUV_FG) + +CairoMakie.save(joinpath(outdir, "sinusoides_cairomakie.png"), fig) + +fig2 = CairoMakie.Figure(size=(600, 500), backgroundcolor=GRUV_BG) +ax2 = CairoMakie.Axis(fig2[1, 1], + title="Dispersión", + xlabel="x", ylabel="y", + backgroundcolor=GRUV_BG, + titlecolor=GRUV_FG, + xlabelcolor=GRUV_FG, + ylabelcolor=GRUV_FG, + xticklabelcolor=GRUV_FG, + yticklabelcolor=GRUV_FG, + xgridcolor=GRUV_GRAY, + ygridcolor=GRUV_GRAY, + bottomspinecolor=GRUV_FG, + leftspinecolor=GRUV_FG, + topspinecolor=GRUV_FG, + rightspinecolor=GRUV_FG) +CairoMakie.scatter!(ax2, xx, yy, color=GRUV_YELLOW, alpha=0.6, label="datos") +CairoMakie.lines!(ax2, xx, 2 .* xx, color=GRUV_RED, linewidth=2, label="y = 2x") +CairoMakie.axislegend(ax2, labelcolor=GRUV_FG) + +CairoMakie.save(joinpath(outdir, "dispersion_cairomakie.png"), fig2) + +fig3 = CairoMakie.Figure(size=(500, 450), backgroundcolor=GRUV_BG) +ax3 = CairoMakie.Axis(fig3[1, 1], + title="Heatmap", + backgroundcolor=GRUV_BG, + titlecolor=GRUV_FG, + xticklabelcolor=GRUV_FG, + yticklabelcolor=GRUV_FG, + bottomspinecolor=GRUV_FG, + leftspinecolor=GRUV_FG, + topspinecolor=GRUV_FG, + rightspinecolor=GRUV_FG) +CairoMakie.heatmap!(ax3, mat, + colormap=CairoMakie.cgrad([GRUV_BLUE, GRUV_PURPLE, GRUV_YELLOW, GRUV_RED])) + +CairoMakie.save(joinpath(outdir, "heatmap_cairomakie.png"), fig3) + +println("✓ Gráficos de CairoMakie guardados como PNG (transparente + Gruvbox)") + +println("\n=== Todos los bloques de prueba terminaron ===")