commit - 0c27cc209c4ef08d6bb54cdfd9d6e6ef9cf70012
commit + 5fdda9c8018fb8f56e1d7f51a25130454160d120
blob - /dev/null
blob + e901580527f0c5f89e21b5872970551080a5b0dc (mode 644)
--- /dev/null
+++ Programing/Ejercicios_Programacion.ipynb
+{
+ "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
+}
