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

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

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

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

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(_,_,_).

caeser(_,[],[]).
caeser(S,[P|PR],[C|CR]) :- shifted(S,P,C), caeser(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(S,L) :- append(_,S,X), append(X,_,L).

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).
