:- use_module(contestlib,[for/3]).

trip(EarliestStart,LatestStart,LatestEnd,Begin,End,Trip) :-
	setof(Arrival-Trip,
	      good_trip(EarliestStart,LatestStart,LatestEnd,
			Begin,End,Trip,Arrival),
	      [_ - Trip|_]).

good_trip(EarliestStart,LatestStart,LatestEnd,
	  Begin,End,trip(Start,Path),Arrival) :-
	for(Start,EarliestStart,LatestStart),
	Start =< LatestEnd,
	any_trip(nowait,Start,LatestEnd,Begin,End,Path,Arrival),
	\+((Path = [Gate|Gates],
	    tripevent(Gates,Gate,Start,Event),
	    fixed_trip(FixedStart,[FixedGate|FixedRestGates]),
	    tripevent(FixedRestGates,FixedGate,FixedStart,Event))).

tripevent([wait(N)|RGs],Gate,Start,Event) :- !,
	NewStart is Start + N,
	tripevent(RGs,Gate,NewStart,Event).
tripevent([_|_],Gate,Start,departure(Start,Gate)).
tripevent([G|_],   _,Start,arrival(Start,G)).
tripevent([G|RGs], _,Start,Event) :-
	NewStart is Start + 1,
	tripevent(RGs,G,NewStart,Event).

any_trip(   _, Start,        _,Begin,Begin,[Begin],Start).
any_trip(wait, Start,LatestEnd,Begin,End,[wait(Wait)|R],Arrival) :-
	N is LatestEnd - Start,
	for(Wait,1,N),
	NewStart is Start + Wait,
	NewStart =< LatestEnd,
	any_trip(nowait,NewStart,LatestEnd,Begin,End,R,Arrival).
any_trip(   _, Start,LatestEnd,Begin,End,[Begin|R],Arrival) :-
	connection(Begin,NewBegin),
	NewStart is Start + 1,
	NewStart =< LatestEnd,
	any_trip(wait,NewStart,LatestEnd,NewBegin,End,R,Arrival).