%
% Gegeben ein Hochhaus mit N Fahrstuehlen. Jeder Fahrstuhl verbindet zwei Stockwerke und haelt nicht auf den Zwischenetagen.
% Pro Stockwerk benoetigt der Fahrstuhl 1 Sekunde. Sobald das obere Stockwerk erreicht wird, faehrt der Fahrstuhl wieder nach unten.
% Alle Fahrstuehle starten auf dem unteren Stockwerk.
% Schreiben Sie ein Praedikat min_time/1, das die geringste Zeit berechnet, die es dauert um von Etage 0 in die oberste Etage zu fahren
% (inklusive Wartezeit). Der Fahrstuhlwechsel benoetigt keine Zeit.

% Inputformat:
%     top(K): oberstes Stockwerk
%     elevators(N): Zahl der Fahrstuehle
%     pro Fahrstuhl ein Fakt elevator(I,B,T): I ist die Fahrstuhlnummer, B ist das untere Stockwerk und T das obere.




%%%%%%%%%%%%%%%%%%%%%%%
% task 1
top(10).
elevators(4).
elevator(1,0,5).
elevator(2,5,10).
elevator(3,5,7).
elevator(4,7,10).

% min_time(15).

/*
%%%%%%%%%%%%%%%%%%%%%%%
% task 2
top(10).
elevators(4).
elevator(1,0,5).
elevator(2,5,10).
elevator(3,5,8).
elevator(4,8,10).


%min_time(14).

%%%%%%%%%%%%%%%%%%%%%%%
% task 3
top(19).
elevators(10).
elevator(1,0,6).
elevator(2,6,19).
elevator(3,3,6).
elevator(4,3,9).
elevator(5,9,19).
elevator(6,3,13).
elevator(7,13,17).
elevator(8,17,19).
elevator(9,9,17).
elevator(10,6,17).


%min_time(30).

%%%%%%%%%%%%%%%%%%%%%%%
% task 4
top(10).
elevators(5).
elevator(1,0,6).
elevator(2,2,6).
elevator(3,6,8).
elevator(4,8,10).
elevator(5,6,10).


%min_time(12).

%%%%%%%%%%%%%%%%%%%%%%%
% task 5
top(10).
elevators(5).
elevator(1,0,3).
elevator(2,2,6).
elevator(3,0,2).
elevator(4,3,10).
elevator(5,6,10).


% min_time(20).

%%%%%%%%%%%%%%%%%%%%%%%
% task 6
top(12).
elevators(5).
elevator(1,0,3).
elevator(2,5,10).
elevator(3,3,8).
elevator(4,8,12).
elevator(5,8,12).


%min_time(20).

%%%%%%%%%%%%%%%%%%%%%%%
% task 7
top(15).
elevators(6).
elevator(1,0,6).
elevator(2,0,8).
elevator(3,3,8).
elevator(4,1,3).
elevator(5,6,15).
elevator(6,8,15).


%min_time(21).


%%%%%%%%%%%%%%%%%%%%%%%
% task 8
top(15).
elevators(5).
elevator(1,0,3).
elevator(2,7,10).
elevator(3,3,7).
elevator(4,3,10).
elevator(5,10,15).


% min_time(25).

*/

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
% Loesung 1: pathfirst


min_time(MinT):-
     findall(T,(path(P),compute_time(P,T,0)),TL),
     min1(TL,MinT).


% computes a path from top to bottom
path(P):- top(T),path(P,[T],T).

% path(Path_complete,Path_Acc,Floor_current)
% bottom is reached
path(P,P,0).

% bottom is not yet reached
path(P,Acc,T):-
     (elevator(_,S,T);elevator(_,T,S)), % there is a fitting elevator (up or down)
     not(member(S,Acc)),  % goal floor has not yet been visited
     path(P,[S|Acc],S).




% compute_time(PathToTravel,TimeFinal,TimeAcc)
% top reached
compute_time([_],T,T).

