/* 

  Gray code generator (CP) in Picat.

  https://stackoverflow.com/questions/67163261/how-to-build-a-gray-code-generator-in-picat
  """
  How to build a Gray-code generator in Picat?
  Encouraged by the knowledge I've gained from the answer to my previous post, 
  I aim to generate Gray-codes of given length. The procedure hamming seems to work 
  correctly, however, the Picat system finds no solution. Where's the mistake here?
  """

  This is a cp model which extends the model in the question: using
  a more efficient hamming distance function and using all_different/1 for
  ensure that the codes are unique. 

  Compare with gray_code.pi for a faster (non-cp) implementation.


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

*/

import cp, util.

main =>
   go.

go ?=>
  nolog,
  gray(5,Codes,CodesNum),
  println(Codes),
  println(codesNum=CodesNum), 
  nl,
  % fail,
  nl.
go => true.

/*

  N  time cp    time sat
  --------------------
  2   0.0s       0.002s
  3   0.0s       0.011s
  4   0.002s     0.029s
  5   0.003s     0.097s
  6   7.988s     3.918s
  7   1.594s   353.954s         
  8  11.301s    ?
  9  ?          ?

*/
go2 ?=>
  foreach(N in 2..10)
    println(n=N),
    if time(gray(N,Codes,CodesNum)) then
      println(Codes),
      println(codesNum=CodesNum),
      nl
    else
      println(nope)
    end,
    nl
  end,
  nl.
go2 => true.

/* 
% All solutions for N=3

codeNr = 8
[[0,0,1],[0,0,0],[0,1,0],[1,1,0],[1,0,0],[1,0,1],[1,1,1],[0,1,1]]
codesNum = [1,0,2,6,4,5,7,3]

[[0,0,1],[1,0,1],[1,0,0],[0,0,0],[0,1,0],[1,1,0],[1,1,1],[0,1,1]]
codesNum = [1,5,4,0,2,6,7,3]

[[0,0,1],[0,0,0],[1,0,0],[1,0,1],[1,1,1],[1,1,0],[0,1,0],[0,1,1]]
codesNum = [1,0,4,5,7,6,2,3]

[[0,0,1],[1,0,1],[1,1,1],[1,1,0],[1,0,0],[0,0,0],[0,1,0],[0,1,1]]
codesNum = [1,5,7,6,4,0,2,3]

[[0,0,1],[0,0,0],[1,0,0],[1,1,0],[0,1,0],[0,1,1],[1,1,1],[1,0,1]]
codesNum = [1,0,4,6,2,3,7,5]

[[0,0,1],[0,1,1],[0,1,0],[0,0,0],[1,0,0],[1,1,0],[1,1,1],[1,0,1]]
codesNum = [1,3,2,0,4,6,7,5]

[[0,0,1],[0,0,0],[0,1,0],[0,1,1],[1,1,1],[1,1,0],[1,0,0],[1,0,1]]
codesNum = [1,0,2,3,7,6,4,5]

[[0,0,1],[0,1,1],[1,1,1],[1,1,0],[0,1,0],[0,0,0],[1,0,0],[1,0,1]]
codesNum = [1,3,7,6,2,0,4,5]

[[0,0,1],[1,0,1],[1,0,0],[1,1,0],[1,1,1],[0,1,1],[0,1,0],[0,0,0]]
codesNum = [1,5,4,6,7,3,2,0]

[[0,0,1],[0,1,1],[1,1,1],[1,0,1],[1,0,0],[1,1,0],[0,1,0],[0,0,0]]
codesNum = [1,3,7,5,4,6,2,0]

[[0,0,1],[0,1,1],[0,1,0],[1,1,0],[1,1,1],[1,0,1],[1,0,0],[0,0,0]]
codesNum = [1,3,2,6,7,5,4,0]

[[0,0,1],[1,0,1],[1,1,1],[0,1,1],[0,1,0],[1,1,0],[1,0,0],[0,0,0]]
codesNum = [1,5,7,3,2,6,4,0]

*/
go3 ?=>
  N=3,
  gray(N,Codes,CodesNum),
  println(Codes),
  println(codesNum=CodesNum),
  nl,
  fail,
  nl.
go3 => true.

/*

CPU time 0.001 seconds.

2 = 2

CPU time 0.0 seconds.

3 = 12

CPU time 0.335 seconds.

4 = 2688

  It's https://oeis.org/A003042
  A003042		Number of directed Hamiltonian cycles (or Gray codes) on n-cube.
  1, 2, 12, 2688, 1813091520, 71676427445141767741440


*/
go4 ?=>
  NumSols = [],
  foreach(N in 2..5)
    time(Len = count_all(gray(N,_,_))),
    println(N=Len),    
    NumSols := NumSols ++ [N=Len]
  end,
  nl,
  println(NumSols),
  nl.
go4 => true.


gray(CodeLen,Codes,CodesNum) =>
    CodeNr is 2**CodeLen,
    Codes = new_array(CodeNr, CodeLen).array_matrix_to_list_matrix,
    Codes :: 0..1,
    CodesNum = new_list(CodeNr),
    CodesNum :: 0..CodeNr-1,

    foreach(CodeNr1 in 1..CodeNr)
        to_num(Codes[CodeNr1],2,CodesNum[CodeNr1]),
        CodeNr2 = cond(CodeNr1 == CodeNr, 1, CodeNr1 + 1),
        hamming2(Codes[CodeNr1], Codes[CodeNr2], 0, 1) 
        % hamming3(Codes[CodeNr1], Codes[CodeNr2], 1)       
        % hamming_distance(Codes[CodeNr1], Codes[CodeNr2], 1)
    end,

    % CodesNum[1] #= 0, % symmetry breaking 
    CodesNum[1] #= 1, % symmetry breaking (faster than 0!)
    all_different(CodesNum),

    Vars = CodesNum ++ Codes.vars,
    % Vars = Codes.vars ++ CodesNum,    
    solve($[ffc,updown],Vars).

hamming2([], [], A, A).
hamming2([H1|T1], [H2|T2], A0, H) :-
    B :: 0..1,
    H1 #!= H2 #<=> B #= 1,
    A1 #= A0 + B,
    hamming2(T1, T2, A1, H).

hamming3(X,Y,H) :-
  N = X.len,
  hamming3(N,N,X,Y,0,H).

hamming3(N,1,_X,_Y,H,H).
hamming3(N,I,X,Y,H0, H) :-
    I > 1,
    B :: 0..1,
    X[I] #!= Y[I] #<=> B #= 1,
    H1 #= H0 + B,
    hamming3(N,I-1,X,Y,H1, H).


hamming_distance(As, Bs,Diff) =>
   Diff #= sum([(A #!= B) : {A,B} in zip(As,Bs)]).

to_num(List, Base, Num) =>
        Len = length(List),
        Num #= sum([List[I]*Base**(Len-I) : I in 1..Len]).

to_num(List, Num) =>
       to_num(List, 10, Num).