:-use_module(library(lists)).

%%% CIFRARIO DI VIGENERE 
%%% vigenere(+In,+Key,-Out)
%%% Semplifica prima il testo In (eg "Ciao, io sono")
%%% togliendo spazi e punteggiatura e usando le sole minuscole
%%% (dunque si ottiene "ciaoiosono"), poi applica il Cifrario
%%% con chiave Key (eg "abc"). Il risultato e' in Out

vigenere(In,Key,Out) :-
    filter_string(In,Temp),
    vigenere(Temp,Key,Key,Out),
    name(Crypt,Out),write(Crypt),nl. %%% Conversione per output
    
%%% Aux:
  
vigenere([],_,_,[]).
vigenere([A|R],[],Key, Out) :-
   vigenere([A|R],Key,Key,Out).
vigenere([A|R],[K|Kr],Key,[B|Out]) :-
   sum(A,K,B),
   vigenere(R,Kr,Key,Out).

%%% CIFRARIO INVERSO DI VIGENERE 
%%% rev_vigenere(+In,+Key,-Out)
%%% In e' il testo cifrato ("....")
%%% key e' una possibile chiave ("....")
%%% Out e' il corrispondente testo originario.

rev_vigenere(In,Key,Out) :-
    inv(Key,RevKey),
    vigenere(In,RevKey,Out).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% decritta(+TESTOCIFRATO,-A,-E,-NE)
%%% Legge il testo cifrato (meglio se lungo)
%%% Usando la tecnica del best_alignment congettura la
%%% lunghezza della chiave "A" e la restituisce
%%% Dunque estrae la proiezione "I"-esima del codice
%%% e con la tecnica statistica fornisce le 3 sostituzioni
%%% piu' probabili in due formati

decritta(TESTOCIFRATO,I,A,E,NE) :-
    best_alignment(TESTOCIFRATO,A,_,_),
    extract(TESTOCIFRATO,I,A,PROIEZIONE),
    %%%name(PP,PROIEZIONE),write(PP),nl,
    frequency(PROIEZIONE,[F1,F2,F3 |_]),
    sort_frequency([P |_]),name(P,[PC]),
    minus(F1,PC,E1), minus(F2,PC,E2), minus(F3,PC,E3),
    E=[E1,E2,E3], name(NE,E).

%%% auto_decritta(+TESTOCIFRATO,-Chiave,-Output)
%%% automatizza la ricerca della chiave, usando backtracking
%%% (l'utente guarda l'output e decide)
%%%%%%
%%% Ulteriore parametro opzionale: 
%%% una stringa che si sospetta possa starci nel testo.
%%% Prova con testo1 e strada.
%%% Divertente provare testo2 e italia

auto_decritta(TESTOCIFRATO,H,OUT) :-
    decritta(TESTOCIFRATO,1,L,_,_),
    auto_decritta(1,L,TESTOCIFRATO,HINTS),
    pickone(H,HINTS),
    rev_vigenere(TESTOCIFRATO,H,OUT),
    name(OutN,OUT), name(HN,H),
    write(HN),write(-->),write(OutN),nl.

auto_decritta(TESTOCIFRATO,H,OUT,STRING) :-
    auto_decritta(TESTOCIFRATO,H,OUT),
    sublist(OUT,STRING,_,_,_).
    
%%%%%%%%%%% ausiliarie    

auto_decritta(A,B,_,[]) :- A > B, !.
auto_decritta(A,B,TESTOCIFRATO,[L|R]) :- 
    decritta(TESTOCIFRATO,A,_,L,_),
    write('### '),name(PP,L),write(PP),nl,
    A1 is A+1, 
    auto_decritta(A1,B,TESTOCIFRATO,R).
    
pickone([],[]).    
pickone([A|R],[B|S]) :-
    member(A,B),
    pickone(R,S).    

%%% Aritmetica in Z26 - a=97, z =122.

sum(A,B,Co) :-
   C is A + B - 97,
  (C =< 122 -> Co = C;
   C > 122  -> Co is C - 26).
   
minus(A,B,Co) :-
  (A >= B -> Co is A - B + 97;
   A < B  -> Co is A - B + 97 + 26). 

