% http://www.cs.kuleuven.be/~dtai/events/ASP-competition/Benchmarks/OptFastFood.shtml
% by Neng-Fa Zhou, April 11, 2009

:-include(lib_bp).

solve(As):-
    findall(RK,member(restaurant(_,RK),As),RKs), % restaurant distances
    (member(number_depots(M),As)->true;true),
    length(Vars,M),      % Vars=[V1,...,VM] Vi=d if the ith depot is built d away
    Vars :: RKs,
    ordered(Vars),       % V1=<V2=<...=<VM, break symmetry
    one_depot_a_restaurant(RKs,RKs,Vars),
    sum_supply_distances(RKs,Vars,0,Sum),
    minof(labeling([ff],Vars),Sum,output(Vars,As,[])),
    format("OPTIMUM FOUND").
solve(_):-
    format("UNSATISFIABLE~n").
    
sum_supply_distances([],_,Sum,Sum).
sum_supply_distances([RK|RKs],DKs,Sum0,Sum):-
    distances(RK,DKs,Distances),
    sum_supply_distances(RKs,DKs,min(Distances)+Sum0,Sum).

distances(_,[],[]).
distances(K,[K1|Ks],[abs(K-K1)|Distances]):-
    distances(K,Ks,Distances).

ordered([_]):-!.
ordered([X1,X2|Xs]):-X1#=<X2,ordered([X2|Xs]).
    
% if there are Len restaurants in the same distance K
% then the number of depots in the distance K cannot exceed Len
one_depot_a_restaurant([],_,_).
one_depot_a_restaurant([K|Ks],RKs,Vars):-
    findall(K,member(K,RKs),SameKs),
    length(SameKs,Len),
    count(K,Vars,#=<,Len),
    one_depot_a_restaurant(Ks,RKs,Vars).

output([],_,_):-nl.
output([K|Ks],As,Prev):-
    member(restaurant(Id,K),As),
    \+ member(restaurant(Id,K),Prev),!, % no two depots at one restaurant
    format("depot(~w,~w). ",[Id,K]),
    output(Ks,As,[restaurant(Id,K)|Prev]).

test:-
    solve([restaurant(r1,5),restaurant(r2,6),restaurant(r3,12),restaurant(r4,19),
	   restaurant(r5,20),restaurant(r6,27),number_depots(3)]).