Progetto-algoritmi-Giugno-Luglio-Settembre

Questa repository privata contiene tutti gli eseguibili, gli appunti, i test, le relazioni per il progetto di algoritmi e strutture dati

---

Appunti sulla prima traccia del progetto di Algoritmi e Strutture dati

Tre date:

• 16 giugno 2025.
• 6 luglio 2025.
• 1 settembre 2025.

Problema: Parole e catene di parole

Concetti preliminari

Una parola è un'insieme di caratteri e ogni parola è composta da caratteri dell'alfabeto inglese minuscolo.

Per ogni parola $x$ ci sono le seguenti operazioni elementari di editing:

• Inserzione: la possibilità di inserire lettere in qualunque posizione di una qualunque parola.
• Cancellazione: la possibilità di cancellare un qualsiasi carattere da $x$.
• Sostituzione: la possibilità di sostituire un qualsiasi carattere di $x$.
• Scambio: la possibilità di scambiare due caratteri adiacenti di $x$.

Ogni parola $x$ e $y$ ha una distanza di editing (la distanza di editing è associabile alla distanza di Hamming) che è sostanzialmente il minor numero di operazioni elementari di editing necessarie per passare da $x$ a $y$. Due parole con distanza di editing pari a 1 sono definite simili.

Una catena tra due parole $x$ e $y$ è una qualunque sequenza di parole che inizia con $x$ e finisce con $y$, dove ogni coppia di parole nella sequenza è formata da parole simili. Possiamo dire che in una catena le parole sono simili a coppie.

Un gruppo è l'insieme massimale di parole, contenute nel dizionario, tali per cui si può trasformare una parola in un'altra con una catena di parole tutte interne al gruppo.

Schemi, assegnazioni e compatibilità

Uno schema è una sequenza finita di caratteri che appartengono all'alfabeto delle lettere inglesi minuscole e maiuscole e che hanno necessariamente almeno una lettera maiuscola.

Un'assegnazione è una funzione $\sigma : {A, B, \ldots, Z} \rightarrow {a, b, \ldots, z}$. In breve $\sigma$ associa ad ogni lettera maiuscola una sola lettera minuscola. Per esempio se viene associato $A \to r$, ogni qualvolta che ci sarà una $A$ nello schema essa diventerà una $r$, perciò una lettera maiuscola non può essere associata a più lettere minuscole, non vale il viceversa. Infatti io posso associare a più lettere maiuscole dello stesso schema, la stessa lettera minuscola. Va sottolineato che un'assegnazione non cambia mai le lettere minuscole.

Una parola $x$ è compatibile con un generico schema $S$ se, eseguendo un assegnazione su quello schema, si può raggiungere $x$, quindi se $x = \sigma(S)$.

Due schemi sono compatibili se esiste almeno una parola che è compatibile con entrambi.

---

Specifiche di progettazione e implementative

Le operazioni, che non devono necessariamente essere funzioni, da implementare nel progetto sono le seguenti:

• crea(): Crea un nuovo dizionario inizializzando, se presente, quello già esistente.
• carica(*os.File): Inserisce le parole e gli schemi separati da spaziature, tabulazioni o a capo presenti nel file, di testo, passato come argomento. Se il file non esiste o non è di tipo testo, allora non viene eseguita nessuna operazione.
• stampa_parole(): stampa tutte le parole del dizionario.
• stampa_schemi(): stampa tutti gli schemi del dizionario.
• inserisci(w string): Inserisce all'interno del dizionario lo schema o la parola w.
• elimina(w string): Rimuovi la parola o lo schema w dal dizionario.
• ricerca(S string): ricerca dello specifico schema.

---

Idee implementative

Per la struttura dati dizionario si può usare una struttura formata da due mappe, una contente gli schemi e l'altra contenente le parole. Come chiave si può utilizzare la stringa effettiva dello schemo che come valore utilizza tutte le parole compatibili. In poche parole la struttura dizionario è formata in questo modo:

• schemi[string]struct{}: Mappa da schema a struct vuota. Questa scelta è fatta per far sì che la mappa sia complessivamente più leggera e comunque mantenga la sua proprietà di fornire istantaneamente il risultato.
• parole[string]struct{}: contiene tutte le parole del dizionario. Le motivazioni della scelta della mappa sono analoghe a quelle fornite prima.

Funzioni e metodi

Distanza

Per la distanza è stata implementata una funzione che calcola la distanza di Demerau-Levhstain fra due stringhe. Ho preso lo pseudo codice del prof Pighizzini per la teoria della programmazione dinamica, poi ho integrato con lo pseudo codice preso da wikipedia nella pagina dedicata alla distanza di Demerau-Levhstain, visto che a quanto pare a lezione abbiamo studiato l'algoritmo di Levhstain (ma senza l'operazione di swap).

Ricerca

Per la ricerca si intende procedere in questo modo:

Suggerimento di Claude.

Per la ricerca si controllano tutte le parole compatibili con lo schema. Non vengono salvate le informazioni trovate ma vengono stampate direttamente. La scelta deriva dall'opzione scartata di salvare le parola compatibili con un determinato schema, dato che tanto non è plausibile cercare più volte la compatibilità.

In pratica si cercano parole con la stessa lunghezza dello schema e si controlla se individuano le possibili sostituzioni fatte da $\sigma$, salvando le allocazioni in una mappa map[rune]rune.

Catena

La funzione catena è stata implementata mediante una BFS che cerca la catena più corta per arrivare ad una determinata parola partendo da un'altra parola del dizionario.

Ho implementato una struttura dati, su suggerimento di claude, che contiene il percorso per arrivare alla parola trovata fino ad ora, il numero di passi per arrivare a quella parola e la parola stessa.

La struttura dati si chiama nodoPila. Questa struttura dati viene inserita all'interno di una struttura dati list, fornita dal package container/list. Il package container list implementa senza problemi, e in maniera ottimizzata, una lista doppiamente concatenata.