soluzione_claudiio.go

package main

import (
    "container/list"
)

// Struttura principale del dizionario
type dizionario struct {
    // Set di parole per ricerca O(1) - usando struct{} per efficienza memoria
    parole map[string]struct{}
    
    // Set di schemi per ricerca O(1) - usando struct{} per efficienza memoria
    schemi map[string]struct{}
    
    // Cache per gruppi di parole (opzionale, per ottimizzazione)
    cacheGruppi map[string][]string
    
    // Cache per famiglie di schemi (opzionale, per ottimizzazione)
    cacheFamiglie map[string][]string
    
    // Flag per invalidare le cache quando necessario
    cacheGruppiValida bool
    cacheFamiglieValida bool
}

// Struttura ausiliaria per BFS nella ricerca di catene
type nodoRicerca struct {
    parola string
    distanza int
    percorso []string
}

// Funzioni principali richieste dalle specifiche

func newDizionario() dizionario {
    return dizionario{
        parole:              make(map[string]struct{}),
        schemi:              make(map[string]struct{}),
    }
}

func esegui(d dizionario, s string) {
    // Implementazione del parsing e esecuzione comandi
    // ... (da implementare secondo le specifiche)
}

// Funzioni ausiliarie per il calcolo della distanza di editing

// Calcola la distanza di editing tra due parole usando programmazione dinamica
func distanzaEditing(x, y string) int {
    m, n := len(x), len(y)
    
    // Matrice DP per Damerau-Levenshtein distance
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    
    // Inizializzazione
    for i := 0; i <= m; i++ {
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }
    
    // Riempimento della matrice
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            cost := 0
            if x[i-1] != y[j-1] {
                cost = 1
            }
            
            dp[i][j] = min(
                dp[i-1][j]+1,      // cancellazione
                dp[i][j-1]+1,      // inserimento
                dp[i-1][j-1]+cost, // sostituzione
            )
            
            // Scambio di caratteri adiacenti (Damerau)
            if i > 1 && j > 1 && x[i-1] == y[j-2] && x[i-2] == y[j-1] {
                dp[i][j] = min(dp[i][j], dp[i-2][j-2]+cost)
            }
        }
    }
    
    return dp[m][n]
}

// Verifica se due parole sono simili (distanza = 1)
func sonoSimili(x, y string) bool {
    return distanzaEditing(x, y) == 1
}

// Trova una catena minima tra due parole usando BFS
func trovaCatenaMinima(d dizionario, start, end string) []string {
	if _, exists := d.parole[start]; !exists {
        return nil
    }
    if _, exists := d.parole[end]; !exists {
        return nil
    }
    
    if start == end {
        return []string{start}
    }
    
    // BFS per trovare il percorso più breve
    queue := list.New()
    visitati := make(map[string]struct{})
    
    queue.PushBack(nodoRicerca{
        parola:   start,
        distanza: 0,
        percorso: []string{start},
    })
    visitati[start] = struct{}{}
    
    for queue.Len() > 0 {
        elemento := queue.Remove(queue.Front()).(nodoRicerca)
        
        // Esplora tutte le parole del dizionario
        for parola := range d.parole {
            if _, visited := visitati[parola]; !visited && sonoSimili(elemento.parola, parola) {
                nuovoPercorso := make([]string, len(elemento.percorso)+1)
                copy(nuovoPercorso, elemento.percorso)
                nuovoPercorso[len(elemento.percorso)] = parola
                
                if parola == end {
                    return nuovoPercorso
                }
                
                queue.PushBack(nodoRicerca{
                    parola:   parola,
                    distanza: elemento.distanza + 1,
                    percorso: nuovoPercorso,
                })
                visitati[parola] = struct{}{}
            }
        }
    }
    
    return nil // Nessuna catena trovata
}

// Verifica compatibilità tra parola e schema
func isCompatibile(parola, schema string) bool {
    if len(parola) != len(schema) {
        return false
    }
    
    // Mappatura maiuscole -> minuscole
    assegnazione := make(map[rune]rune)
    
    for i, char := range schema {
        parolaChar := rune(parola[i])
        
        if char >= 'A' && char <= 'Z' {
            // Carattere maiuscolo nello schema
            if esistente, ok := assegnazione[char]; ok {
                if esistente != parolaChar {
                    return false
                }
            } else {
                assegnazione[char] = parolaChar
            }
        } else if char >= 'a' && char <= 'z' {
            // Carattere minuscolo nello schema
            if char != parolaChar {
                return false
            }
        }
    }
    
    return true
}

// Funzione ausiliaria min
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}