/* 

  Shifted division in Picat.

  https://twitter.com/queued_q/status/1315505135246663682
  """
   7903225806451612       7
   -----------------  =   -
    9032258064516128      8
  """

  This is represented as

    x/y = a/b

  Note that a (here 7) is the first digit of x and b (here 8) is the
  last digit of y. These constraints are what make it interesting problem.


  Also, see an animation of this at https://twitter.com/ScienceMagician/status/1485613903623200776

  Here are the solutions for 17 digits numbers:
  x = 7903225806451612
  y = 9032258064516128
  [a1 = 7,bn = 8]

  x = 8648648648648648
  y = 6486486486486486
  [a1 = 8,bn = 6]

  x = 4999999999999999
  y = 9999999999999998
  [a1 = 4,bn = 8]

  x = 1999999999999999
  y = 9999999999999995
  [a1 = 1,bn = 5]

  x = 4324324324324324
  y = 3243243243243243
  [a1 = 4,bn = 3]

  x = 2666666666666666
  y = 6666666666666665
  [a1 = 2,bn = 5]

  x = 1666666666666666
  y = 6666666666666664
  [a1 = 1,bn = 4]



  Note that Picat's CP/SAT solvers cannot work with numbers larger than 2**56, about
  10**17.

  Below (go4/0 and shifted_division2/0) is a port of a Python non-CP approach.

  For a much faster implementation which also supports much larger numbers, 
  see my Z3/Python program http://hakank.org/z3/shifted_division2.py
  

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

*/

import sat.
% import cp.

main => go.

go =>
  nolog,
  % N = 16, % N=17 is the largest we can go with CP/SAT
  member(N, 2..17),
  shifted_division(N,X,Y,A,B),
  println(x=X),
  println(y=Y),
  println([a1=A[1],bn=B[N]]),
  nl,
  fail,
  nl.

%
% Number of solutions (w/o any out weeding).
%
% 2 = 4
% 3 = 7
% 4 = 6
% 5 = 7
% 6 = 5
% 7 = 20
% 8 = 4
% 9 = 8
% 10 = 6
%
% 
go2 =>
  nolog,
  foreach(N in 2..10)
    Count = count_all(shifted_division(N,_X,_Y,_A,_B)),
    println(N=Count)
  end,
  nl.

% 
% The instance above.
% x = 7903225806451612
% y = 9032258064516128
% [a1 = 7,bn = 8]
% 
go3 =>
  nolog,
  N = 16,
  X #= 7903225806451612,
  shifted_division(N,X,Y,A,B),
  println(x=X),
  println(y=Y),
  println([a1=A[1],bn=B[N]]),
  fail,
  nl.

/*
  The output is

   [903225806451612,7,8] 
  which represents
   7903225806451612    7
   ----------------  = -
    9032258064516128   8

  See more below.

*/
go4 =>
  shifted_division2(),
  nl.


%
% Alternative and faster approach compared to shifted_division/1.
%
% However, the maximum number of digits is 16 (not 17).
%
go5 =>
  nolog,
  foreach(N in 2..16)
    Sol = findall(X,(shifted_division3(N,X,Y,A,B), println([N,X,Y,A,B]))),
    println(N=Sol.len),
    nl
  end,
  nl.
  



shifted_division(N,X,Y,A,B) =>

  X :: 10**(N-1)..10**(N)-1,
  Y :: 10**(N-1)..10**(N)-1,  


  A = new_list(N),
  A :: 0..9,

  B = new_list(N),
  B :: 0..9,

  to_num(A,X),
  to_num(B,Y),

  % The division
  %  X / Y = A[1] / B[N]
  % Convert to a multiplication instead.
  X*B[N] #=A[1]*Y,

  % Bi = shift Ai to right
  foreach(I in 2..N)
    A[I] #= B[I-1]
    % , A[I] #!= B[I] % weed out some boring solutions
    % . A[I] #!= A[I-1] % weed out some boring solutions
  end,

  % 
  A[1] #> 0,
  B[1] #> 0,
  X #!= Y,

  Vars = A ++ B ++ [X,Y],
  solve($[],Vars).

%
% From the Python code https://twitter.com/queued_q/status/1315506898850869248/photo/1
% No CP.
%
% This works when B is single digit number.
% 
% Here are some solutions:
%
% 2105263157894736842   2
% ------------------ = -- 
% 1052631578947368421   1
% 
% 5813953488372093023255813953488372093023255   5
% ------------------------------------------ = -- 
% 8139534883720930232558139534883720930232557   7
%
% 67924528301886792452830188679245283018867924528301886   6
% ---------------------------------------------------- = -- 
% 79245283018867924528301886792452830188679245283018867   7
%
%
% 19944751381215469613259668508287292817679558011049723756906077348066298342541436464088397790055248618784530386740331491712707182320441988950276243093922651933701657458563535911602209  19
% ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ = -- 
% 9447513812154696132596685082872928176795580110497237569060773480662983425414364640883977900552486187845303867403314917127071823204419889502762430939226519337016574585635359116022099   9
%
%
% Here's the solution in the tweet and some "extensions" of that
%
% 7903225806451612   7
% --------------- = -- 
% 9032258064516128   8
%
% 7903225806451612903225806451612   7
% ------------------------------ = -- 
% 9032258064516129032258064516128   8
%
% 7903225806451612903225806451612903225806451612   7
% --------------------------------------------- = -- 
% 9032258064516129032258064516129032258064516128   8
%
% 7903225806451612903225806451612903225806451612903225806451612   7
% ------------------------------------------------------------ = -- 
% 9032258064516129032258064516129032258064516129032258064516128   8
%
%
% A similar "progression" for 8/2:
% 8205128   8
% ------ = -- 
% 2051282   2

