/*********************************************************** coins.pi from Constraint Solving and Planning with Picat, Springer by Neng-Fa Zhou, Hakan Kjellerstrand, and Jonathan Fruhman ***********************************************************/ import cp. main ?=> member(N,[12,20,30,40,50,60,70]), statistics(runtime,_), once minW(N,M), statistics(runtime,[_,Time]), writeln((N,M,Time)), fail. main => true. minW(N,M) => initialize_table, between(1,N,M), coin({N,0,0,0,M},_). table(+,-) coin({0,0,0,_,_},Plan) => Plan=nil. coin({0,1,0,_,_},Plan) => Plan=nil. coin({0,0,1,_,_},Plan) => Plan=nil. coin(State@{NU,NPH,NPL,NG,NW},Plan),NW>0 => Plan = \$weigh(State, {NU1,NPH1,NPL1,NG1}, {NU2,NPH2,NPL2,NG2},Plan1,Plan2,Plan3), [NU1,NU2] :: 0..NU, [NPH1,NPH2] :: 0..NPH, [NPL1,NPL2] :: 0..NPL, [NG1,NG2] :: 0..NG, NU1+NU2 #=< NU, NPH1+NPH2 #=< NPH, NPL1+NPL2 #=< NPL, NG1+NG2 #=< NG, LSide #= NU1+NPH1+NPL1+NG1, RSide #= NU2+NPH2+NPL2+NG2, lex_le([NU1,NPH1,NPL1,NG1],[NU2,NPH2,NPL2,NG2]), LSide #> 0, RSide #> 0, LSide #= RSide, % equal number of coins on both sides NW1 = NW-1, solve([NU1,NU2,NPH1,NPH2,NPL1,NPL2,NG1,NG2]), O1 = {NU-NU1-NU2, % Outcome1: both sides are equal NPH-NPH1-NPH2, NPL-NPL1-NPL2, NG+NU1+NPH1+NPL1+NU2+NPH2+NPL2, NW1}, coin(O1,Plan1), O2 = {0, % Outcome2: left side is heavier NPH1+NU1, NPL2+NU2, NG+(NPH-NPH1)+(NPL-NPL2)+(NU-NU1-NU2), NW1}, coin(O2,Plan2), O3 = {0, % Outcome3: left side is lighter NPH2+NU2, NPL1+NU1, NG+(NPH-NPH2)+(NPL-NPL1)+(NU-NU1-NU2), NW1}, coin(O3,Plan3).