sopaLetras

Codi “vintage” d’una pràctica de C++ de l’assignatura Estructura de Dades i Algorismes (FIB).

El projecte implementa una sopa de lletres i dos mòduls principals:

• solver: cerca paraules d’un diccionari dins la sopa de lletres.
• builder: construeix/emplena una sopa de lletres posant paraules del diccionari en “forats” predefinits i omplint la resta amb lletres aleatòries.

Estructures i mòduls

sopa_letras

Representa una graella de caràcters (A..Z i *).

Funcions rellevants:

• inserta_fila(string): afegeix una fila (en mode mida variable) o omple la següent fila (en mode mida fixa).
• cadena(fil, col, lon, orientacion): retorna la cadena de longitud lon a partir de (fil,col) en una orientació.
• inserta_cadena(string, fil, col, orientacion): escriu una cadena a la graella en una orientació.
• num_filas(), num_columnas().

Orientacions suportades (8 direccions):

• H, HR, V, VR, D, DR, B, BR.

diccionario

Diccionari implementat amb un Ternary Search Tree (TST).

Operacions:

• inserta(palabra): insereix una paraula.
• prefijo(string): retorna el prefix més llarg de l’string que sigui una paraula del diccionari.
• satisfacen_patron(patron, list<string>&): retorna totes les paraules que compleixen un patró amb * com a wildcard.

solver

solver::solve(const sopa_letras& S, const diccionario& D, list<match>& L)

Busca matches en totes les orientacions a partir de totes les posicions. Per cada posició/orientació:

• genera la cadena disponible en aquella direcció
• consulta D.prefijo(...)
• si el resultat té longitud >= 4, afegeix un match a la llista

Finalment ordena la llista amb list_sort::sort(L).

builder

builder::build(const diccionario& D, const list<hueco>& Huecos, list<match>& L, sopa_letras& S)

Construeix una sopa col·locant paraules del diccionari dins una llista de forats (hueco):

• cada hueco indica (fila, columna, orientacion, longitud)
• es resol amb backtracking provant paraules que satisfan el patró actual del forat (on * és comodí)
• si es pot construir, retorna la llista de match corresponent als forats i omple els * sobrants amb lletres aleatòries A..Z.

Com executar / compilar

Aquest repositori inclou sobretot codi de biblioteca i un driver de proves:

• driver_sopa_letras.cpp fa servir headers del framework de l’assignatura (eda/gen_driver, eda/error, etc.).
• Per tant, compilar-lo “tal qual” requereix disposar d’aquest framework (eda/).

Si vols fer un executable simple sense el framework, el camí habitual és escriure un main.cpp propi que:

1. carregui una sopa (fitxer de text amb files de lletres)
2. carregui un diccionari (llista de paraules)
3. invoqui solver::solve(...) i imprimeixi els match

Format i tipus de dades

• La sopa de lletres treballa amb caràcters A..Z.
• * s’utilitza com a “cel·la buida” (especialment al builder) i com a wildcard en patrons del diccionari.

Fitxers del projecte

• sopa_letras.cpp: implementació de la graella.
• diccionario.cpp: diccionari TST, prefixos i patrons amb *.
• solver.cpp: cerca de paraules (8 direccions).
• builder.cpp: backtracking per emplenar forats + omplir aleatori.
• hueco.cpp: definició de hueco.
• driver_sopa_letras.cpp: driver de proves (framework EDA).

Notes

• El solver, tal com està implementat, tendeix a retornar el prefix més llarg que sigui paraula del diccionari per cada posició/orientació, i filtra paraules de longitud < 4.