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,T):-
    (Z =< AP,(Y=<LP;X=<LP) ->  T = 'n';
    Y =< AP,(Z=<LP;X=<LP) ->  T = 'y';
    X =< AP ,(Y=<LP;Z=<LP)->  T = 'x').

%b)
%caminho(_,_,_,Div_Chegada,Div_Chegada,[Div_Chegada],0):-!.
%caminho(X,Y,Z,Div_Partida,Div_Chegada,Lista_Divisoes,N):-
%    liga(Div_Partida,Div_Chegada,LP,AP),
%    ppp(X,Y,Z,LP,AP,T),
%    (T == 'y'; T == 'x' -> N = 1),
%    Lista_Divisoes = [Div_Partida,Div_Chegada].

%caminho(X,Y,Z,Div_Partida,Div_Chegada,Lista_Divisoes,N).

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

caminho2(_,_,_,Dest,[Dest|T],[Dest|T],N,N).
caminho2(X,Y,Z,Dest,[H|T],LD,NT,N):-
	%evitar backtracking
	H\==Dest,
	%liga��o bi-direccional
	(liga(H,NDiv,LP,AP);liga(NDiv,H,LP,AP)),
	%evitar caminhos circulares
	\+ member(NDiv,[H|T]),
	%a porta permite passagem
	%testar tipo de tombo para actualizar coordenadas e contar tombos
	ppp(X,Y,Z,LP,AP,Tombo),
	(
		(Tombo==n,
		 caminho2(X,Y,Z,Dest,[NDiv,H|T],LD,NT,N));
		(Tombo==x,
		 NT1 is NT+1,
		 caminho2(Z,Y,X,Dest,[NDiv,H|T],LD,NT1,N));
		(Tombo==y,
		 NT1 is NT+1,
		 caminho2(X,Z,Y,Dest,[NDiv,H|T],LD,NT1,N))
	).

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

%d)
menosdivtomb(X,Y,Z,Div_Partida,Div_Chegada,Lista_Divisoes):-
    todos_caminhos(X,Y,Z,Div_Partida,Div_Chegada,[P|LL]),
    menos_divisoes(LL,P,Lista_Divisoes).

menos_divisoes([],P,L):- P = p(_,L).
menos_divisoes([PAtual|LL],PAnt,L):-
    PAnt = p(NAnt,LAnt),
    PAtual = p(NAtual,LAtual),
    length(LAnt,LenAnt),
    length(LAtual,LenAtual),
    (LenAnt < LenAtual ->  menos_divisoes(LL,PAnt,L);
    LenAnt == LenAtual ->  (NAnt < NAtual ->  menos_divisoes(LL,PAnt,L);
                           menos_divisoes(LL,PAtual,L));
    LenAnt > LenAtual ->  menos_divisoes(LL,PAtual,L)).