 /*
  *
  * rehearsal.pl:	Source prolog code solving "Scheduling Rehearsal Problem"
  * Implemented by: 	Psallidas Fotis
  * std code :		std06170
  * Project Reference:	Logic Programming Project 6.0
  *
  */

:- lib(fd).

players([[1,1,0,1,0,1,1,0,1],
	 [1,1,0,1,1,1,0,1,0],
	 [1,1,0,0,0,0,1,1,0],
	 [1,0,0,0,1,1,0,0,1],
	 [0,0,1,0,1,1,1,1,0]]
	).
durations([2,4,1,3,3,2,5,7,6]).

 /*
  *	Declare Variables ( generating rehearsal's parts order ).
  *	The solution set will give as the order of parts
  *	which should be played to minimize the cost.  
  */
variables(S,N):-
	length(S,N).

 /*
  *	Declare Domains:
  *	Each song can be played as Nth part of the rehearsal
  *	so its variable can take value from 1 to N.
  */
domains(S,N):-
	S :: 1..N.

 /*
  *	Basic Constraints:
  *	All variables must have different value.
  *	(Two or more parts cannot be played in the same time).
  *	Also the last part should be more bigger than the first part.
  */
constrain([SH | ST]):-
	fd_global:alldifferent([SH | ST]),
	append(_, [Last], ST),	
	SH #< Last.


 /*
  *	Make durations elemented.
  */
map_durations([],_,[]):- !.
map_durations([H | T],DL,[HD | TD]):-
	element(H,DL,HD),
	map_durations(T,DL,TD).

 /*
  *	Make players elemented
  */
map_player([],_,[]):- !.
map_player([H | T],PL,[HP | TP]):-
	element(H,PL,HP),
	map_player(T,PL,TP).

map_players(_,[],[]).	
map_players(S,[HP | TP],[HPL | TPL]):-
	map_player(S,HP,HPL),
	map_players(S,TP,TPL).


 /*
  *	For player i
  *	* Arrive list
  *		* if	j == 0 	: Arrive[i][0] = Player[i][0]
  *		* else (j != 0)	: Arrive[i][j] = (A[i][j-1] or P[i][j])
  *	* Left list
  *		Reverse P[i] making RH 
  *		*	if    j == 0 	:   RL[i][0] = RH[i][0] 
  *		*	else (j != 0)	:   RL[i][j] = (RL[i][j-1] or RH[i][j])	
  *		Left[i] = Reversed RL[i]
  *	Definition of Arrive and Left lists can be found in the given paper
  *		Constraint Programming in Practice:
  *			Scheduling a Rehearsal		 
  */
player_lst([],[],-1,_):-!.
player_lst([H | T],[LSH | LST],-1,ORD):-
	LSH isd H #\/ ORD,
	player_lst(T,LST,-1,LSH).
	

player_lst([],[],-2,_):-!.
player_lst([H | T],[H | LST],-2,_):-
	player_lst(T,LST,-1,H).

arrive([],[]):-!.
arrive([H | T],[HA | TA]):-
	player_lst(H,HA,-2,_),
	arrive(T,TA).

left([],[]):- !.
left([H | T],[HL | TL]):-
	reverse(H,RH),
	player_lst(RH,RHL,-2,_),
	reverse(RHL,HL),
	left(T,TL).

/*
 *	As far as Arrive and Left lists are declared we can also declare cost.
 *	For every player i we declare his cost for a part j as
 *	Cost[i][j] = [ (Arrive[i][j] or P[i][j]) and ( Left[i][j] or P[i][j] ) and ( P[i][j] == 0 ) ] * Dur[j]
 *	The sum up for all this costs (Sum(Cost)) is our final Cost which we want to minimize.
 *	Definition of Cost can be found in the given paper
 *		Constraint Programming in Practice:
 *			Scheduling a Rehearsal
 */
player_cost([],[],[],[],0):- !.
player_cost([PH | PT],[AH | AT],[LH | LT],[DH | DT],Cost):-
	player_cost(PT,AT,LT,DT,CURcost),
	ORD isd (AH #\/ PH)  #/\ (LH #\/ PH) #/\ (PH#=0),
	Cost #= ORD * DH + CURcost. 

cost([],[],[],_,0):- !.
cost([PLH | PLT],[AH | AT],[LH | LT],D,Cost):-
	cost(PLT,AT,LT,D,CURcost),
	player_cost(PLH,AH,LH,D,PLcost),
	Cost #= PLcost + CURcost.

/* 
 *	To further optimize csp
 *	We transform variables' list so that
 *	Solution_Vars[k] = Vars[i] and Solution_Vars[k+1] = Vars[Vars.size-1-i]
 *	Where Solution_Vars is the final variables' set.
 */
emo([],[]):- !.
emo([X],[X]):- !.
emo([H | T],[H,Y | R]):-
	append([H | Q],[Y],[H | T]),
	emo(Q,R).

generate([]).
generate([H | T]):-
	indomain(H),
	generate(T).

rehearsal(SS,Cost):-
	players(PL),
	durations(DUR),
	length(DUR,N),
	variables(SS,N),
	domains(SS,N),
	constrain(SS),
	map_durations(SS,DUR,D),
	map_players(SS,PL,P),
	arrive(P,A),
	left(P,L),
	cost(P,A,L,D,Cost),
	emo(SS,S),
	minimize(generate(S),Cost).
	

