% concatena duas listas
concatena([], Lista, Lista).
concatena([X|Y], List2, [X|Resp]) :-
          concatena(Y, List2, Resp).

% inverte uma lista
reverte([], []).
reverte([X|Y], L) :-
          reverte(Y, Y1), concatena(Y1, [X], L).

% função auxiliar para o Ex p1
soma([], [], 0).
soma([X|List], [K|M], K) :-
          soma(List, M, N), K is N+X.

% retorna a lista das, somas, porém invertida
soma_aux(List, Resp) :-
          reverte(List, B), soma(B, Resp, _).

% booleano para ver se X é maior que Y
maior_que(X, Y) :- X > Y.

% realiza a junção de duas listas ordenadas, formando uma lista ordenada, mas com repetição
junta_com_rep([], List, List2) :-
          concatena([], List, List2).
junta_com_rep(List, [], List2) :-
          concatena(List, [], List2).
junta_com_rep([X|Caud1], [Y|Caud2], [X|M]) :-
          not(maior_que(X, Y)),
          p3(Caud1, [Y|Caud2], M).
junta_com_rep([X|Caud1], [Y|Caud2], [Y|M]) :-
          maior_que(X, Y),
          junta_com_rep([X|Caud1], Caud2, M).

% verifica se o elemento X aparece em uma lista
aparece(X, [X|_]).
aparece(X, [_|Y]) :-
          aparece(X, Y).

% retira todas as ocorrências de um elemento X da lista
retirar_elemento(_, [], []).
retirar_elemento(X, [X|List1], Resp) :-
          retirar_elemento(X, List1, Resp).
retirar_elemento(X, [Y|List1], [Y|Resp1]) :-
          not(X == Y), retirar_elemento(X, List1, Resp1).

% retira a repeticao dos elementos da lista
retirar_repeticao([], []).
retirar_repeticao([X|List1], [X|List2]) :-
          retirar_elemento(X, List1, Aux2),
          retirar_repeticao(Aux2, List2).

% retira apenas uma ocorrência de um elemento X da lista
retirar_uma_ocu(X, [X|L], L).
retirar_uma_ocu(X, [Y|L], [Y|L1]) :-
          retirar_uma_ocu(X, L, L1).

% realiza a intersecção de duas listas, mas permitindo repetições
intersec_com_rep([], _, []).
intersec_com_rep([X|List1], List2, [X|Resp1]) :-
          aparece(X, List2), intersec_com_rep(List1, List2, Resp1), !.
intersec_com_rep([X|List1], List2, Resp1) :-
          not(aparece(X, List2)),
          intersec_com_rep(List1, List2, Resp1), !.

% função que pega duas listas, verifica as posições com a mesma letra, coloca num contador e gera duas listas sem essas posições
retirar_pos_igual([], [], [], [], 0).
retirar_pos_igual([X|List1], [X|List2], Resp1, Resp2, M) :-
          retirar_pos_igual(List1, List2, Resp1, Resp2, N), M is N+1.
retirar_pos_igual([X|List1], [Y|List2], [X|Resp1], [Y|Resp2], M) :-
          not(X==Y), retirar_pos_igual(List1, List2, Resp1, Resp2, M).

% realiza a contagem do Y da questão p2
contar_igual_pos_errada([], _, 0).
contar_igual_pos_errada([X|List1], List2, M) :-
          aparece(X, List2),
          retirar_uma_ocu(X, List2, Resp1),
          contar_igual_pos_errada(List1, Resp1, L),
          M is L + 1.
contar_igual_pos_errada([X|List1], List2, M) :-
          not(aparece(X, List2)),
          contar_igual_pos_errada(List1, List2, M).

% predicado das questões
p1(List, Resp) :-
          soma_aux(List, Resp1), reverte(Resp1, Resp).

p2(List1, List2, X, Y) :-
          retirar_pos_igual(List1, List2, Resp1, Resp2, X),
          contar_igual_pos_errada(Resp1,Resp2, Y).

p3(List1, List2, Resp) :-
          junta_com_rep(List1, List2, Resp1),
          retirar_repeticao(Resp1, Resp).

p4(List1, List2, Resp) :-
          intersec_com_rep(List1, List2, Resp1),
          retirar_repeticao(Resp1, Resp).