/* 

  Cookie Monster Problem in Picat.

  Richard Green
  "The Cookie Monster Problem"
  https://plus.google.com/u/0/101584889282878921052/posts/8qWvSaLJVGD
  """
  Suppose that we have a number of cookie jars, each containing a certain number of cookies. 
  The Cookie Monster wants to eat all the cookies, but he is required to do so in a number 
  of sequential moves. At each move, the Cookie Monster (CM) chooses a subset of the jars, 
  and eats the same (nonzero) number of cookies from each jar. The goal of the CM is to 
  empty all the cookies from the jars in the smallest possible number of moves, and the 
  Cookie Monster Problem is to determine this number for any given set of cookie jars.
  
  Since the CM has an unlimited appetite, there is essentially no difference between eating 
  three cookies from one jar, and eating three cookies from each of 10 jars. It turns out 
  that there is no advantage to depleting these 10 jars at different rates, so the 10 jars 
  may as well be one jar, and we may as well reduce to the case where no two jars contain 
  the same number of cookies. It is also safe to ignore any empty jars. This means that the 
  starting state of the problem may be described by a set of positive integers, S. 
  The Cookie Monster Number of S, CM(S), is the smallest number of moves in which this set 
  of jars can be completely emptied.

  Let's look at an example. Suppose that S is the set {15, 13, 12, 4, 2, 1}, meaning that there 
  are six jars, containing 1, 2, 4, 12, 13 and 15 cookies each. Here are three possible 
  strategies open to the CM.

  ...
  
  The recent paper http://arxiv.org/abs/1304.7508 by Megan Belzner gives a good introduction 
  to the Cookie Monster Problem. The paper looks at some special cases of the problem, 
  including the case where the set S has size 3. In this case, it takes three moves to 
  empty S, unless the sum of the cookies in two of the jars equals the number in the 
  third, in which case it only takes two moves. Some other cases examined in the paper 
  are arithmetic progressions (which sometimes achieve the lower bound), geometric 
  progressions (which sometimes achieve the upper bound) and the Fibonacci sequence 
  (which can be emptied in a number of moves roughly equal to half the number of jars). 
  The problem can also be altered to form a two-player game, similar to the game of Nim, 
  and the author discusses this to some extent.
  """

  This is a simple model usings the planner module.

  Compare with the faster constraint model in http://hakank.org/picat/cookie_monster_problem.pi .


  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import planner.


main => go.

go ?=>
  data(2,Jars,MaxMoves),
  run(Jars,MaxMoves),
  nl.

go => true.


run(Jars,MaxMoves) =>
  println(jars=Jars),
  println(maxMoves=MaxMoves),
  best_plan(Jars,MaxMoves,Plan,Cost),
  println(cost=Cost),
  foreach(P in Plan)
    println(P)
  end,
 
  nl.


final(Final) =>
  Final = [0 : _I in 1..Final.len].


% move for player Player
action(From, To, Move, Cost) ?=>
  L = 1..max(From),
  member(Num,L.reverse),
  % between(1,max(From),Num),
  New = [cond(From[I] >= Num, From[I]-Num, From[I]) : I in 1..From.len],
  To = New,
  Move = [takes,Num,New],
  Cost = 1.



%
% data
%


%
% Original problem (see above).
%
data(1,Jars,MaxMoves) =>
  Jars = [15, 13, 12, 4, 2, 1],
  MaxMoves = 5.


%
% Megan Belzner: "Emptying Sets: The Cookie Monster Problem"
% From http://arxiv.org/abs/1304.7508
% page 1
% """
% The initial formulation presents a set of n = 15 cookie jars with i cookies in 
% the ith jar. 
% """
% There is just one optimal solution to this problem: 4 steps [8,4,2,1]
%
data(2,Jars,MaxMoves) =>
  N = 15,
  Jars = [I : I in 1..N],
  MaxMoves = N+1.


data(3,Jars,MaxMoves) =>
  N = 30,
  Jars = [I : I in 1..N],
  MaxMoves = N+1.

%
% Reverse version of #3
% 30..1 is faster than 1..30
%
data(4,Jars,MaxMoves) =>
  N = 30,
  Jars = [I : I in 1..N].reverse,
  MaxMoves = N+1.

%
% Harder problem.
%
data(5,Jars,MaxMoves) =>
  Jars = [100,86,59,58,56,52,48,47,41,30,27,24,23,18,17,16,14,9,3,1],
  MaxMoves = Jars.len+1.


%
% Even harder
%
data(6,Jars,MaxMoves) => 
  Jars = [989,965,947,899,898,855,804,796,758,745,729,719,672,625,588,573,558,537,536,535,504,502,500,493,473,404,381,363,264,254,240,232,212,180,142,94,14,9,7,4],
  MaxMoves = Jars.len+1.