// DonaldGeraldRobert.java
// Krzysztof Kuchcinski and Radoslaw Szymanek, 2008
// Slightly modified by Andrew Davison, ad@coe.psu.ac.th, Dec. 2022

/* The cryptogram: DONALD + GERALD = ROBERT.
   The solution:
     Donald    526485
     Gerald  + 197485
               ------
     Robert    723970

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

  The code utilizes three weighted sum LinearInt constraints:
      w1 * x1 + w2 * x2 + ... + wn * xn == sum
  for each word, with the letters on the lhs, and the total
  for the word on the right.

 See SendMoreMoney.java for a simpler approach.

  Usage:
     > compile DonaldGeraldRobert.java
     > run DonaldGeraldRobert

     Donald + Gerald = Robert
     d = 5;  o = 2;  n = 6;  a = 4;  l = 8;
     g = 1;  e = 9;  r = 7;  b = 3;  t = 0;
*/



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

import java.util.*;


public class DonaldGeraldRobert
{

  public static void main(String args[])
  {
    System.out.println("Donald + Gerald = Robert");

    Store store = new Store();

    // create constraint variables for the letters
    // Note: the first letter of each word cannot be 0
    IntVar d = new IntVar(store, "d", 1, 9);  // not 0
    IntVar o = new IntVar(store, "o", 0, 9);
    IntVar n = new IntVar(store, "n", 0, 9);
    IntVar a = new IntVar(store, "a", 0, 9);
    IntVar l = new IntVar(store, "l", 0, 9);
    IntVar g = new IntVar(store, "g", 1, 9);  // not 0
    IntVar e = new IntVar(store, "e", 0, 9);
    IntVar r = new IntVar(store, "r", 1, 9);  // not 0
    IntVar b = new IntVar(store, "b", 0, 9);
    IntVar t = new IntVar(store, "t", 0, 9);

    // Since T is D+D mod 10 then T must be even or 0, so
    store.impose(new XneqC(t, 1));    // T is not odd
    store.impose(new XneqC(t, 3));
    store.impose(new XneqC(t, 5));
    store.impose(new XneqC(t, 7));
    store.impose(new XneqC(t, 9));

    IntVar[] digits = {d, o, n, a, l, g, e, r, b, t};
    store.impose(new Alldifferent(digits));

    IntVar[] donald = {d, o, n, a, l, d};
    IntVar[] gerald = {g, e, r, a, l, d};
    IntVar[] robert = {r, o, b, e, r, t};

    // Constraint variables for the three words
    IntVar donaldTot = new IntVar(store, "Donald", 0, 999999);
    IntVar geraldTot = new IntVar(store, "Gerald", 0, 999999);
    IntVar robertTot = new IntVar(store, "Robert", 0, 999999);

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

    // constraints linking letters to each word
    store.impose(new LinearInt(donald, weights, "==", donaldTot));
    store.impose(new LinearInt(gerald, weights, "==", geraldTot));
    store.impose(new LinearInt(robert, weights, "==", robertTot));

    // constraint linking the three words
    store.impose(new XplusYeqZ(donaldTot, geraldTot, robertTot));

    SelectChoicePoint<IntVar> select =
      new SimpleSelect<>(digits, null, new IndomainMin<>());

    Search<IntVar> search = new DepthFirstSearch<>();
    search.setPrintInfo(false);
    search.labeling(store, select);

    JacopUtils.printSolns(search);
  } /* main */

}  // end of DonaldGeraldRobert class