:- lib(fd_global).

:- local struct(post(r,m,e,j,k)).

go(NWeeks) :-

	
	NDays = 7,
	NLabels = 5,

	
	data(NWeeks, Data),

	
	dim(Roster, [NWeeks,NDays]),		
	Rows is Roster[1..NWeeks,1..NDays],
	flatten(Rows, Vars),			
	length(Vars, NVars),
	Vars :: 1..NLabels,			

	
	( for(Label,1,NLabels), param(Data,Roster,NDays,NWeeks) do
	    ( for(Day, 1, NDays), param(Data,Roster,Label,NWeeks) do
		Required is Data[Label,Day],
		Days is Roster[1..NWeeks,Day],
		occurrences(Label, Days, Required)
	    )
	),

	
	
	append(Vars, Vars, VarsWithOverlap),

	
	(
	    for(I,1,NVars),
	    fromto(VarsWithOverlap, RestVars, RestVars1, _),
	    fromto(AllViolations, [Viol1,Viol2|Violations], Violations, [])

	do
	    RestVars = [_|RestVars1],

	    
	    first_n(7, RestVars, Consec7),
	    occurrences(r of post, Consec7, DaysOffIn7),
	    DaysOffIn7 :: 1..6,

	    
	    first_n(4, RestVars, Consec4),
	    occurrences(r of post, Consec4, DaysOffIn4),
	    DaysOffIn4 :: 0..3,

	    
	    RestVars = [SomeDay,NextDay|_],
	    Viol1  isd  SomeDay #= e of post  #/\  NextDay #= m of post,

	    
	    RestVars = [Before,Off,After|_],
	    Viol2  isd  Off #= r of post
	    	#/\ Before #\= r of post
		#/\  After #\= r of post
	),
	Cost #= sum(AllViolations),

	
	min_max((
	    Cost=0,bouygues_labeling(NDays, NWeeks, Data, Roster),
	    labeling_ff(Vars)
	    ),
	    Cost),

	
	print_roster(Roster).


    print_roster(Roster) :- 
	dim(Roster, [NWeeks,NDays]),
	( for(Week,1,NWeeks), param(Roster,NDays) do
	    ( for(Day, 1, NDays), param(Roster,Week) do
		Table = post with [r:'R',m:'M',e:'E',j:'J',k:'K'],
		Symbol is Table[Roster[Week,Day]],
		printf(" %w ", [Symbol])
	    ), nl
	), nl.




    bouygues_labeling(NDays, NWeeks, Data, Roster) :-
	
	(
	    for(Day, 1, NDays), param(Data,Roster,NWeeks),
	    foreach(OffInColumn, OffInColumns)
	do
	    ColDays is Roster[1..NWeeks,Day],
	    occurrences(r of post, ColDays, OffInColumn)
	),
	place_days_off(NDays, NWeeks, Data, Roster, OffInColumns).

    place_days_off(NDays, NWeeks, Data, Roster, OffInColumns) :-
    	( best_column(OffInColumns, Data, NDays, BestWD) ->
	    place_day_off(NDays, NWeeks, Data, Roster, OffInColumns, BestWD)
	;
	    true
	).

    place_day_off(NDays, NWeeks, Data, Roster, OffInColumns, BestWD) :-
	best_week(NDays, NWeeks, Roster, BestWD, BestW), 

	(
	    Roster[BestW,BestWD] #= r of post,
	    place_days_off(NDays, NWeeks, Data, Roster, OffInColumns)
	;
	    Roster[BestW,BestWD] #\= r of post,
	    place_day_off(NDays, NWeeks, Data, Roster, OffInColumns, BestWD)
	).

    
    best_column(OffInColumns, Data, NDays, BestWD) :-
    	(
	    for(Day, 1, NDays),
	    foreach(OffInColumn, OffInColumns),
	    fromto(2, MaxReq0,  MaxReq1,  _),
	    fromto(_, BestWD0, BestWD1, BestWD),
	    param(Data)
	do
	    Req is Data[r of post, Day] - mindomain(OffInColumn),
	    ( Req >= MaxReq0 ->
	    	MaxReq1 = Req, BestWD1 = Day
	    ;
	    	MaxReq1 = MaxReq0, BestWD1 = BestWD0
	    )
	),
	nonvar(BestWD).	

    
    best_week(NDays, NWeeks, Roster, BestWD, BestW) :-
    	(
	    for(I,1,NWeeks),
	    fromto(_,     BestW0,     BestW1,     BestW),
	    fromto(10000, MinAssign0, MinAssign1, _),
	    param(NDays,Roster,BestWD)
	do
	    Candidate is Roster[I,BestWD],
	    ( 
		var(Candidate),
		dvar_domain(Candidate, Dom),
		dom_check_in(r of post, Dom)
	    ->
		( 
		    for(J,1,NDays),
		    fromto(0, NAssign0, NAssign1, NAssign),
		    param(Roster,I)
		do
		    D is Roster[I,J],
		    ( D == r of post ->
		    	NAssign1 is NAssign0+1
		    ;
		    	NAssign1 = NAssign0
		    )
		),
		( NAssign < MinAssign0 ->
		    BestW1 = I, MinAssign1 = NAssign
		;
		    BestW1 = BestW0, MinAssign1 = MinAssign0
		)
	    ;
	    	BestW1 = BestW0, MinAssign1 = MinAssign0
	    )
	),
	nonvar(BestW).	
 




    
    first_n(N, List, FirstN) :-
    	length(FirstN, N),
	append(FirstN, _, List).


    
    labeling_ff(AllVars) :-
    	( fromto(AllVars, Vars, Rest, []) do
	    deleteff(X, Vars, Rest),
	    indomain(X)
	).



    	
data(12, post with [
	    r: week(4,6,5,6,6,6,6),	
	    m: week(3,2,2,3,2,4,2),	
	    e: week(4,2,2,1,1,0,1),	
	    j: week(0,1,1,0,1,0,1),	
	    k: week(1,1,2,2,2,2,2)	
	]).
data(24, post with [
	    r: week(8,9,5,7,9,8,3),	
	    m: week(4,3,4,3,2,0,3),	
	    e: week(6,5,8,7,5,7,5),	
	    j: week(2,3,2,3,4,5,8),	
	    k: week(4,4,5,4,4,4,5)	
        ]).