inicial([1,s,s]).
objetivo([_,l,l]).

acao(entrar1, [2,Y,Z], [1,Y,Z]).
acao(entrar2, [1,Y,Z], [2,Y,Z]).
acao(aspirar, [1,s,Z], [1,l,Z]).
acao(aspirar, [2,Y,s], [2,Y,l]).

busca_aleatoria(P) :-
    inicial(E),
    busca_aleatoria([E:[]], [], P).

busca_aleatoria([E:C|_], _, P) :-
    objetivo(E), !,
    reverse(C, P).

busca_aleatoria([E:C|F],V,P) :-
    sucessores(E:C, V, S),
    insereAleatoriamente(S, F, NF),
    union([E], V, NV),
    busca_aleatoria(NF, NV, P).


sucessores(E:C, V, S) :-
    findall(N:[A|C], (acao(A,E,N), not(member(N, V))), S).

insereAleatoriamente(S, F, NF) :-
    append(S, F, R),
    length(R, L),
    embaralha(L, R, NF), !.

embaralha(0, F, F) :- !.
embaralha(L, F, [X | NF]) :-
    N is random(L),
    nth0(N, F, X),
    delete(F, X, R),
    M is L-1,
    embaralha(M, R, NF), !.

busca_largura(P) :-
    inicial(E),
    busca_largura([E:[]],[],P).

busca_largura([E:C |_], _, P) :-
    objetivo(E), !,
    reverse(C, P).

busca_largura([E:C | F], V, P) :-
    sucessores(E:C, V, S),
    insereNoFinal(S, F, NF),
    union([E], V, NV),
    busca_largura(NF, NV, P).

insereNoFinal(S, F, NF) :-
    append(F, S, NF), !.


busca_profundidade(P) :-
    inicial(E),
    busca_profundidade([E:[]], [], P).

busca_profundidade([E:C|_], _, P) :-
    objetivo(E), !,
    reverse(C, P).

busca_profundidade([E:C | F], V, P) :-
    sucessores(E:C , V, S),
    insereNoInicio(S, F, NF),
    union([E], V, NV),
    busca_profundidade(NF, NV, P).

insereNoInicio(S, F, NF) :-
    append(S, F, NF), !.
