:-use_module(library(clpfd)).
:-use_module(library(lists)).	% some list operations used for Golomb
:-use_module(library(system)).  % to measure time

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% SEASAW problem
seesaw(Sol):-
	Sol = [A,B,C],
	
	domain([A,B,C],-5,5),
	36*A+32*B+16*C #= 0,
	A #=< 0,
	abs(A-B) #> 2,
	abs(A-C) #> 2,
	abs(B-C) #> 2,
	
	labeling([ff],Sol).


seesaw2(Sol):-
	Sol = [A,B,C],
	
	domain([A,B,C],-5,5),
	A #=< 0,
	36*A+32*B+16*C #= 0,
	serialized([A,B,C],[3,3,3],[bounds_only(false)]),
	
	labeling([ff],Sol).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% ASSIGNMENT problem
assignment_p(Sol):-
	Sol = [W1,W2,W3,W4],
	
	domain(Sol,1,4),
	all_different(Sol),
	element(W1,[7,1,3,4],EW1),
	element(W2,[8,2,5,1],EW2),
	element(W3,[4,3,7,2],EW3),
	element(W4,[3,1,6,3],EW4),
	EW1+EW2+EW3+EW4 #>= 19,

	labeling([ff],Sol).

%	EW1+EW2+EW3+EW4 #= E,
%	maximize(labeling([ff],Sol),E).

assignment_dual(Sol):-
	Sol = [P1,P2,P3,P4],
	
	domain(Sol,1,4),
	all_different(Sol),
	element(P1,[7,8,4,3],EP1),
	element(P2,[1,2,3,1],EP2),
	element(P3,[3,5,7,6],EP3),
	element(P4,[4,1,2,3],EP4),
	EP1+EP2+EP3+EP4 #>= 19,

	labeling([ff],Sol).

assignment_combined(Workers,Products):-
	Workers= [W1,W2,W3,W4],
	
	domain(Workers,1,4),
	all_different(Workers),
	element(W1,[7,1,3,4],EW1),
	element(W2,[8,2,5,1],EW2),
	element(W3,[4,3,7,2],EW3),
	element(W4,[3,1,6,3],EW4),
	EW1+EW2+EW3+EW4 #>= 19,

	Products = [P1,P2,P3,P4],
	
	domain(Products,1,4),
	all_different(Products),
	element(P1,[7,8,4,3],EP1),
	element(P2,[1,2,3,1],EP2),
	element(P3,[3,5,7,6],EP3),
	element(P4,[4,1,2,3],EP4),
	EP1+EP2+EP3+EP4 #>= 19,

	assignment(Workers,Products),

	labeling([ff],Workers).

%	EW1+EW2+EW3+EW4 #= E,
%	maximize(labeling([ff],Sol),E).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% GOLOMB RULER  problem
golomb(I):-
	statistics(runtime,_),
	golomb(I,Sol),
	statistics(runtime,[_,Time]),
	write(I-Time-Sol),nl, % write size-runtime-solution
	I1 is I+1,!,
	golomb(I1).
	

golomb(M,Sol):-
	Sol = [0|_],
	UpperBound is M*M,
	ruler(M,-1,UpperBound,Sol),
	last(Sol,XM),
	distances(Sol,1,M,XM,Dist),
	all_distinct(Dist),

	(Dist=[_,_|_] ->
	    Dist=[DF|_], last(Dist,DL), DF#<DL
	;
	    true
	),

%	minimize(labeling([leftmost,enum],Sol),XM).
%	minimize(labeling([leftmost,step],Sol),XM).
	minimize(labeling([leftmost,bisect],Sol),XM).
%	minimize(labeling([ff,enum],Sol),XM).
%	minimize(labeling([ff,step],Sol),XM).
%	minimize(labeling([ff,bisect],Sol),XM).

ruler(0,_,_,[]).
ruler(K,PrevX,UpperBound,[X|Rest]):-
	K>0,
	PrevX#<X, X#=<UpperBound,
	K1 is K-1,!,
	ruler(K1,X,UpperBound,Rest).

distances([],_,_,_,[]).
distances([X|Rest],I,M,XM,Dist):-
	J is I+1,
	distances_from_x(Rest,X,I,J,M,XM,Dist,RestDist),
	I1 is I+1,!,
	distances(Rest,I1,M,XM,RestDist).

distances_from_x([],_,_,_,_,_,RestDist,RestDist).
distances_from_x([Y|Rest],X,I,J,M,XM,[DXY|Dist],RestDist):-
	DXY #= Y-X,
	LowerBound is integer(((J-I)*(J-I+1))/2),
	LowerBound #=< DXY,
	UpperBoundP is integer(((M-1-J+I)*(M-J+I))/2),
	DXY #=< XM - UpperBoundP,
	J1 is J+1,!,
	distances_from_x(Rest,X,I,J1,M,XM,Dist,RestDist).
