commit - 675eb05ce95d9b4a2e5df7050cb05f48182b26ac
commit + 554726b69f9fd8f76f69f122873f9fc2d472988a
blob - 2e03d47a6b7b7d5b2fdcefe2a6b91db66b0d950e (mode 644)
blob + /dev/null
--- Programing/Ejercicios_Programacion.ipynb
+++ /dev/null
-{
- "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
+# 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 ===")
