package algs24;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac Taxicab.java
 *  Execution:    java Taxicab N
 *
 *  Find all nontrivial integer solutions to a^3 + b^3 = c^3 + d^3 where
 *  a, b, c, and d are between 0 and N. By nontrivial, we mean
 *  a <= b, c <= d, and (a, b) != (c, d).
 *
 *  % java Taxicab 11
 *
 *  % java Taxicab 12
 *  1729: 9^3 + 10^3
 *  1729: 1^3 +  12^3
 *
 *  % java Taxicab 1000
 *  1729: 1^3 + 12^3
 *  1729: 9^3 + 10^3
 *  4104: 2^3 + 16^3
 *  4104: 9^3 + 15^3
 *  13832: 2^3 + 24^3
 *  13832: 18^3 + 20^3
 *  ...
 *  87539319: 228^3 + 423^3
 *  87539319: 167^3 + 436^3
 *  87539319: 167^3 + 436^3
 *  87539319: 255^3 + 414^3
 *  ...
 *  1477354411: 802^3 + 987^3
 *  1477354411: 883^3 + 924^3
 *
 *************************************************************************/

public class XTaxicab implements Comparable<XTaxicab> {
  private final long sum;
  private final int i;
  private final int j;

  // create a new tuple (i, j, i^3 + j^3)
  public XTaxicab(int i, int j) {
    this.sum = (long) i*i*i + (long) j*j*j;
    this.i = i;
    this.j = j;
  }

  public int compareTo(XTaxicab that) {
    if      (this.sum < that.sum) return -1;
    else if (this.sum > that.sum) return +1;
    else                          return  0;
  }

  public String toString() {
    return sum + " = " + i + "^3 + " + j + "^3";
  }


  public static void main(String[] args) {

    int N = Integer.parseInt(args[0]);

    // initialize priority queue
    MinPQ<XTaxicab> pq = new MinPQ<>();
    for (int i = 1; i <= N; i++) {
      pq.insert(new XTaxicab(i, i));
    }

    // enumerate sums in ascending order, look for repeated sums
    XTaxicab prev = new XTaxicab(0, 0);   // sentinel
    while (!pq.isEmpty()) {
      XTaxicab s = pq.delMin();

      // sum is same as previous one
      if (prev.sum == s.sum) {
        StdOut.println(prev);
        StdOut.println(s);
      }
      prev = s;

      if (s.j < N) pq.insert(new XTaxicab(s.i, s.j + 1));
    }
  }

}