Pontificia Universidad Católica de Chile

IIC2133-1 - Estructura de Datos y Algoritmos

Parte 1
Estructuras de Datos Utilizadas
1. TrieNodo (Árbol de Prefijos)
Esta estructura permite almacenar palabras de manera que compartan prefijos comunes,
optimizando tanto el espacio como el tiempo de búsqueda.
Justificación de complejidad espacial: Aunque cada nodo tiene 26 punteros (consumiendo
más memoria por nodo), esto nos garantiza acceso O(1) a cada hijo. La alternativa de usar
una lista enlazada o hash table por nodo tendrı́a mejor uso de memoria pero peor tiempo de
acceso. En este problema, priorizamos velocidad sobre espacio.

2. Trie Invertido (para Sufijos)

Funcionamiento: Si queremos buscar palabras que terminan en ’os’, insertamos cada
palabra al revés en el Trie. Por ejemplo, ’minutos’ se inserta como ’sotunim’. Ası́, buscar
sufijos se convierte en buscar prefijos en el Trie invertido.
Justificación: Alternativamente, podrı́amos usar una lista simple y verificar cada palabra
O(N × L), pero esto vioları́a la restricción de complejidad O(k × L). El Trie invertido nos
permite aprovechar la misma estructura eficiente del Trie normal, transformando el problema
de sufijos en uno de prefijos.

3. Hash Table (Tabla de Hash)

Para búsquedas exactas en O(1) promedio, implementamos una Hash Table con encadenamiento.
Función hash utilizada: djb2, desarrollada por Daniel J. Bernstein.
¿Por qué djb2? Solo usa operaciones bit-shift y sumas, evitando divisiones costosas. El
uso del número primo 33 (como multiplicador) minimiza colisiones. Pequeños cambios en la
entrada producen grandes cambios en el hash
Tamaño de la tabla: 100003 (número primo grande)
1. Minimización de colisiones: Cuando usamos hash % tabla size, un tamaño primo
asegura que los valores hash se distribuyan uniformemente. Si el tamaño fuera una
 T2 - Agustı́n Alonso De Juan Córdova - 24662100
potencia de 2 (ej: 65536), solo los bits menos significativos del hash importarı́an,
perdiendo información.
2. Máximo Común Divisor (MCD): Para cualquier hash h, si M CD(h, tabla size) >
1, entonces h solo puede mapear a tabla size/M CD posiciones, aumentando colisiones.
Con un número primo, M CD(h, primo) = 1 para casi todos los h, maximizando la
distribución.
3. 100003 especı́ficamente: Es suficientemente grande para minimizar colisiones en
diccionarios tı́picos (factor de carga λ = N/100003 permanece bajo), pero no tan
grande como para desperdiciar memoria excesiva.
Manejo de colisiones: Utilizamos encadenamiento mediante listas enlazadas. Cada posición
de la tabla apunta a una lista de palabras con el mismo valor hash
Factor de carga: Para N palabras insertadas, el factor de carga es λ = N/100003. Con
djb2 y un primo grande, esperamos que cada lista tenga longitud O(λ). Para búsquedas, esto
significa O(1 + λ) = O(1) cuando λ es constante.

Algoritmos y Complejidades
Evento WRITE
Implementación: write words().
Inserción en Trie de prefijos; Inserción en Trie invertido; Inserción en Hash Table: O(L)
Complejidad total para W palabras: O(W × L).

Evento FIND-WORD
Implementación: find word().
Caso promedio: O(L).
Caso peor: O(N × L), aunque improbable debido a la buena distribución de djb2 y el
tamaño primo.

Evento FIND-PREFIX
Implementación: find prefix().
Complejidad total: O(P ) + O(k × L) = O(k × L).

Evento FIND-SUFFIX
Implementación: find suffix().
Complejidad: búsqueda O(k × L) + ordenamiento O(k log(k) × L).

2
 T2 - Agustı́n Alonso De Juan Córdova - 24662100
Análisis de Espacio
Memoria utilizada:
Trie de prefijos: O(N × L)
• Peor caso: todas las palabras son completamente distintas = O(N × L × 26)
• Mejor caso: muchos prefijos compartidos = O(Σ(caracteres únicos))
• Caso promedio en lenguaje natural: O(N × L) efectivo debido a prefijos comunes
Trie invertido: Analogo a Trie de prefijos O(N × L)
Hash Table: O(N × L)
• Tabla: O(100003) = O(1) constante
• Nodos: cada palabra se almacena una vez = O(N × L)
• Total: O(N × L)
Espacio total: 2 × O(N × L) + O(N × L) = O(N × L) dominante
Espacio total: O(N × L).

Optimizaciones Implementadas
1. Arrays fijos de 26 posiciones por nodo (O(1) acceso).
2. Capacidad dinámica duplicada para resultados (O(1) amortizado).
3. Tabla hash de tamaño primo (100003) para minimizar colisiones.
4. Construcción in-place de strings en DFS.
5. strdup() solo al final para ahorrar memoria.

3
 T2 - Agustı́n Alonso De Juan Córdova - 24662100
