martedì 7 aprile 2015

Anagrammi italiani

Data una serie di lettere, trovare tutte le parole valide nel minor tempo è una sfida di programmazione molto difficile. Oggi, riprendendo l'articolo sul gioco scarabeo, vedremo il metodo migliore e più veloce.
Per avere dei risultati sorprendenti, non bisogna fare tutti gli anagrammi possibili delle lettere. Ad esempio, date le lettere AMOR un programma lento si metterebbe a cercare tutti i possibili anagrammi:

a, am, ma, amo, oma, oam, amor, ecc.

Ma ciò è sbagliato!
Non ci servono tutti gli anagrammi, ma solo la firma delle parole. La firma è la serie di lettere di una parola, ordinandole alfabeticamente; ad esempio:
  • amor  ->  amor
  • ramo ->  amor
  • Roma -> amor
Come vedete le tre parole diverse hanno la stessa firma, quindi date le parole AMOR, le uniche firme che ci servono sono:

a, am, amo, amor, amr, ao, aor, ar, m, mo, mor, mr, o, or, r

sono solo 15 elementi, mentre un programma generico di anagrammi ne produrrebbe 64.
A questo punto ci serve un database che contenga le firme di tutte le parole valide, e le relative firme; cercando tutte le parole con una determinata firma, otterrete tutti gli anagrammi validi per quelle lettere.
Il codice del programma è quasi tutto qui:

on mouseUp
   put the text of field "lettere" into lettere
   #ordiniamo alfabeticamente
   #put ordinaalfab(lettere) into lettere
   put lettere & CR into field "combinazioni"
   rimuovilettera lettere
   sort field "combinazioni"
   put the text of field "combinazioni" into lista
   put empty into field "combinazioni"
   repeat for each line tLine in lista
      trovaparole tLine
   end repeat
end mouseUp

function ordinaalfab lettere
   repeat for each char tChar in lettere
      put tChar & CR after let2
   end repeat
   delete last char of let2
   sort let2
   replace CR with empty in let2
   return let2
end ordinaalfab

on trovaparole lettere
   put the connessione of this card into connID
   put "SELECT parola FROM parole WHERE firma='" & lettere & "'" into tSQL      
   put revDataFromQuery(tab,return,connID,tSQL) into tRecords   
   if tRecords is not empty then
      put tRecords & CR after field "combinazioni"
   end if
end trovaparole


on controlla lettere
   put ordinaalfab(lettere) into lettere
   if lettere is not among the lines of field "combinazioni" then      
      put lettere & CR after field "combinazioni"
   end if
end controlla

on rimuovilettera lettere
   put the number of chars of lettere into n
   repeat with i=1 to n
      put lettere into temp
      delete char i of temp
      controlla temp
      rimuovilettera temp
   end repeat  
end rimuovilettera



Il programma potete scaricarlo da qui: risolutore scarabeo.

Nessun commento:

Posta un commento