% vim: set ft=prolog:

% A maioria dos exercíos desta lista são da lista de 99 problemas
% para resolver em prolog. As soluções destes problemas estão em
% https://sites.google.com/site/prologsite/prolog-problems/
% Neste arquivo estão algumas soluções para os demais problemas.

%% Ex 10 %%
%% mergesort(+A, -S) is semidet
%
%  Verdadeiro se S é uma lista em ordem crescente com os mesmos elementos de A.
%  Exemplos
%  ?- mergesort([7, 2, 4, 1, 9], A).
%  A = [1, 2, 4, 7, 9].

mergesort([], []).
mergesort([A], [A]).
mergesort([A0,A1|T], S) :-
    divisao([A0,A1|T], L1, L2),
    mergesort(L1, S1),
    mergesort(L2, S2),
    merge(S1, S2, S), !.

divisao(A, B, C) :-
    length(A, T),
    N is T div 2,
    divisao_em(N, A, B, C).


%% divisao_em(+N, ?A, ?B, ?C) is nondet
%
%  Verdadeiro se A = [A_0, A_1, ..., A_N, A_(N+1), ..., A_K] e
%  B = [A_0, ..., A_N] e C = [A_(N+1), ..., A_K].

divisao_em(N, [A|As], [A|Bs], Cs) :-
    N > 0,
    N0 is N - 1,
    divisao_em(N0, As, Bs, Cs).

divisao_em(0, A, [], A).


%% merge(+A, +B, ?C) is semidet
%
%  Verdadeiro se C é a intercalação das listas A e B.

merge(A, [], A).
merge([], B, B).
merge([A|As], [B|Bs], [A|Cs]) :-
    A =< B,
    merge(As, [B|Bs], Cs).

merge([A|As], [B|Bs], [B|Cs]) :-
    A > B,
    merge([A|As], Bs, Cs).


%% Ex 13 %%
%% dobrada(?L) is semidet
%
%  Verdadeiro se L é uma lista com dois blocos consecutivos de elementos
%  iguais.
%  Exemplo
%  ?- dobrada([a, b, c, a, b, c]).
%  true.
%  ?- dobrada([a, b, a]).
%  false.

% versão simples
dobrada(L) :-
    append(A, A, L), !.

% versão eficiente
dobrada2(L) :-
    length(L, T),
    T rem 2 =:= 0,
    N is T div 2,
    divisao_em(N, L, A, A).


%% Ex 14 %%

zebra(N) :-
    % existe uma rua com três casa vizinhas
    Casa1 = casa(_, _, _), % cor, nacionalidade, animal
    Casa2 = casa(_, _, _),
    Casa3 = casa(_, _, _),
    Rua = [Casa1, Casa2, Casa3],
    % com cores diferentes
    member(casa(vermelho, _, _), Rua),
    member(casa(azul, _, _), Rua),
    member(casa(verde, _, _), Rua),
    % o inglês vive na casa vermelha
    member(casa(vermelho, ingles, _), Rua),
    % o espanhol tem como animal de estimação um jaguar
    member(casa(_, espanhol, jaguar), Rua),
    % o japonês vive ao lado de quem tem uma cobra
    ao_lado(Rua, casa(_, japones, _), casa(_, _, cobra)),
    % quem tem um cobra vive a esquerda da casa azul
    a_esquerda(Rua, casa(azul, _, _), casa(_, _, cobra)),
    % quem tem uma zebra
    member(casa(_, N, zebra), Rua).
    % writeln(Rua). % descomente a linha para ver a resposta completa

%% ao_lado(?L, ?A, ?B) is nondet
%
%  Verdadeiro se A aparece ao lado de B em L.
%  Exemplos
%  ?- ao_lado([1, 7, 4], 7, B).
%  B = 1 ;
%  B = 4 ;
%  false.

ao_lado([A,B|_], A, B).
ao_lado([A,B|_], B, A).
ao_lado([_|R], A, B) :-
    ao_lado(R, A, B).

%% a_esquerda(L, A, E) is nondet
%
%  Verdadeiro se E aparece a esquerda de A na lista L.
%  Exemplos
%  ?- a_esquerda([6, 4, 3, 8], 4, E).
%  E = 3 ;
%  E = 8 ;
%  false.
a_esquerda([A|As], A, E) :-
    member(E, As).
a_esquerda([_|As], A, E) :-
    a_esquerda(As, A, E).
