/* 

  Share the Power Puzzle in Picat.

  standupmaths:
  https://www.youtube.com/watch?v=E5-pgBnGyzw

  This is an exploration of the fair sharing / taking turns of two persons.

  For 0..7: (n < 2^3)

    0^1 + 3^1 + 5^1 + 6^1
       == 
    1^1 + 2^1 + 4^1 + 7^1

  and
  
    0^2 + 3^2 + 5^2 + 6^2
       == 
    1^2 + 2^2 + 4^2 + 7^2


  For 0..15: (n < 2^4)


    0^i + 5^i + 6^i + 3^i + 12^i + 9^i + 10^i + 15^i

      ==
    
    1^i + 2^i + 4^i + 7^i + 8^i + 11^i + 13^i + 14^i

    i = 1,2,3

   
  General: n < 2^(k+1): i = 1..k


  Challenge: arrange 0..31 for i=1..4
 
 
  The solution solution of k is the start of the solution of k+1

  This model:
  [k = 1,n = 4]
  a = [0,3]
  b = [1,2]

  [k = 2,n = 8]
  a = [0,3,5,6]
  b = [1,2,4,7]

  [k = 3,n = 16]
  a = [0,3,5,6,9,10,12,15]
  b = [1,2,4,7,8,11,13,14]

  [k = 4,n = 32]
  a = [0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30]
  b = [1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31]


  go/0 use the CP model puzzle/3 and is not very fast 
  (K=4, for 0..31, is solved in 0.16s).

  go1/1 use the Thue-Morse sequence in puzzle2/3 and is 
  much faster: K =0..20 is solved in 2s.

  For more on the Thue-Morse sequence, see my Picat program
  http://hakank.org/picat/thue_morse_sequence.pi


  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.

%
% Using puzzle/3 (CP)
%
go ?=>
  K = 4,
  println([k=K,n=2**(K+1)]),
  puzzle(K, A,B),
  println(a=A),
  println(b=B),

  % fail,

  nl.

go => true.


%
% Thue-Morse version:
% This is the Thue-Morse sequence presented as the
% positions of A and B (0 and 1) as 0-based arrays.
% The Thue-Morse sequence is a sequence of fair sharing.
% (See http://hakank.org/picat/thue_morse_sequence.pi)
%
%
% This is _much_ faster than puzzle/3.
%
% [k = 0,n = 2]
% a = {0}
% b = {1}
%
% [k = 1,n = 4]
% a = {0,3}
% b = {1,2}
%
% [k = 2,n = 8]
% a = {0,3,5,6}
% b = {1,2,4,7}
%
% [k = 3,n = 16]
% a = {0,3,5,6,9,10,12,15}
% b = {1,2,4,7,8,11,13,14}
%
% [k = 4,n = 32]
% a = {0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30}
% b = {1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31}
%
% [k = 5,n = 64]
% a = {0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39,40,43,45,46,48,51,53,54,57,58,60,63}
% b = {1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,50,52,55,56,59,61,62}
%
% [k = 6,n = 128]
% a = {0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39,40,43,45,46,48,51,53,54,57,58,60,63,65,66,68,71,72,75,77,78,80,83,85,86,89,90,92,95,96,99,101,102,105,106,108,111,113,114,116,119,120,123,125,126}
% b = {1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,50,52,55,56,59,61,62,64,67,69,70,73,74,76,79,81,82,84,87,88,91,93,94,97,98,100,103,104,107,109,110,112,115,117,118,121,122,124,127}
% ...
% 
% 
% Note: K 0..10 is solved in 0.004s
%       K 0..20 is solved in 2.79s w/o output (5.97s with output)
% 
go2 =>
  foreach(K in 0..20)
    println([k=K,n=2**(K+1)]),
    % time(puzzle2(K, A,B)),
    puzzle2(K, A,B),
    println(a=A),
    println(b=B),
    nl
  end,
  nl.


%
% Here's an example of the Thue-Morse sequence for K 5:
%
% tm = {0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1}
% a = {0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39,40,43,45,46,48,51,53,54,57,58,60,63}
% b = {1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,50,52,55,56,59,61,62}
%
% The A sequence is the indices (0 based) of TM where TM[I] = 0 ('A'),
% and the B sequence is the indices where TM[I] = 1 ('B').
% 
go3 =>
  K = 5,
  TM = {thue2(I) : I in 0..2**(K+1)},
  println(tm=TM),
  puzzle2(K, A,B),
  println(a=A),
  println(b=B),
  nl.


%
% CP version
%
puzzle(K, A,B) =>

  N = 2**(K+1),
  N2 = N div 2,
  
  A = new_list(N2),
  A :: 0..N-1,
  B = new_list(N2),
  B :: 0..N-1,
  
  Vars = A ++ B,

  all_distinct(Vars),
  increasing(A),
  increasing(B),
  lex_lt(A,B),

  foreach(I in 1..K)
    sum([A[J]**I : J in 1..N2]) #= sum([B[J]**I : J in 1..N2])
  end,

  % 
  foreach(I in 1..N2-1)
    A[I] #< B[I+1],
    B[I] #< A[I+1]
  end,

  solve([ffd,split],Vars).


%
% Thue-Morse sequence approach:
%
% This approach is _much_ faster than using puzzle/3.
%
% Here is the solution for K=5, i.e. numbers 0..63. Found in 0.0s
%
% tm = [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]
% a = [0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39,40,43,45,46,48,51,53,54,57,58,60,63]
% b = [1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,50,52,55,56,59,61,62]
%
puzzle2(K, A,B) =>
  N = 2**(K+1),
  N2 = N div 2,
  A1 = new_array(N2),
  B1 = new_array(N2),
  AC = 1,
  BC = 1,
  foreach(I in 1..N)
    if thue2(I-1) = 0 then
       A1[AC] := I-1,
       AC := AC + 1
    else
       B1[BC] := I-1,
       BC := BC + 1
    end
  end,
  A = A1,
  B = B1.



%
% Recurrence relation:
%
% t(0) = 0
% t(2n) = t(n)
% t(2n+1) = 1-t(n)
%
% See http://hakank.org/picat/thue_morse_sequence.pi
%
table
thue2(0) = 0.
thue2(N) = TM, N mod 2 = 0 => TM = thue2(N div 2).
thue2(N) = TM, N mod 2 = 1 => TM = 1-thue2(N div 2).