!752

// TODO: translator should accept this: "s/Rational/Rat" :-)

static S dataProgID = "#1002049"; // read/save data there

// Numeric quadruple
static class NQ {
  BigInteger a;
  S b;
  BigInteger c;
  S d;
  
  *() {}
  *(S a, S *b, S c, S *d) {
    this.a = smartBigint(a);
    this.c = smartBigint(c);
  }
  *(BigInteger *a, S *b, BigInteger *c, S *d) {}
  
  public boolean equals(O o) {
    ret stdEq(this, o, "a", "b", "c", "d");
  }
  
  public S toString() {
    ret a + " " + b + " is " + c + " " + d;
  }
  
  NQ reverse() {
    ret new NQ(c, d, a, b);
  }

  bool trivial() {
    ret eq(b, d) && eq(a, c);
  }
  
  bool usable() {
    if (trivial()) ret false;
    if (eq(a, 0) || eq(c, 0)) ret false;
    if (eq(b, d)) ret false; // matchin kinds, non-matching numbers
    ret true;
  }
}

static new L<NQ> terms;

p {
  load(dataProgID, "terms");
}

synchronized answer {
  if (match("* * is * *", s, m) || match("* * are * *", s, m)) {
    NQ nq = new NQ(m.unq(0), simplify(m.unq(1)), m.unq(2), simplify(m.unq(3)));
    if (terms.contains(nq))
      ret "I know!";
    terms.add(nq);
    save(dataProgID, "terms");
    ret "OK, added to theory. Now " + l(terms) + " entries";
  }
  
  if (match("show theory", s)) {
    ret structure(allToString(terms));
  }
  
  if (match("how many * * * *", s, m)) {
    S isAre = m.get(1);
    if (litlist("is", "are").contains(toLower(isAre))) {
      BigInteger a = bigint(m.unq(2));
      S b = m.unq(3);
      S d = m.unq(0);
      Rat c = calc(new Rat(a), b, d);
      if (c == null)
        ret "I don't know";
      ret a + " " + b + " " + isAre + " " + c.mixed() + " " + d + "!";
    }
  }
  
  if (match("check theory", s))
    ret checkTheory();
    
  if (match("show clusters", s))
    ret showClusters();
}

static Rat calc(Rat a, S b, S d) {
  b = simplify(b);
  d = simplify(d);
  ret calcTransitive(a, b, d, new TreeSet);
}

// b is the unit we have, d is the unit we're searching for
static Rat calcTransitive(Rat a, S b, S d, Set<S> seen) {
  print(format("calcTransitive * * * *", a, b, d, structure(seen)));
  if (eq(b, d)) ret a; // done
  if (seen.contains(b)) ret null;
  seen.add(b);
  for (NQ nq : terms) if (nq.usable()) {
    twice {
      if (eq(nq.b, b)) {
        Rat r = calcTransitive(calcForward(nq, a), nq.d, d, seen);
        if (r != null) ret r;
      }
      nq = nq.reverse();
    }
  }
  null;
}

static Rat calcForward(NQ nq, Rat a) {
  ret a.multiply(nq.c).divide(nq.a);
}

static S simplify(S s) {
  ret toSingular(toLower(s));
}

static S toSingular(S s) {
  ret dropSuffix("s", s); // yeah it's rough
}

static BigInteger smartBigint(S s) {
  if (litlist("a", "an", "one").contains(toLower(s)))
    ret bigint(1);
  ret bigint(s);
}

static S checkTheory() {
  new L<NQ> trivial;
  new L<NQ> valid;
  new L<NQ> invalid;
  for (NQ nq : terms) {
    L<NQ> bucket = nq.trivial() ? trivial : nq.usable() ? valid : invalid;
    bucket.add(nq);
  }
  
  new StringBuilder buf;
  if (!isEmpty(trivial))
    buf.append(l(trivial) + " trivial: " + joinQuoted(", ", allToString(trivial)) + ".\n");
  
  if (!isEmpty(invalid))
    buf.append(l(invalid) + " invalid: " + joinQuoted(", ", allToString(invalid)) + ".\n");
  
  if (!isEmpty(valid))
    buf.append(l(valid) + " valid statements.\n");
    
  L<L<S>> clusters = getClusters();
  buf.append(l(clusters) + " clusters. ");

  int consistent = 0;
  new L<L<S>> inconsistent;
  for (L<S> cluster : clusters) {
    boolean ok = checkCluster(cluster);
    if (ok) ++consistent; else inconsistent.add(cluster);
  }
  
  if (isEmpty(inconsistent))
    buf.append("All consistent.\n");
  else {
    buf.append(l(inconsistent) + " cluster(s) inconsistent:\n");
    for (L<S> cluster : inconsistent)
      buf.append("  " + structure(cluster) + "\n");
  }

  ret trim(buf);
}

static L<L<S>> getClusters() {
  L<NQ> l = filterByMethod(terms, "usable"); // get all usable terms
  
  // a cluster is a list of concepts.
  // first, make trivial clusters (one per concept).
  
  Map<S, L<S>> clusters = new TreeMap<S, L<S>>();
  for (NQ nq : l) {
    if (!clusters.containsKey(nq.b))
      clusters.put(nq.b, litlist(nq.b));
    if (!clusters.containsKey(nq.d))
      clusters.put(nq.d, litlist(nq.d));
  }
  
  // then, merge the clusters.
  
  for (NQ nq : l) {
    L<S> c1 = clusters.get(nq.b), c2 = clusters.get(nq.d);
    if (c1 != c2) { // different clusters, need to merge!
      mergeClusters(clusters, c1, c2);
    }
  }
  
  // IdentitySet would be more efficient, but meh.
  ret asList(new HashSet<L<S>>(clusters.values()));
}

static S showClusters() {
  L<L<S>> clusters = getClusters();
  ret l(clusters) + " clusters: " + structure(clusters);
}

static void mergeClusters(Map<S, L<S>> clusters, L<S> c1, L<S> c2) {
  for (S concept : c2) {
    clusters.put(concept, c1);
    c1.add(concept);
  }
}

static boolean checkCluster(L<S> cluster) {
  new Map<S, Rat> values;
  
  // randomly choose a concept and a value (!= 0) to start with
  values.put(cluster.get(0), rat(1));
  
  while true {
    int lastSize = l(values);
    
    for (NQ nq : terms) if (nq.usable()) {
      twice {
        Rat lvalue = values.get(nq.b);
        if (lvalue != null) {
          Rat rvalue = calcForward(nq, lvalue);
          Rat expectedValue = values.get(nq.d);
          if (expectedValue == null) 
            values.put(nq.d, rvalue);
          else if (neq(expectedValue, rvalue))
            ret false; // Cluster is inconsistent!
        }
        nq = nq.reverse();
      }
    }
    if (l(values) == lastSize) ret true; // all done
  }
}

Began life as a copy of #1002049