/*

  de Bruijn sequence in Picat.

  Implementation of de Bruijn sequences in Comet, both "classical" 
  and "arbitrary". 
 
  Compare with the the web based programs:
    http://www.hakank.org/comb/debruijn.cgi   
    http://www.hakank.org/comb/debruijn_arb.cgi

  For Base = 2, N = 3, M = 8 there are 2 solutions:
    x : [](0, 1, 3, 7, 6, 5, 2, 4)
    bincode : [0, 0, 0, 1, 1, 1, 0, 1]

    x : [](0, 1, 2, 5, 3, 7, 6, 4)
    bincode : [0, 0, 0, 1, 0, 1, 1, 1]

  There are two symmetry breaking constraints:
  - if possible, we require that the occurrences of number are the same, 
    i.e if M mod Base == 0.
  - the sequence X always start with the minumum value (0).


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

*/

import cp,util.
% import sat,util.

main => go.


%
% Let's start simple: This has 2 solutions.
%
go ?=>
        Base = 2,
        N = 3,
        M = Base**N,
        % Tmp = Base**N-1,
        % do_it2(Base, N, M, Tmp),
        deBruijn(Base, N, M, X, Binary, BinCode, GCC),
        println(x=X),
        println(binary=Binary),
        println(binCode=BinCode),
        println(gcc=GCC),        
        nl,
        fail.

go => true.

%
% This is an "arbitrary" de Bruijn sequence
%   Base = 13
%   N = 4
%   M = 52 (note: not 13**4=28561)
%
% i.e. the length of the sequence is 52, i.e. < Base**N.
% This is a sequence length 52 with 4 occurrences of 1..13.
% 
% 
% Many solutions. Here are some "random looking", generated
% with solve($[ffd,rand_val],Flattened) below:
%  gcc = {4,4,4,4,4,4,4,4,4,4,4,4,4}
%  0 9 0 10 4 1 1 12 3 1 7 2 3 0 12 12 1 9 10 10 11 7 8 3 3 4 5 2 4 10 4 9 12 6 6 5 5 2 5 7 11 9 11 2 8 6 6 8 7 8 0 11
%  0 9 0 10 4 1 1 12 3 1 7 2 3 0 12 12 1 9 10 10 11 7 8 3 3 4 5 2 4 10 4 9 12 6 6 5 5 2 5 7 11 9 11 2 8 6 6 8 7 0 11 8
%
% Or use the sat solver which also generate "random looking" solutions:
%  0 4 6 2 3 3 0 11 12 9 10 7 4 2 9 6 5 11 11 6 11 8 8 1 5 12 10 9 12 12 6 10 5 1 1 4 0 9 4 7 1 7 0 8 8 3 3 7 5 10 2 2
%  0 1 4 3 0 3 1 0 12 8 12 1 6 11 8 9 4 10 4 2 11 2 2 4 9 7 10 6 12 5 7 9 11 7 10 11 5 1 2 6 7 8 3 5 6 10 9 12 0 8 3 5
%
go2 ?=>
        Base = 13,
        N = 4,
        M = 52,
        Tmp = Base**N-1,
        do_it2(Base, N, M, Tmp),
        fail.

go2 => true.

%
% The "door code" sequence, i.e. all codes of length 4 in for 0..9.
%
go3 =>
        garbage_collect(300_000_000),
        Base = 10,
        N = 4,
        M = Base**N,
        Tmp = Base**N-1,
        do_it(Base, N, M, Tmp).

%
% Arbitrary deBruijn:
%  Base = 2
%  N    = 5
%  M    = 27 (note: not 2**5=32 )
%
% It has 2000 solutions.
%
go4 ?=>
        Map = get_global_map(),
        Map.put(count,0),
        Base = 2,
        N = 5,
        M = 27,
        Tmp = Base**N-1,
        do_it(Base, N, M, Tmp),
        Map.put(count,Map.get(count)+1),
        fail.

go4 => 
  println(count=get_global_map().get(count)).


%
% Classic deBruijn:
%  Base = 2
%  N    = 5
%  M    = 32 (note: 2**5=32)
%
% It has 2048 solutions.
go5 ?=>
        Map = get_global_map(),
        Map.put(count,0),
        Base = 2,
        N = 5,
        M = 32,
        Tmp = Base**N-1,
        do_it(Base, N, M, Tmp),
        Map.put(count,Map.get(count)+1),
        fail.

go5 => 
  println(count=get_global_map().get(count)).



%
% converts a number Num to/from a list of integer List given a base Base
%
to_num(List, Base, Num) =>
        Len = length(List),
        Num #= sum([List[I]*Base**(Len-I) : I in 1..Len]).


%
% de Bruijn sequence with 
%   Base: base to use
%   N: length of each element (row)
%   M: length of sequence
%
deBruijn(Base, N, M, X, Binary, BinCode, GCC) =>

        %
        % X: list of the integers to use which are converted to
        %    base-ary numbers below
        %
        X = new_list(M),
        X :: 0..(Base**N)-1,

        all_different(X),
        % all_distinct(X),

        %
        % Binary: the matrix of the "fully expanded" integers in X
        %
        Binary = new_array(M, N),
        Binary :: 0..Base-1,
        foreach(I in 1..M)
              % convert the integer to base-ary representation
              to_num([Binary[I,J] : J in 1..N], Base, X[I])
        end,

        %% number of occurrences for each number
        GCC = new_array(Base), % index: 0..Base-1
        GCC :: 0..M,

        %
        % The de Bruijn criterion: Connect one element to the next...
        %
        foreach(I in 2..M, J in 2..N) 
           Binary[I-1, J] #= Binary[I, J-1]
        end,
        
        % ... and around the corner.
        foreach(J in 2..N) 
           Binary[M, J] #= Binary[1, J-1] 
        end,
        
        
        % 
        % BinCode: The de Bruijn sequence, i.e. the first
        %          elements in each row in Binary
        %          Note: this is just a slice.
        BinCode = [Binary[I,1] : I in 1..M],

        % GCC: Count the number of different elements in the bin code
        % (poor man's global cardinarlity count...)
        foreach(I in 1..Base)
          count(I-1, BinCode, GCC[I])
        end,

        % If possible, we require that the occurrences of number are the same.
        if M mod Base == 0 then
           foreach(I in 2..Base)
             GCC[I] #= GCC[I-1],
             GCC[I] #= M div Base
           end
        end,

        % symmetry breaking
        X[1] #= min(X),
        println(gcc=GCC),

        Flattened = X ++ Binary ++ GCC,
        solve([ff,split],Flattened),
        % solve([ffd, rand_val],Flattened), % random looking...    
        println(gcc=GCC).
        
%
% Wrapper: Print everything
%
do_it(Base, N, M, Tmp) =>
        println([base=Base, n=N, m=M, '(Base**N)-1)'=(Tmp)]),
        deBruijn(Base, N, M, X, Binary, BinCode, GCC),
        println(x=X),
        % println(binary=Binary),
        foreach(B in Binary) println(B.to_list()) end,
        if max(BinCode) > 9 then
          println(debruijn=[I.to_string() : I in BinCode].join(' '))
        else 
          println(debruijn=[I.to_string() : I in BinCode].join(''))
        end,
        println(gcc=GCC),
        printf("\n").

%
% Simple presentation
%
do_it2(Base, N, M, Tmp) =>
        deBruijn(Base, N, M, X, Binary, BinCode,GCC),
        if max(BinCode) > 0 then
          println([to_string(B) : B in BinCode].join(' '))
        else
          println([to_string(B) : B in BinCode].join(''))
        end.