Parte 2
1. Estrategia Utilizada y Justificación Implementó el algoritmo de Rabin-Karp1 con rolling
hash (hash rodante).
Justificación: Esta estrategia es excepcionalmente adecuada para el problema porque su
complejidad temporal es O(N + Q × M ). El pre-cálculo de los hashes de los patrones toma
O(Q × M ), y el recorrido único a través del mensaje de longitud N para comparar los hashes
toma O(N ). Esta eficiencia se logra al evitar la comparación directa de cadenas, que serı́a
mucho más lenta (O(N × M )).
2. Manejo de Colisiones Una colisión de hash ocurre cuando dos cadenas diferentes producen
el mismo valor de hash. El algoritmo de Rabin-Karp es susceptible a esto.
Para manejar las colisiones, implementó un paso de verificación:
Cuando el hash de la ’ventana’ actual en el mensaje coincide con el hash de una de las
palabras buscadas, no se asume una coincidencia inmediata.
En su lugar, se realiza una comparación carácter por carácter entre la subcadena del
mensaje y la palabra correspondiente para confirmar que son idénticas.
Este paso de verificación garantiza que solo se reporten las coincidencias verdaderas, eliminando
los falsos positivos causados por las colisiones de hash.
3. Costo en Memoria El costo de memoria asociado a esta estrategia es principalmente para
almacenar la información necesaria para la búsqueda:
El mensaje de Gru, que requiere O(N ) de memoria.
Las Q palabras a buscar, cada una de longitud M, lo que resulta en un costo de
O(Q × M ).
Un arreglo para almacenar los hashes calculados de las Q palabras, que ocupa O(Q)
de memoria.
Estructuras para almacenar los ı́ndices de resultados para cada consulta.
Por lo tanto, el costo de memoria dominante de la estrategia es O(N + Q × M )

4
 T2 - Agustı́n Alonso De Juan Córdova - 24662100
Parte 3
Técnica de programación
Para resolver utilizo backtracking
a) Modelamiento
Variables
Cada casilla no bloqueada del tablero se modela como una variable de decisión. Su
dominio corresponde al conjunto de piezas disponibles (ya que pueden repetirse ilimitadamente).
Dominios
Di = {todas las piezas posibles} para cada casilla i. No hay limite de uso por tipo de
pieza
Restricciones
1. Compatibilidad de bordes:
Si una pieza borde derecho R y la pieza vecina izquierda L, debe cumplirse R = L.
Esto se verificó antes de colocar una pieza, inspeccionando las piezas adyacentes
ya asignadas.
2. Borde negro (N ):
Si una pieza tiene un borde con color negro, no puede existir ninguna pieza en la
casilla adyacente. Este caso se filtra antes de asignar la pieza.
3. Casillas bloqueadas (#):
Se ignoran en la búsqueda y no forman parte del conjunto de variables.
4. Colores:
Si el color principal de la pieza coincide con el color de la casilla, su peso (WEIGHT)
se duplica al calcular el puntaje total.
El algoritmo recorre las casillas no bloqueadas en orden lineal (almacenadas en el arreglo
cells[]) y, en cada paso, intenta colocar todas las piezas válidas según las restricciones.
Cada vez que se alcanza una asignación completa válida, se actualiza el mejor puntaje
encontrado.
b) Representación de datos
Piece: estructura con los atributos weight, color, up, down, left, right.
board: matriz N × M de caracteres (’-’, ’#’ o color).
cells[]: lista de casillas no bloqueadas, que define el orden de exploración.

5
 T2 - Agustı́n Alonso De Juan Córdova - 24662100
placed[]: arreglo paralelo a cells[] que guarda qué pieza se colocó en cada posición.
dfs(): función recursiva que implementa el backtracking, acumulando puntaje parcial
y verificando factibilidad local.

Optimizaciónes
Optimización 1: Poda mediante cota superior Antes de expandir cada nodo del árbol de
búsqueda, se calcula una cota superior del puntaje posible a partir de la posición actual:

n−1
X
U B = puntaje actual + maximo peso posible en la casilla i
i=pos

Si U B es menor o igual al mejor puntaje actual (best score), se descarta toda esa rama.
Esta técnica reduce drásticamente el número de combinaciones exploradas, especialmente en
tableros grandes.
La cota superior se precomputó en el arreglo suffix upper[], que almacena la suma acumulada
del máximo peso posible por casilla (considerando el bonus de color más favorable).
Optimización 2: Validación incremental de restricciones
Al intentar colocar una pieza, el algoritmo sólo verifica las casillas adyacentes ya asignadas,
en lugar de revisar todo el tablero. Esto se implementa en la función can place(), que
comprueba bordes y reglas de color en tiempo O(1) por intento. Ası́, cada paso del backtracking
tiene costo lineal solo en el número de casillas ya asignadas localmente, no en todo el tablero.
Otras optimizaciones a hacer
Orden dinámico de variables: seleccionar primero las casillas con más restricciones
(por ejemplo, rodeadas de piezas o bordes) podrı́a reducir aún más la búsqueda.
Memorización parcial: almacenar configuraciones parciales equivalentes podrı́a evitar
recomputar subproblemas repetidos, aunque requerirı́a hashing de estados.

6
 T2 - Agustı́n Alonso De Juan Córdova - 24662100
Comentarios adicionales y Bibliografı́a
Comentario 1: Quiero decir que no tuve mucho tiempo para realizar está tarea (al igual
que la pasada) asi que no logre implementar todo de la manera mas eficiente y lo hice mas
por pequeñas cosas que vi por internet y ocurrencias mias.
Comentario 2: Por la falta de tiempo no alcance que a señalar todos las referencia de linea
en el informe.
Comentario 3: Por alguna razón al usar time en wsl va con un buen tiempo, pero al usar
valgrind el tiempo se triplica o hasta se quintuplica
Comentario 4: En realidad el uso del numero primo fue porque fui haciendo pruebas y
vi que con los numeros primos altos funcionaba mejor y despues le pregunte a chatgpt un
numero primo alto para el algoritmo. Luego yo le encontre una logica matematica aplicable
Enlaces
[Link]
[Link]
[Link]