/*
The University of York
CONSTRAINT SATISFACTION AND COMBINATORIAL OPTIMISATION
Open Examination

http://www-course.cs.york.ac.uk/cop/exam2000.pdf


Each year the Department of Computer Science interviews potential undergraduate
students in a series of interview session on different dates. Each session must be taffed
by a number of interviewers, with possibly different numbers being required on different
dates. Before the interview series starts, each interviewer indicates which sessions, if 
any, he is unavailable for.  The department's admissions tutor must then decide which 
interviewers must serve at each interview session, ensuring that the required number of 
interviewers - and no more - serve at each session and that no interviewer is assigned
to a session for which he is unavailable.  Furthermore, each interviewer has a work limit and
cannot be assigned to serve on more sessions than his limit. 

Input:  Requirements list:  a list of positive integers specifying how man interviews are 
	required for each session.
	
	Resource list:  a list containing one element for each interviewer.  Each element is a 
	three-element list containing interviewers name, work limit, and a list of sessions
	for which he is unavailable. (Ex [ [white, 2, [1]], [black, 3 []]]).
*/

/*
Solutions by George Rabanca, Aug, 2007
*/

/*************************************************************************************************/

/*
First write a program that solves the problem for the special case when there are exactly three
interview sessions, exaclty four interviewers and each interviewer is available for every session.
*/

go1:-
    statistics(runtime,[Start|_]),
    top1,
    statistics(runtime,[End|_]),
    T is End-Start,
    write('execution time is '),write(T), write(milliseconds),nl.

top1:-
    interviews1([2,3,4], [ [white, 2, []], [black, 2, []], [red, 4, []], [green, 2, []] ]).
top1.


interviews1(Req, Resources):-
	Req = [Ra, Rb, Rc], 
	Resources = [Prof1, Prof2, Prof3, Prof4], 
	nth(2, Prof1, WorkLimit1),
	nth(2, Prof2, WorkLimit2),
	nth(2, Prof3, WorkLimit3),
	nth(2, Prof4, WorkLimit4),
	
	new_array(Schedule, [3,4]),
	array_to_list(Schedule, L), 
	L in [0..1],
	
	Schedule^[1,1] + Schedule^[1,2] + Schedule^[1,3] + Schedule^[1,4] #= Ra,
	Schedule^[2,1] + Schedule^[2,2] + Schedule^[2,3] + Schedule^[2,4] #= Rb,
	Schedule^[3,1] + Schedule^[3,2] + Schedule^[3,3] + Schedule^[3,4] #= Rc,
	
	Schedule^[1,1] + Schedule^[2,1] + Schedule^[3,1] #=< WorkLimit1,
	Schedule^[1,2] + Schedule^[2,2] + Schedule^[3,2] #=< WorkLimit2,
	Schedule^[1,3] + Schedule^[2,3] + Schedule^[3,3] #=< WorkLimit3,	
	Schedule^[1,4] + Schedule^[2,4] + Schedule^[3,4] #=< WorkLimit4,
	
	labeling(L), 
	writeln(Schedule).
		
	
/*
A general solution
*/	

go:-
    statistics(runtime,[Start|_]),
    top,
    statistics(runtime,[End|_]),
    T is End-Start,
    writeln(''),
    write('execution time is '),write(T), write(milliseconds),nl.

top:-
    interviews([3,3,4,4], [ [white, 3, [1]], [black, 3, []], [red, 4, []], [green, 5, []] ]).
top:-
    writeln('No Solution').


interviews(Req, Resources):-
	length(Req, N), 
	length(Resources, M), 
	
	new_array(Schedule, [N,M]),
	array_to_list(Schedule, L), 
	L in [0..1],
	
	Schedule^columns @= Professors,
	make_resources_constraints(Professors, Resources),
	Schedule^rows @= Sessions,
	make_requirements_constraints(Sessions, Req),
	
	labeling(L), 
	writeln(Schedule).	
	
%dinamically generates the constraints related to the available resources
make_resources_constraints([], []). 	
make_resources_constraints([P|Professors], [R|Resources]):- 
	sum(P,Sum), 
	nth(2, R, Limit),
	Sum #=< Limit,
	nth(3,R,Unavailable),
	set_unavailable(P, Unavailable),
	make_resources_constraints(Professors, Resources).
	
%dinamically generates the constraints related to the requirements
make_requirements_constraints([], []).
make_requirements_constraints([S|Sessions], [R|Requirements]):-
	sum(S,Sum),
	Sum #= R,	
	make_requirements_constraints(Sessions, Requirements).
	
%sets to 0 the dates for which professor is unavailable
set_unavailable(_, []).
set_unavailable(Professor, [U|Unavailable]):-
	element(U,Professor, 0),
	set_unavailable(Professor, Unavailable).
		
%Sum is the sum of all elements in L	
sum(L, Sum):- sum(L, Sum, 0). 
sum([], Sum, Sum). 
sum([X|Xs], Sum, Acc):-
	Acc1 #= Acc + X, 
	sum(Xs, Sum, Acc1).