// LeastDiff.java
// Hakan Kjellerstrand and Radoslaw Szymanek, 2008
// Slightly modified by Andrew Davison, ad@coe.psu.ac.th, Dec. 2022

/* Minimize the difference ABCDE - FGHIJ
   where A..J are all different values in the range 0..9.
   The solution is: 50123 - 49876 = 247

   More Info: https://en.wikipedia.org/wiki/Verbal_arithmetic

  The code utilizes a similar approach as in DonaldGeraldRobert.java
  but the constraint between the words is more complex, using
  a new diff variable. diff is also used as a cost
  parameter to make the search use branch-and-bound.

  Usage:
     > compile LeastDiff.java
     > run LeastDiff

     Minimize ABCDE - FGHIJ
     a = 5;  b = 0;  c = 1;  d = 2;  e = 3;
     f = 4;  g = 9;  h = 8;  i = 7;  j = 6;
     diff = 247;
 */

import org.jacop.constraints.*;
import org.jacop.core.*;
import org.jacop.search.*;
  // uses Jacop: https://jacop.cs.lth.se/

import java.util.*;


public class LeastDiff
{

  public static void main(String args[])
  {
    System.out.println("Minimize ABCDE - FGHIJ");

    Store store = new Store();

    // constraint variables for the letters
    IntVar a = new IntVar(store, "a", 0, 9);
    IntVar b = new IntVar(store, "b", 0, 9);
    IntVar c = new IntVar(store, "c", 0, 9);
    IntVar d = new IntVar(store, "d", 0, 9);
    IntVar e = new IntVar(store, "e", 0, 9);
    IntVar f = new IntVar(store, "f", 0, 9);
    IntVar g = new IntVar(store, "g", 0, 9);
    IntVar h = new IntVar(store, "h", 0, 9);
    IntVar i = new IntVar(store, "i", 0, 9);
    IntVar j = new IntVar(store, "j", 0, 9);

    IntVar digits[] = {a, b, c, d, e, f, g, h, i, j};
    store.impose(new Alldifferent(digits));

    IntVar[] abcde = {a, b, c, d, e};
    IntVar[] fghij = {f, g, h, i, j};

    // Constraint variables for the words
    IntVar abcdeTot = new IntVar(store, "abcde", 0, 99999);
    IntVar fghijTot = new IntVar(store, "fghij", 0, 99999);

    int[] weights = {10000, 1000, 100, 10, 1};

    // constraints linking letters to each word
    store.impose(new LinearInt(abcde, weights, "==", abcdeTot));
    store.impose(new LinearInt(fghij, weights, "==", fghijTot));

    // abcde > fghij
    store.impose(new XgtY(abcdeTot, fghijTot));

    // Constraint between the words:
    // diff = abcde - fghij   ->   diff + fghij = abcde
    IntVar diff = new IntVar(store, "diff", 0, 99999);
         // used as a cost argument to search.labeling()
    store.impose(new XplusYeqZ(diff, fghijTot, abcdeTot));


    SelectChoicePoint<IntVar> select =
      new SimpleSelect<>(JacopUtils.concat(digits, diff),
              new SmallestDomain<>(), new IndomainMin<>());
        // first consider the variables with the smallest domains

    Search<IntVar> search = new DepthFirstSearch<>();
    search.setPrintInfo(false);

    /* the search uses diff as a cost parameter, so the
       value found is the smallest. */
    search.labeling(store, select, diff);
    JacopUtils.printSolns(search);
  } /* main */


}  // end of LeastDiff class