% 8205128205128   8
% ------------ = -- 
% 2051282051282   2

% 8205128205128205128   8
% ------------------ = -- 
% 2051282051282051282   2

% 8205128205128205128205128   8
% ------------------------ = -- 
% 2051282051282051282051282   2

% 8205128205128205128205128205128   8
% ------------------------------ = -- 
% 2051282051282051282051282051282   2

% 8205128205128205128205128205128205128   8
% ------------------------------------ = -- 
% 2051282051282051282051282051282051282   2

% 8205128205128205128205128205128205128205128   8
% ------------------------------------------ = -- 
% 2051282051282051282051282051282051282051282   2

% 8205128205128205128205128205128205128205128205128   8
% ------------------------------------------------ = -- 
% 2051282051282051282051282051282051282051282051282   2

% 8205128205128205128205128205128205128205128205128205128   8

% 2051282051282051282051282051282051282051282051282051282   2

% 8205128205128205128205128205128205128205128205128205128205128   8
% ------------------------------------------------------------ = -- 
% 2051282051282051282051282051282051282051282051282051282051282   2

% 8205128205128205128205128205128205128205128205128205128205128205128   8
% ------------------------------------------------------------------ = -- 
% 2051282051282051282051282051282051282051282051282051282051282051282   2

% 8205128205128205128205128205128205128205128205128205128205128205128205128   8
% ------------------------------------------------------------------------ = -- 
% 2051282051282051282051282051282051282051282051282051282051282051282051282   2
%
% Here are the found fractions:
% [[1,1],[1,3],[1,4],[1,5],[2,1],[2,2],[2,3],[2,5],[2,6],[3,1],[3,3],[3,4],[3,7],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[4,7],[4,8],[5,1],[5,3],[5,4],[5,5],[5,7],[5,8],[6,1],[6,2],[6,3],[6,4],[6,5],[6,6],[6,7],[6,8],[7,1],[7,3],[7,4],[7,5],[7,7],[7,8],[8,1],[8,2],[8,3],[8,4],[8,6],[8,7],[8,8],[9,1],[9,3],[9,4],[9,5],[9,7],[9,8],[9,9],[10,1],[10,2],[10,3],[10,5],[10,6],[10,7],[10,8],[10,9],[11,1],[11,3],[11,4],[11,5],[11,7],[11,8],[11,9],[12,1],[12,2],[12,3],[12,4],[12,5],[12,6],[12,7],[12,8],[12,9],[13,1],[13,3],[13,4],[13,7],[13,8],[13,9],[14,1],[14,2],[14,3],[14,4],[14,5],[14,6],[14,7],[14,8],[14,9],[15,1],[15,3],[15,4],[15,5],[15,7],[15,8],[15,9],[16,1],[16,2],[16,3],[16,4],[16,5],[16,6],[16,7],[16,8],[16,9],[17,1],[17,3],[17,4],[17,5],[17,7],[17,8],[17,9],[18,1],[18,2],[18,3],[18,6],[18,7],[18,8],[18,9],[19,1],[19,3],[19,4],[19,5],[19,7],[19,8],[19,9]]
% 
shifted_division2() =>
  Res = [],
  foreach(A in 1..19)
    foreach(B in 1..19)
      foreach(I in 1..A*10-B-1)
        if A*B * (10**I-1) mod (A*10-B) == 0 then
          X = A*B * (10**I-1) // (A*10-B),
          if 10**(I-1) <= X, X < 10**I then
            XS = X.to_string,
            XLen = XS.len,
            Format = "%" ++ "w  %2w\n",
            S = A.to_string ++ XS,
            T = XS ++ B.to_string,
            % println([X,A,B]),
            printf(Format,S,A),
            println(['-' : _ in 1..XLen] ++ " = -- "),
            printf(Format,T,B),
            Res := Res ++ [[A,B]],
            nl
          end
        end
      end
    end
  end,
  % What fractions where used?
  println(Res.sort_remove_dups).


/*
  Another constraint approach but without to_num/2.
*/
shifted_division3(N,X,Y,A,B) =>
  C :: 10**(N-2)..10**(N-1)-1, % The common number
  [X,Y] :: 10**(N-1)..10**N-1,
  [A,B] :: 0..9,

  X #= C + A*10**(N-1),
  Y #= 10*C + B,

  X*B #= A*Y,
  X #!= Y,
  
  Vars = [C,X,Y,A,B],
  solve(Vars).


%
% 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]).

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