/*

  Least diff problem in Picat using bv module.

  The model solves the following problem:
  
  What is the smallest difference between two numbers X - Y
  if you must use all the digits (0..9) exactly once, i.e.
  Minimize the difference 
    ABCDE - FGHIJ

  This model uses the bv module.

  Cf least_diff.pi

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

*/

import sat.
import bv_utils.

main => go.


/*

  CPU time 0.506 seconds.
  [5,0,1,2,3,4,9,8,7,6]
  247


  CPU time 0.374 seconds.
  [5,0,1,2,3,4,9,8,7,6]
  247

  CPU time 0.88 seconds. Backtracks: 0

*/
go =>
   nolog,
   time(least_diff(L, Diff)),
   writeln(L.bti),
   writeln(Diff.bti),
   nl,
   time(least_diff2(L2, Diff2)),
   writeln(L2.bti),
   writeln(Diff2.bti),
   nl.

least_diff(L,Diff) =>

  L = make_bv_array(10,0,9),
  L = {A,B,C,D,E,  F,G,H,I,J},

  bv_all_different(L),

  X = A.bv_mul(10000).bv_add(B.bv_mul(1000)).bv_add(C.bv_mul(100)).bv_add(D.bv_mul(10)).bv_add(E),
  Y = F.bv_mul(10000).bv_add(G.bv_mul(1000)).bv_add(H.bv_mul(100)).bv_add(I.bv_mul(10)).bv_add(J),  
  bv_ge(X,Y), 
  Diff = bv_sub(X,Y),
  solve([$min(Diff)], L).


% Alternative version using scalar_product
least_diff2(L,Diff) =>
  L = make_bv_array(10,0,9),
  L = {A,B,C,D,E,  F,G,H,I,J},

  bv_all_different(L),
  M = L.length // 2,

  Base = make_base(M,10),
  X = bv_scalar_product(Base, [A,B,C,D,E]),
  Y = bv_scalar_product(Base, [F,G,H,I,J]),
  bv_ge(X,Y),
  Diff = bv_sub(X,Y),
  solve([$min(Diff)], L).

make_base(N, Base) = List =>
   List = [T : I in 1..N, T = Base**(N-I)].