commit 5fdda9c8018fb8f56e1d7f51a25130454160d120 from: Ale date: Fri Feb 27 00:27:49 2026 UTC Estos son algunos ejersicios para mi entrevista en google commit - 0c27cc209c4ef08d6bb54cdfd9d6e6ef9cf70012 commit + 5fdda9c8018fb8f56e1d7f51a25130454160d120 blob - /dev/null blob + e901580527f0c5f89e21b5872970551080a5b0dc (mode 644) --- /dev/null +++ Programing/Ejercicios_Programacion.ipynb @@ -0,0 +1,1165 @@ +{ + "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-02-27T00:24:38.479707794Z", + "start_time": "2026-02-27T00:24:38.408905309Z" + } + }, + "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": 12 + }, + { + "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 +}