% fahren mit Lift zwischen Stationen
% Beispiel: 17 gefahren, naechste Differenz +6 => Wartezeit ist 7
% gefahrene Stockwerke seit letztem Halt: Acc mod Diff
% zu fahren bis zum naechsten Halt: Diff-(Acc mod Diff)
% war zuletzt unten: 0 is (Acc//Diff mod 2)
% war zuletzt oben: 1 is (Acc//Diff mod 2)
% faehrt nach oben: -1 is sign(S1-S2)
% faehrt nach unten: 1 is sign(S1-S2)

compute_time([S1,S2|P],T,TAcc):-
     Diff is abs(S1-S2),
     UpDown is sign(S1-S2),
     LastStation is (TAcc//Diff) mod 2,
     compute_wait(UpDown,LastStation,Diff,TAcc,Wait),
     TimeAfterWait is TAcc + Wait,   % volle Stufen + Schritte bis zur naechsten Stufe
     TAccNew is TimeAfterWait+Diff,
     compute_time([S2|P],T,TAccNew).


% Ist an Station
compute_wait(UpDown,Position,Diff,T,Wait):-
     passend(UpDown,Position,Fit),
     0 is T mod Diff,
     Wait is Diff-Diff*Fit.


% Ist nicht an Station
compute_wait(UpDown,Position,Diff,T,Wait):-
     passend(UpDown,Position,Fit),
     Wait is Fit * Diff + Diff-(T mod Diff).

% Richtung passt
passend(1,0,0).
passend(-1,1,0).

% Richtung passt nicht
passend(1,1,1).
passend(-1,0,1).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
% Loesung 2: with lists

% inital situation elevator(CurrentPosition,Direction,Bottom,Top)
initialize(N,[elevator(B,1,B,T)|L]):-
     elevator(N,B,T),
     N1 is N-1,
     initialize(N1,L).

initialize(0,[]).


% update(Times,SitOld,SitNew)
update(0,SitNew,SitNew):-!.

update(T,SitOld,SitFinal):-
     update(SitOld,SitNew),
     T1 is T-1,
     update(T1,SitNew,SitFinal).

% update(SitOld,SitNew)
update([],[]).
update([elevator(C,D,B,T)|ELold],[elevator(C1,D1,B,T)|ELnew]):-
     update_elev(elevator(C,D,B,T),elevator(C1,D1,B,T)),
     update(ELold,ELnew).

update_elev(elevator(B,_,B,T),elevator(C1,1,B,T)):-
     C1 is B+1.

update_elev(elevator(T,_,B,T),elevator(C1,-1,B,T)):-
     C1 is T-1.

update_elev(elevator(C,D,B,T),elevator(C1,D,B,T)):-
     C \= B,
     C \= T,
     C1 is C+D.


% travel(Time,NAcc,TimeMax,CurrentFloor,Visited,Goal,Sit,WaitCounter)

travel(N,N,_,G,V,G,_,_):- write(V).

travel(_,NAcc,TimeMax,_,_,_,_,_):- NAcc>TimeMax,!,fail.


% traveller is at bottom position of some elevator
travel(N,NAcc,TimeMax,F,V,G,SitOld,_):-
     member(elevator(F,_,F,T),SitOld),
     not(member(T,V)),
     write('visited floors '),write(V),nl,
     write(NAcc),write(' takes elevator to floor '), write(T),nl,
     Dist is T-F,
     update(Dist,SitOld,SitNew),
     NAccNew is NAcc+Dist,
     travel(N,NAccNew,TimeMax,T,[T|V],G,SitNew,0).

% traveller is at top position of some elevator
travel(N,NAcc,TimeMax,F,V,G,SitOld,_):-
     member(elevator(F,_,B,F),SitOld),
     not(member(B,V)),
     write('visited floors '),write(V),nl,
     write(NAcc),write(' takes elevator to floor '), write(B),nl,
     Dist is F-B,
     update(Dist,SitOld,SitNew),
     NAccNew is NAcc+Dist,
     travel(N,NAccNew,TimeMax,B,[B|V],G,SitNew,0).


% traveller waits

travel(N,NAcc,TimeMax,F,V,G,SitOld,Wold):-
     Wnew is Wold + 1,
     Wnew < 2*G, !,
     update(SitOld,SitNew),
%     write(NAcc),write(' waits on floor '), write(F),nl,
     NAccNew is NAcc+1,
     travel(N,NAccNew,TimeMax,F,V,G,SitNew,Wnew).


min_time(Min):-
     elevators(N),
     initialize(N,Sit),
     top(G),
     timemax(TimeMax1,Sit),
     TimeMax is TimeMax1*3,
     travel(T,0,TimeMax,0,[0],G,Sit,0),
     findall(T1,travel(T1,0,T,0,[0],G,Sit,0),L),min1(L,Min),print(L).

timemax(0,[]).
timemax(Time1,[elevator(_,_,B,T)|EL]):-
     timemax(Time,EL),
     Time1 is Time+(T-B).



min1([H|T],Min) :- min1(T,H,Min).

min1([],Min,Min).
min1([H|T],Acc,Min) :- H < Acc, min1(T,H,Min).
min1([H|T],Acc,Min) :- H >= Acc, min1(T,Acc,Min).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Loesung 3: with retract/assert

% main predicate

traveltime(T):-
     retractall(elevator/5),
     initialize,
     top(G),
     travel(T,0,[],G).


% working horse
% travel(time needed,actual floor,history, goal floor)

% goal is reached
travel(0,G,H,G):- print_hist([G|H]),!.

% traveller is at bottom position of some elevator
travel(N,F,V,G):-
     elevator(_,F,_,F,T),
     not(member(T,V)),  % avoid to travel in loops
     Dist is T-F,     % Dist time in the elevator
     elevators(NE),
     update(NE,Dist),
     travel(N1,T,[F|V],G),
     N is N1+Dist.

% traveller is at top position of some elevator
travel(N,F,V,G):-
     elevator(_,F,_,B,F),
     not(member(B,V)),
     Dist is F-B,
     elevators(NE),
     update(NE,Dist),
     travel(N1,B,[F|V],G),
     N is N1+Dist.

% traveller waits

travel(N,F,V,G):-
     elevators(NE),
     update(NE,1),
     travel(N1,F,V,G),
     N is N1+1.


% assert for each elevator its situation
% elevator/5
% elevator(Number, Actual Floor, Actual Direction [-1 or 1], Bottom Floor,  Top Floor)
initialize:-
     elevator(N,B,T),
     assert(elevator(N,B,1,B,T)),
     fail.

initialize.


% update/2: updates the elevator knowledge base (iterates over time steps)
% update(total number of elevators,update time)
update(_,0):-!.

update(N,T):-
     update(N),
     T1 is T-1,
     update(N,T1).

% update/1: updates  elevators (iterates over elevators)
update(0):-!.
update(N):-
     update_elev(N),
     N1 is N-1,
     update(N1).

% update_elev(N): updates elevator N by one step
% elevator is neither in top nor bottom position
update_elev(N):-
     elevator(N,C,D,B,T),
     C1 is C+D,
     C1 =\=T,
     C1 =\=B,
     retract(elevator(N,C,D,B,T)),
     assert(elevator(N,C1,D,B,T)).

% elevator is either in top or bottom position
update_elev(N):-
     elevator(N,C,D,B,T),
     C1 is C+D,
     (C1 ==T; C1==B),
     D1 is D * (-1),
     retract(elevator(N,C,D,B,T)),
     assert(elevator(N,C1,D1,B,T)).



% auxiliary predicate to print current elevator knowledge base
print_sit:-
     elevator(N,C,D,B,T),
     write(elevator(N,C,D,B,T)), nl,
     fail.

print_sit.


print_hist(H):-
     reverse(H,HR),
     hist(HR).

hist([_]):- write('you have reached your goal'),nl.
hist([B,T|H]):-
     (elevator(N,B,T);elevator(N,T,B)),
     write('take elevator '),write(N),write(' from floor '),write(B),write(' to floor '),write(T),nl,
     hist([T|H]).
     
     
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Loesung 4


     min_path(T) :-
    setof(T1, path(0,0,[0],T1), Ts),
    minimum(Ts,T).

% path(vergangene Zeit, aktuelle Etage, besuchte Etagen, Rueckgabe Zeit)
path(_,St,_,0) :-
    top(St).

path(Tic,St,Visited,T) :-
    elevator(No,St,Ex),
    \+ member(Ex,Visited),
    T1 is Ex-St,
    timetilldown(No,Tic,WT),
    Tic1 is Tic+T1+WT,
    path(Tic1,Ex,[Ex|Visited],T2),
    T is T1+WT+T2.

path(Tic,St,Visited,T) :-
    elevator(No,Ex,St),
    \+ member(Ex,Visited),
    T1 is St-Ex,
    timetillup(No,Tic,WT),
    Tic1 is Tic+T1+WT,
    path(Tic1,Ex,[Ex|Visited],T2),
    T is T1+WT+T2.

timetilldown(No,Tic,T) :-
    elevator(No,St,Ex),
    Period is 2*(Ex-St),
    T is (-Tic mod Period).
timetillup(No,Tic,T) :-
    elevator(No,St,Ex),
    HalfPeriod is Ex-St,
    Period is 2*HalfPeriod,
    T is (-(Tic+HalfPeriod) mod Period).

minimum(L,X) :-
    member(X,L),
    maplist(=<(X), L), !.
