/*
  http://www.cs.kuleuven.be/~dtai/events/ASP-competition/Benchmarks/GolombRuler.shtml
  Program taken from PRACTICAL CONSTRAINTS: A TUTORIAL ON MODELLING WITH CONSTRAINTS,
  by ROMAN BARTÁK
*/
:-include(base).
:-include(lib_bp).
solve(As):-
    get_largest_atom(As,mark(M)),
    get_largest_atom(As,position(P)),
    Sol = [0|_],
    ruler(M,-1,P,Sol),
    last(Sol,XM),
    distances(Sol,1,M,XM,Dist),
    all_different(Dist),
    (Dist=[DF,_|_] ->
     last(Dist,DL), DF#<DL
     ;
     true
     ),
    minof(labeling(Sol),XM,output(Sol,XM)),!,  % defined in base.pl
    format("OPTIMUM FOUND").
solve(_):-
    format("UNSATISFIABLE~n").
    
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).

last([X],X):-!.
last([_|Xs],X):-last(Xs,X).

output(Sol,XM):-
    output_positions(Sol,1),
    format("Optimization: ~w~n",[XM]).

output_positions([],_).
output_positions([P|Ps],M):-
    format("location(~w,~w) ",[M,P]),
    M1 is M+1,
    output_positions(Ps,M1).

test:-
    solve([mark(1),mark(2),mark(3),mark(4),mark(5),mark(6),mark(7),mark(8),
	   position(0),position(1),position(2),position(3),position(4),position(5),position(6),position(7),position(8),position(9),position(10),position(11),position(12),position(13),position(14),position(15),position(16),position(17),position(18),position(19),position(20),position(21),position(22),position(23),position(24),position(25),position(26),position(27),position(28),position(29),position(30),position(31),position(32),position(33),position(34),position(35),position(36),position(37),position(38),position(39),position(40)]).