/* 

  Coins problem (planning) in Picat.

  http://stackoverflow.com/questions/29780471/java-program-for-fastest-coin-move-combination
  """
  Starting with 138 coins find the least number of moves to reach exactly 0 coins. With each move 
  you can either 
     (a) discard 17 coins, 
     (b) discard 1 coins or 
     (c) discard half your coins (but only if you currently have an even number of coins). 

  Write a program that tests all possible combination of moves and prints the number of moves 
  required by the fastest move combination.
  """

  Note: This problem don't generate all possible combinations, instead it use the planner module...


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

*/


import util.
import planner.


main => go.

%
% 138 coins
%
go => 
  nolog,
  Plans = coins(138),
  foreach(Plan in Plans)
    println(Plan)
  end,
  nl.

%
% Which N give the longest number of moves?
%
go2 =>
  nolog,
  MaxLen = 0,
  Max = [],
  foreach(N in 1..1000) 
    println(n=N),
    All = coins(N),
    foreach(Plan in All)
      println(Plan)
    end,
    Len = All.len,
    println([n=N,len=Len]),
    nl,

    % Is this max length?
    if Len >= MaxLen then
       if Len == MaxLen then
         Max := Max ++ [All]
       else 
         Max :=  [All],
         MaxLen := Len
       end
    end
  end,
  println(maxLen=MaxLen),
  println(len=Max.len),
  foreach(M in Max) 
     foreach(MM in M) 
        % println(MM.join(', '))
        println(MM.join('\n')),
        nl
     end,
     nl
  end,
  nl.


coins(N) = findall(Plan, best_plan_nondet(N,Plan)).


final(Goal) => 
  Goal = 0.

% Use with go/0
action(From,To,Move,Cost) ?=>
  From mod 2 == 0,
  To = From div 2,
  % Move = From.to_string() ++ " div 2 = " ++ To.to_string(),
  Move = [From, ' div 2 = ', To],
  Cost = 1.

action(From,To,Move,Cost) ?=>
  To = From -1,
  % Move = From.to_string() ++ "-1 = " ++ To.to_string(),
  Move = [From, ' -1 = ', To],
  Cost = 1.

action(From,To,Move,Cost) =>
  To = From - 17,
  % Move = From.to_string() ++ "-17 = " ++ To.to_string(),
  Move = [From, ' -17 = ', To],
  Cost = 1.


/*
% variant
action(From,To,Move,Cost) ?=>
  (
    (
      From mod 2 == 0,
      To = From div 2,
      Move = [From,half,To]
    ) 
    ; 
    (
      To = From -1,
      Move = [From,minus_1,To]
    )
    ; 
    (
      To = From - 17,
      Move = [From,minus_17,To]
    )
  ),
  
  Cost = 1.
*/