liga(hall,corredor,90,190).
liga(hall,sala,160,190).
liga(sala,cozinha,90,190).
liga(cozinha,corredor,100,200).
liga(cozinha,lavandaria,80,180).
liga(cozinha,arrumos,80,180).
liga(corredor,wc,90,200).
liga(corredor,quarto1,95,200).
liga(corredor,quarto2,95,200).
liga(corredor,quarto_suite,120,200).
liga(quarto_suite,wc_suite,90,200).
liga(quarto_suite,terraço,200,200).
liga(sala,terraço,240,200).

% =================================================================

% a)
ppp(X,Y,Z,LP,AP,n):- Z < AP,(X < LP; Y < LP),!.
ppp(X,Y,Z,LP,AP,x):- X < AP,(Z < LP; Y < LP),!.
ppp(X,Y,Z,LP,AP,y):- Y < AP,(Z < LP; X < LP).

% b)
caminho(X,Y,Z,Div_Partida,Div_Chegada,Lista_Divisoes,N):-
    caminho2(X,Y,Z,Div_Partida,Div_Chegada,[Div_Partida],Lista_Divisoes,0,N).

caminho2(_,_,_,Div_Chegada,Div_Chegada,Divisoes,Lista_Divisoes,N,N):-
    reverse(Divisoes,Lista_Divisoes).
caminho2(X,Y,Z,Div_Partida,Div_Chegada,Divisoes,Lista_Divisoes,N,NFinal):-
    ligacao(Div_Partida,Div_Passagem,LP,AP),
    \+ member(Div_Passagem,Divisoes),
    ppp(X,Y,Z,LP,AP,T),
    (T == n -> N1 is N; N1 is N + 1),
    caminho2(X,Y,Z,Div_Passagem,Div_Chegada,[Div_Passagem|Divisoes],Lista_Divisoes,N1,NFinal).

ligacao(Div1,Div2,LP,AP):-
    liga(Div1,Div2,LP,AP);
    liga(Div2,Div1,LP,AP).

% c)
todos_caminhos(X,Y,Z,Div_Partida,Div_Chegada,LLista_Divisoes):-
    findall(p(N,Lista_Divisoes),
            caminho(X,Y,Z,Div_Partida,Div_Chegada,Lista_Divisoes,N),
            LLista_Divisoes).

% d)
menosdivtomb(X,Y,Z,Div_Partida,Div_Chegada,Lista_Divisoes):-
    findall(p(Len,N,Lista_Divisoes),
            (caminho(X,Y,Z,Div_Partida,Div_Chegada,Lista_Divisoes,N),
            length(Lista_Divisoes,Len)),
            LLista_Divisoes),
    sort(LLista_Divisoes,[p(_,_,Lista_Divisoes)|_]).