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

:-include(base).
:-include(lib_bp).

:-dynamic controller/1,toBeControlled/1,onSale/4.

solve(As):-
    assert_facts(As), % assert all facts (built-in in B-Prolog)
    findall(C,company(C),Cs),
    make_control_table(Cs,Cs,ControlTable,ControlVars),
    ensure_controlled(ControlTable),
    make_purchase_table(Cs,PurchaseTable,PurchaseVars,TotalCost),
    sum_shares(Cs,Cs,ControlTable,PurchaseTable),
    append(PurchaseVars,ControlVars,AllVars),
    minof(labeling([ffc],AllVars),TotalCost,output(PurchaseTable)),!,
    format("OPTIMUM FOUND"),
    abolish_all.
solve(_):-
    format("UNSATISFIABLE~n").

% for each two companies C1 and C2 (C1 and C2 can be the same), add
%   c(C1,C2,Control,OwnTotal)
% into the table where Control=1 iff OwnTotal>50.
make_control_table([],_,ControlTable,[]):-closetail(ControlTable).
make_control_table([C|Cs],AllCs,ControlTable,ControlVars):-
    make_control_table(C,AllCs,ControlTable,ControlVars,ControlVarsR),
    make_control_table(Cs,AllCs,ControlTable,ControlVarsR).

make_control_table(_,[],_,ControlVars,ControlVars).
make_control_table(C1,[C2|Cs],ControlTable,[Control|ControlVars],ControlVarsR):-
    member(c(C1,C2,Control,OwnTotal),ControlTable),!,
    Control :: 0..1,
    Control #<=> OwnTotal#>50,
    make_control_table(C1,Cs,ControlTable,ControlVars,ControlVarsR).
    
% for each company C1 and each package onSale(P,C2), add the following entry into the table
%    p(C1,C2,P,Share,Purchase)
% where Purchase (0 or 1) indicates whether C1 purchases this package
make_purchase_table(Cs,PurchaseTable,PurchaseVars,TotalCost):-
    findall(onSale(P,Company,Share,Cost),onSale(P,Company,Share,Cost),Packages),
    make_purchase_table(Packages,Cs,PurchaseTable,PurchaseVars,TotalCost).

make_purchase_table([],_,PurchaseTable,[],0):-closetail(PurchaseTable).
make_purchase_table([Package|Packages],Cs,PurchaseTable,PurchaseVars,TotalCost1+TotalCost2):-
    make_purchase_table_aux(Package,Cs,PurchaseTable,PurchaseVars1,TotalCost1),
    sum(PurchaseVars1) #=< 1,  % each package has only one buyer
    make_purchase_table(Packages,Cs,PurchaseTable,PurchaseVars2,TotalCost2),
    append(PurchaseVars1,PurchaseVars2,PurchaseVars).

make_purchase_table_aux(_,[],_,[],0).
make_purchase_table_aux(Package,[C1|Cs],PurchaseTable,[Purchase|PurchaseVars],Purchase*Cost+TotalCost):-
    Package=onSale(P,C2,Share,Cost),
    member(p(C1,C2,P,Share,Purchase),PurchaseTable),!,
    Purchase :: 0..1,
    make_purchase_table_aux(Package,Cs,PurchaseTable,PurchaseVars,TotalCost).

% for each pair of companies (C1,C2), compute the total share C1 owns in C2
sum_shares([],_,_,_).
sum_shares([C|Cs],AllCs,ControlTable,PurchaseTable):-
    sum_shares(C,AllCs,AllCs,ControlTable,PurchaseTable),
    sum_shares(Cs,AllCs,ControlTable,PurchaseTable).

sum_shares(_,[],_,_,_).
sum_shares(C1,[C2|Cs],AllCs,ControlTable,PurchaseTable):-
    member(c(C1,C2,_,OwnTotal12),ControlTable),!,
    (owns(C1,C2,S0)->true;S0=0),  % directly owns
    purchased_share(C1,C2,PurchaseTable,S1),
    sum_shares(C1,C2,AllCs,ControlTable,S0+S1,S),
    OwnTotal12 #= S,
    sum_shares(C1,Cs,AllCs,ControlTable,PurchaseTable).

purchased_share(_,_,[],0).
purchased_share(C1,C2,[p(C1,C2,_,S12,Purchase12)|Table],S):-!,
    S=Purchase12*S12+SRest,
    purchased_share(C1,C2,Table,SRest).
purchased_share(C1,C2,[_|Table],S):-
    purchased_share(C1,C2,Table,S).

sum_shares(_,_,[],_,S,S).
sum_shares(C1,C2,[C3|Cs],ControlTable,S0,S):-
    C3\==C1,
    member(c(C1,C3,Control13,_),ControlTable),!, % indirectly owns
    (owns(C3,C2,S32)->true;S32=0),
    sum_shares(C1,C2,Cs,ControlTable,S0+Control13*S32,S).
sum_shares(C1,C2,[_|Cs],ControlTable,S0,S):-     
    sum_shares(C1,C2,Cs,ControlTable,S0,S).

% ensure that B is controlled by at least one company in As
ensure_controlled(ControlTable):-
    findall(Controller,controller(Controller),Controllers),
    toBeControlled(Controlled),!,
    ensure_controlled(Controllers,Controlled,ControlTable,0).
ensure_controlled(_).

ensure_controlled([],_,_,Sum):-Sum#>=1.
ensure_controlled([A|As],B,ControlTable,Sum):-
    member(c(A,B,Control,_),ControlTable),!,
    ensure_controlled(As,B,ControlTable,Control+Sum).

output([]):-nl.
output([p(C1,C2,P,S,Purchase)|L]):-
   (Purchase==1->
     onSale(P,C2,S,Cost),
     format("buy(~w,~w,~w,~w,~w). ",[C1,P,C2,S,Cost]);
    true),
    output(L).

test:-
    solve([company(c1),company(c2),company(c3),company(c4),owns(c1,c2,30),owns(c1,c3,20),owns(c1,c4,20),owns(c2,c3,45),owns(c3,c4,40),onSale(p1,c2,30,900),onSale(p2,c3,10,550),onSale(p3,c4,15,550),controller(c1),controller(c2),toBeControlled(c4)]).
%    solve([company(c3),company(c1),company(c2),company(c4),owns(c1,c2,30),owns(c1,c3,20),owns(c1,c4,20),owns(c2,c3,45),owns(c3,c4,40),onSale(p1,c2,30,900),onSale(p2,c3,10,550),onSale(p3,c4,15,550),controller(c1),controller(c2),toBeControlled(c4)]).