remove([(C,N)|Coins],C,[(C,M)|Coins]) :- N > 0, M is N - 1.
remove([X|Coins],C1,[X|NCoins]) :- remove(Coins,C1,NCoins).

put([(C,N)|Coins],C,[(C,M)|Coins]) :- !, M is N + 1.
put([X|Coins],C1,[X|NCoins]) :- put(Coins,C1,NCoins).
put([],C,[(C,1)]).

change(0,_,[]).
change(X,Av,Change) :- remove(Av,C,NAv), X1 is X - C, X1 >= 0,
                       change(X1,NAv,NChange),
                       put(NChange,C,Change).

changeNoDups(0,_,[]) :- !.
changeNoDups(X,[(C,N)|Coins],Change) :-
                       remove([(C,N)|Coins],C,NAv),
                       X1 is X - C, X1 >= 0,
                       changeNoDups(X1,NAv,NChange),
                       put(NChange,C,Change).
changeNoDups(X,[_|Coins],Change) :- changeNoDups(X,Coins,Change).


shifted(S,P,C) :- integer(S), integer(P), !, C is mod(P + S, 256).
shifted(S,P,C) :- integer(S), integer(C), !, P is mod(C - S, 256).
shifted(S,P,C) :- integer(P), integer(C), !, S is mod(C - P, 256).
shifted(_,_,_).

caesar(_,[],[]).
caesar(S,[P|PR],[C|CR]) :- shifted(S,P,C), caesar(S,PR,CR).

print(X) :- writef("%s\n", [X]).

vigenere(_,[],[]).
vigenere([S|SR],[P|PR],[C|CR]) :- shifted(S,P,C), append(SR,[S],NSR),
                                  vigenere(NSR,PR,CR).

subseq(X,Y) :- append(_,X1,Y), append(X,_,X1).

append2([],B,B).
append2([A|AR],B,[C|CR]) :- C = A, append2(AR,B,CR).

encrypted([140,146,95,96,96,80,170,147,97,81,115,171,82,164,153,151,83,168,146,171,94,80,165,154,152,81,164,147,159,149,81,162,165,160,148,151,150,165,163,151,83,146,164,82,158,145,164,166,83,170,150,147,164,92,81,127,156,164,164,82,133,159,161,154,156,150,112,82,95,80,133,154,152,81,164,147,159,149,81,162,165,160,148,151,150,165,163,151,83,146,164,82,151,166,150,164,172,81,170,151,147,162,81,124,148,158,150,165,83,80,94,82,138,150,157,158,94,80,122,89,159,157,81,150,161,80,158,171,83,167,150,164,171,80,147,151,166,165,82]).

decrypt(K) :- encrypted(T), length(K,8), subseq("procedure",X),
              vigenere(K,X,T).


test(X,Y) :- Y = [2,3,4,5|X].
