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

solve(As):-
    findall(RK,member(restaurant(_,RK),As),RKs), % restaurant distances
    findall(DK,member(depot(_,DK),As),DKs),      % dipot distances
    sum_supply_distances(RKs,DKs,0,Sum0),
    length(DKs,M),       % M - number of depots
    length(Vars,M),      % Vars=[V1,...,VM] Vi=d if the ith depot is built d ki away
    Vars :: RKs,
    ordered(Vars),       % V1=<V2=<...=<VM, break symmetry
    one_depot_a_restaurant(RKs,RKs,Vars),
    sum_supply_distances(RKs,Vars,0,Sum1),
    Sum1 #< Sum0,
    labeling([ff],Vars),!,
    output(Vars,As,[]).
    
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([],_,_).
output([K|Ks],As,Prev):-
    member(restaurant(Id,K),As),
    \+ member(restaurant(Id,K),Prev),!, % no two depots at one restaurant
    format("altdepot(~w,~w). ",[Id,K]),
    output(Ks,As,[restaurant(Id,K)|Prev]).

test:-
	  solve([depot(hamburg_stillhorn_west,155),
		 depot(lichtendorf_nord,70),
		 depot(muensterland_west,276),
		 depot(ehrenberg_west,368),
		 restaurant(aarbachkate_sued,36),
		 restaurant(buddikate_ost,25),
		 restaurant(buddikate_west,25),
		 restaurant(dammer_berge_ost,194),
		 restaurant(dammer_berge_west,194),
		 restaurant(ehrenberg_west,368),
		 restaurant(eichengrund_west,296),
		 restaurant(eifel_ost,93),
		 restaurant(eifel_west,93),
		 restaurant(grundbergsee_nord,86),
		 restaurant(grundbergsee_sued,86),
		 restaurant(hamburg_stillhorn_ost,155),
		 restaurant(hamburg_stillhorn_west,155),
		 restaurant(hochwald_ost,148),
		 restaurant(hochwald_west,148),
		 restaurant(hollenstedt,36),
		 restaurant(im_mersch_ost,296),
		 restaurant(kucksiepen,367),
		 restaurant(lennhof_west,61),
		 restaurant(lichtendorf_nord,70),
		 restaurant(lichtendorf_sued,70),
		 restaurant(muensterland_ost,275),
		 restaurant(muensterland_west,276),
		 restaurant(neustaedter_bucht_ost,81),
		 restaurant(neustaedter_bucht_west,81),
		 restaurant(ostetal_nord,51),
		 restaurant(ostetal_sued,51),
		 restaurant(oyten_sued,97),
		 restaurant(remscheid_ost,381),
		 restaurant(remscheid_west,381),
		 restaurant(tecklenburger_land_ost,234),
		 restaurant(tecklenburger_land_west,234),
		 restaurant(trave,43),
		 restaurant(ville_ost,431),
		 restaurant(ville_west,431),
		 restaurant(wildeshausen_nord,142),
		 restaurant(wildeshausen_sued,144)]).