test4.pl

match_one(one(L), LIn, LOut) :- append(L, LOut, LIn).
match_one(star(L), LIn, LOut) :- LIn = LOut; match_one(plus(L), LIn, LOut).
match_one(plus(L), LIn, LOut) :- match_one(one(L), LIn, LMid), match_one(star(L), LMid, LOut).
match_one(opt(L), LIn, LOut) :- LIn = LOut; match_one(one(L), LIn, LOut).

match(Expr, Str) :- foldl(match_one, Expr, Str, []).

decode_char(Key, A, B) :- B #= (A - 97 + Key) mod 26 + 97.

decode_string(_, _, [], []).
decode_string(Key1, Key2, [A|As], [B|Bs]) :-
    decode_char(Key1, A, B),
    decode_string(Key2, Key1, As, Bs).

decode(K1, K2, S1, S2) :-
    string_codes(S1, C1),
    decode_string(K1, K2, C1, C2),
    string_codes(S2, C2).

somewhere(A, B) :- member(B, A).

decrypt(Line, Dict, R) :-
    split_string(Line, " ", " ", Words),
    between(0, 25, Key1),
    between(0, 25, Key2),
    maplist(decode(Key1, Key2), Words, Decoded),
    maplist(somewhere(Dict), Decoded),
    atomics_to_string(Decoded, " ", R).