inv([],[]).
inv([A|R],[Co|S]) :-
  minus(122,A,C),
  sum(C,98,Co),
  inv(R,S).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% best_alignment(+LIST, -BEST,-NBEST,'RL).
%%%%%%
%%% Dato un codice crittato con Vigenere (LIST)
%%% prova i punti fissi con gli allineamenti con se'
%%% stesso fino a lunghezza MAXKEY
%%% (default 30)
%%%%%%
%%% Permette di scoprire la lunghezza della chiave
%%% che e' probabilmente BEST o un suo divisore. 
%%% NBEST e' il numero di matchings.
%%% RL riassume gli allineamenti (si vede se altri 
%%% valori sono confrontabili con NBEST). 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

best_alignment(LIST,BEST,NBEST,RL) :-
   length(LIST,N),
   MAXKEY is min(30,N),
   best_alignment(LIST,1,MAXKEY,0,0,BEST,NBEST,RL).
   
best_alignment(   _,N,N,IBEST,NBEST,IBEST,NBEST,[]).
best_alignment(LIST,I,N,Iold,Kold,Inew,Knew,[[I,VAL]|Rl]) :-
   I < N,I1 is I+1,
%%%   format("Running with I = ~d ~n",[I]),
   align(LIST,I,VAL),
   (VAL > Kold   ->  best_alignment(LIST,I1,N,I,VAL,Inew,Knew,Rl), !;
    true         ->  best_alignment(LIST,I1,N,Iold,Kold,Inew,Knew,Rl)).

align(LIST,I,VAL) :-
    length(NEW,I),
    append(NEW,LIST,NEWLIST),
    count(LIST,NEWLIST,VAL).
    
count([],_,0).
count([A|R],[B|S],VAL) :-
   count(R,S,VAL1),
   (A == B -> VAL is VAL1 + 1, !;
    true   -> VAL=VAL1).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%%%% reduce_string
%%%% Toglie spazi e punteggiatura e porta 
%%%% maiuscole in minuscole
    
filter_string([],[]).     
filter_string([A|R],S) :-
   (A < 65; (90 < A, A < 97); A > 122), 
   !,
   filter_string(R,S).     
filter_string([A|R],[B|S]) :-
   A =< 90,
   !,
   B is A + 32,
   filter_string(R,S).     
filter_string([A|R],[A|S]) :-
   97 =< A,
   filter_string(R,S).     

%%%%%%%%%%%%%%%%%%
%%% extract(+L,+I,+K,-Out)
%%% Estrae i caratteri i, i+k, i+2k, ... dalla lista L
%%% e li mette in Out
%%%%%%%%%%%%%%%%%%

extract(L,I,K,Out) :-
   I1 is I - 1,
   length(A,I1),
   append(A,B,L),
   extract(B,K,Out).

extract([],_,[]).
extract([A|L],K,[A]) :-
   length(L,N), N < K, !.
extract(L,K,[A|Out]) :-
   length([A|B],K), 
   append([A|B],C,L),
   extract(C,K,Out).
   
%%%%%% calcola frequenze

frequency(TEXT,LIST) :-
   compute_flist(97,122,TEXT,FLIST),
   sort(FLIST,SLIST),
   rev_filter(SLIST,[],LIST).

compute_flist(A,B,_,[]) :- A > B , !.
compute_flist(A,B,TEXT,[[N,A]|R]) :- 
     findall(_,member(A,TEXT),LA),
     length(LA,N),
     A1 is A + 1,
     compute_flist(A1,B,TEXT,R).

%%%%%%%%

writestring([]) :- nl.
writestring([A|R]) :- write(A),writestring(R).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

ita_freq(a,11.74).  ita_freq(b,0.92). 
ita_freq(c,4.5).    ita_freq(d,3.73).
ita_freq(d,3.73).   ita_freq(e,11.79).
ita_freq(e, 11.79). ita_freq(f, 0.95).
ita_freq(g, 1.64).  ita_freq(h, 1.54).
ita_freq(i, 11.28). ita_freq(l, 6.51).
ita_freq(m, 2.51).  ita_freq(n, 6.88).
ita_freq(o, 9.83).  ita_freq(p, 3.05).
ita_freq(q, 0.51).  ita_freq(r, 6.37).
ita_freq(s, 4.98).  ita_freq(t, 5.62). 
ita_freq(u, 3.01).  ita_freq(v, 2.10).
ita_freq(z, 0.49).

sort_frequency(OUT) :-
   findall([F,L],ita_freq(L,F),LIST),
   sort(LIST,SORTED),
   rev_filter(SORTED,[],OUT).
   
rev_filter([],OUT,OUT).
rev_filter([[_,L]|R],S,OUT) :-
   rev_filter(R,[L|S],OUT).

%%%%%%%%%%
   
testo1("La strada dove e' avvenuto l'incidente era stata chiusa per via del maltempo e delle frane. In molte zone del Centro-Nord infatti ci sono state frane e allarmi per i fiumi in piena, a causa delle abbondanti piogge. Allarme slavine in Veneto. Da domani e' attesa una forte diminuzione delle temperature e un rinforzo dei venti dai quadranti settentrionali. Nevicate, anche a quote molto basse, si verificheranno sulle regioni adriatiche. Venerdi le temperature saranno ancora basse, ma le nevicate sulle regioni centro-meridionali adriatiche saranno meno intense. Sulla base delle informazioni disponibili, la Protezione Civile prevede anche per oggi rovesci molto forti che si potranno verificare su Liguria di Levante, alta Toscana, Appennino Emiliano e settori alpini e prealpini centro-orientali. Precipitazioni anche sul resto del Nord e della Toscana, Lazio, Umbria, Marche e Abruzzo. Ancora banchi di nebbia sulla Pianura Padana e forte ventilazione da Sud su tutte le regioni centrali e sulla Sicilia occidentale. L'incidente mortale in Liguria. La sovrintendente Teresa Marcocci era sul posto per rilevare un incidente capitato a un automobilista la cui auto era stata colpita da un ramo spezzato. Mentre era intenta ai rilievi, un altro albero e' caduto, travolgendola. Sul posto sono stati tentati i primi soccorsi. Trasferita d'urgenza all'ospedale Sant'Andrea, la donna e' stata sottoposta ad un intervento chirurgico urgente, ma, purtroppo, non ce l'ha fatta. La strada della Ripa era stata riaperta solo ieri, dopo una lunga chiusura dovuta proprio al maltempo e alle frane. Da poche ore le auto avevano ripreso a circolare sull'arteria, molto trafficata. Chiusi Ponte Alto e Passo dell'Uccellino. Dalle 8 di questa mattina la Protezione civile di Modena ha chiuso ponte Alto e il ponte al Passo dell'Uccellino, ambedue sul fiume Secchia, a causa dell'onda di piena che sta attraversando il territorio comunale. Si tratta di una massa d'acqua consistente proveniente dell'Appennino che ha fatto registrare, poco dopo le 9, un livello di piena di 8,18 metri.").
testo2("Effetto Italia sulle Borse. Seduta in rialzo dopo la manovra. Lo spread cala sotto quota 380 per la prima volta da ottobre, il rendimento dei Btp scende al 6,1 . A Parigi la Merkel e Sarkozy chiedono un nuovo trattato per creare un'unione fiscale nel Vecchio continente e ribadiscono il loro  no  agli eurobond. Apertura positiva per Wall Street. La settimana decisiva per il futuro dell'euro si apre all'insegna degli acquisti trainati dalla rinnovata fiducia nell'Italia dopo la presentazione da parte del governo Monti della manovra correttiva da 30 miliardi di euro. Ma occhi puntati anche su Parigi dove, oggi, il cancelliere tedesco Angela Merkel incontrerà il presidente francese Nicolas Sarkozy per discutere dell'unione fiscale europea. La manovra Monti ha immediatamente alleviato le tensioni sul debito pubblico italiano: lo spread nei confronti dei bund tedeschi è calato sotto quota 380 punti base ai minimi da oltre un mese, mentre il rendimento dei Btp decennali scende al 6,1 . Nel frattempo Berlino ha collocato titoli del tesoro a sei mesi per 2,675 miliardi di euro al rendimento medio dello 0,0005  che diventa il nuovo minimo storico, a conferma che il Bund resta uno dei beni rifugio per eccellenza. Milano si muove in rialzo del 3 , Londra recupera lo 0,8 , Francoforte l'1,4 , Parigi l'1,5 . In spolvero i bancari a Piazza Affari sulla scia del decreto varato ieri dal governo: Mps avanza del 9 ; Banco Popolare +5 ; Unicredit +4 . Bene anche Wall Street dove il Dow Jones viaggia a +1,2  e il Nasdaq a +0,9 . Negli Usa a novembre l'indice Ism dei servizi è cresciuto a 56,2 punti, mentre a ottobre gli ordini dell'industria si sono contratti dello 0,4 . Sul fronte dei Piigs - dice Michael Hewson, analista di Cmc Markets - il governo italiano si presenta agli investitori con una manovra correttiva da trenta miliardi di euro, misure delineate sia per fare cassa che per mettere in atto riforme strutturali che rendano più efficiente l'economia: a colpire è soprattutto l'impossibilità introdotta di pagare per contanti importi superiori ai mille euro, un tentativo che potrebbe rivelarsi vincente nella lotta al sommerso e riportare un senso di equità non solo tra i contribuenti italiani ma più in generale tra quelli europei. E nel frattempo l'incontro Sarkozy-Merkel servirà per fare il punto sulla crisi debitoria della zona euro e cercare di delineare una serie di proposte comuni in vista del vertice europeo del 8 e 9 dicembre prossimi. Vertice che molti sperano possa produrre, se non un accordo, almeno la sensazione che la Zona euro si stia avvicinando ad un'intesa su un piano di superamento della crisi. Seduta in rialzo per Tokyo che guadagna lo 0,6 , mentre l'euro recupera a 1,34 nei confronti del dollaro e il petrolio Wti sale oltre i 101 dollari al barile.").
%%% (inglese)
testo2("Constraint programming (CP) originates from a branch of Artificial Intelligence and, in particular, from the study of problem solving. The CP allows to tackle a wide variety of problems that traditionally arise in the areas of job scheduling, timetabling, routing, industrial planning. The key feature of this programming methodology is that the focus is on the definition and handling of some properties (constraints) of the model being studied. This methodology is able to model complex problems and to solve them efficiently [24,25].  Problem modeling is the most delicate phase, since it determines the features of the problem that are enabled to interact through constraints. Those features are abstracted by variables that can range among a specific domain, e.g., integers and real numbers, and the algebraic operations defined over them. A CP program contains mathematical expressions or relations (constraints), e.g.,  ,  , that have to be satisfied by every solution, i.e. an specific assignment of domain elements to the corresponding variables. The process of searching for solutions that satisfy every constraint is named constraint solving and it is performed by a specific program called constraint solver, or in short solver. Constraint solvers are specialized to work on a specific domain: the most common ones can work on integers, reals and sets. "). 


%%%%%%%%%%

