/* 

  Nimatron problem in Picat.

  Problem and XPress Model model from 
  Martin J.Chlond & Oguz Akyol "A Nimatron"
  http://archive.ite.journal.informs.org/Vol3No3/ChlondAkyol/

  Original note from the XPress Mosel model:
  nim.mos : Computes move to safe position (if available) in game of Nim
  Written by : Martin J. Chlond
  Date written : 26 December 2001

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

*/


import cp.

main => go.


go =>

  % number of heapas
  Heap = 5,

  % columns for binary representation of position after move
  Col = 4,

  % maximum number of heaps to change (if k>1 then Moore's game) ! number of squares per side
  K = 1, 

  % maximum number allowed in any heap
  NMax = 2**(Col-1),

  % number in each heap before move,
  N = [5,4,3,2,1],

  % variables

  % binary values of position after move
  X = new_array(Heap,Col),
  X :: 0..1, 

  % 1 if heap changed, 0 otherwise
  D = new_list(Heap), 
  D :: 0..1,

  % number taken from heap
  S = new_list(Heap),

  % number in each heap after move
  M = new_list(Heap),

  % dummy variables for winning position test 
  W = new_list(Col), 

  % number of heaps changed
  HeapCh #= sum(D),

  foreach(I in 1..Heap) 
     S[I] #>= 0,
     M[I] #>= 0
  end,

  foreach(I in 1..Col) 
     W[I] #>= 0
  end,


  % convert heap numbers [after move] to binary
  foreach(I in 1..Heap) 
    sum([(2**(J-1))*X[I,J] : J in 1..Col]) #= M[I]
  end,

  % ensures safe position after move
  foreach(J in 1..Col)
    sum([X[I,J] : I in 1..Heap]) #= (K+1)*W[J]
  end,

  % positions before and after are consistent with move
  foreach(I in 1..Heap)
    N[I]-S[I] #= M[I]
  end,
 
  % dummy set to 1 if heap changed
  foreach(I in 1..Heap)
    S[I]-NMax*D[I] #=< 0
  end,

  % HeapCh #= 1,


  % minimise number of heaps changed - 
  % if solution is zero then current position already safe

  Vars = X.vars() ++ D ++ S ++ M ++W,
  solve($[min(HeapCh)], Vars),

  println(heapCh=HeapCh),
  foreach({SS,MM} in zip(S,M))
     println([SS,MM])
  end,

  nl.