% weightAssign.pi for Picat % https://www.mat.unical.it/aspcomp2013/WeightedSequenceProblem % Neng-Fa Zhou, March, 2013 % translated to Picat on 23 August, 2013 import cp. asp(As), once(member(\$num(N),As)), LeafWeightVect = new_array(N), LeafWeightVect.to_list() = LeafWeightLst, LeafCardVect = new_array(N), LeafCardVect.to_list() = LeafCardLst, fill_weight_card(As,LeafWeightVect,LeafCardVect,MaxW), % PosLeafVect = new_array(N), PosLeafVect.to_list() = PosLeafLst, PosLeafLst :: 1..N, all_different(PosLeafLst), % PosColorVect = new_array(N), PosColorVect.to_list() = PosColorLst, PosColorLst :: 0..2, % 0: green; 1: red; 2: blue % PosCostVect = new_array(N), PosCostVect.to_list() = PosCostLst, PosCostLst :: 0..MaxW, PosCostLst=[_|Costs], sum(Costs) #=< MaxW, % foreach(I in 1..N) computeCost(I,LeafWeightLst,LeafCardLst,PosLeafVect,PosColorVect,PosCostVect) end, % solve(PosLeafLst), solve(PosColorLst) => println('ANSWER'), write('exists. '), output(PosColorLst,PosLeafLst,0). asp(_) => println('INCONSISTENT'). fill_weight_card([],_LeafWeightVect,_LeafCardVect,_MaxW) => true. fill_weight_card([leafWeightCardinality(I,W,C)|As],LeafWeightVect,LeafCardVect,MaxW) => LeafWeightVect[I] = W, LeafCardVect[I] = C, fill_weight_card(As,LeafWeightVect,LeafCardVect,MaxW). fill_weight_card([max_total_weight(W)|As],LeafWeightVect,LeafCardVect,MaxW) => MaxW=W, fill_weight_card(As,LeafWeightVect,LeafCardVect,MaxW). fill_weight_card([_|As],LeafWeightVect,LeafCardVect,MaxW) => fill_weight_card(As,LeafWeightVect,LeafCardVect,MaxW). computeCost(1,LeafWeightLst,_LeafCardLst,PosLeafVect,_PosColorVect,PosCostVect) => element(PosLeafVect[1],LeafWeightLst,PosCostVect[1]). computeCost(I,LeafWeightLst,LeafCardLst,PosLeafVect,PosColorVect,PosCostVect) => I1 = I-1, PosColorVect[I] = Color, PosCostVect[I] = Cost, PosCostVect[I1] = Cost1, Leafi = PosLeafVect[I], element(Leafi,LeafWeightLst,Wi), element(Leafi,LeafCardLst,Ci), Weight0 #= Wi+Ci, Weight1 #= Cost1+Wi, Weight2 #= Cost1+Ci, % Color#=0 #=> Cost#=Weight0, % green Color#=1 #=> Cost#=Weight1, % red Color#=2 #=> Cost#=Weight2, % blue Cost #>= min([Weight0,Weight1,Weight2]), Cost #=< max([Weight0,Weight1,Weight2]). output([],[Leaf],I) => I1 is I+1, write(\$leafPos(Leaf,I1)),writeln('.'). output([Color|Colors],[Leaf|Leaves],I) => I1 is I+1, (Color==0->SymColor=green;Color==1->SymColor=red;SymColor=blue), write(\$posColor(I1,SymColor)),write('. '), write(\$leafPos(Leaf,I)),write('. '), output(Colors,Leaves,I1). test => asp(\$[leafWeightCardinality(1,45,44), leafWeightCardinality(2,21,3), leafWeightCardinality(3,64,74), leafWeightCardinality(4,29,91), leafWeightCardinality(5,80,48), leafWeightCardinality(6,91,8),leafWeightCardinality(7,10,64), leafWeightCardinality(8,62,79),innerNode(1), innerNode(2), innerNode(3), innerNode(4),innerNode(5), innerNode(6), innerNode(7),num(8), max_total_weight(495)]).