// PynTriplets.java
// Andrew Davison, ad@coe.psu.ac.th, April 2023

/* A Pythagorean triple are three positive integers (a,b,c), 
   a < b < c, such that a^2 + b^2 = c^2. 

   For any pair of relatively prime integers, (m, n), such
   that one of them is odd, the other is even, and m > n > 0, 
   the three numbers (m^2 — n^2, 2mn, m^2 + n^2) form a 
   primitive triple.

   https://en.wikipedia.org/wiki/Pythagorean_triple
and
   https://www.geeksforgeeks.org/generate-pythagorean-triplets/

   Test all the (m,n) pairs for m,n = 1 up to a max value
   and draw a box diagram showing the (m.n) pairs that make triplets.
   Also list all the triplets <= 100.

   The diagram is based on 
   Figure 1.3, "A view of the Pythagorean Triplets" from
       "A Course in Computational Number Theory"
       David Bressoud, Stan Wagon, Wiley, 2000

   Usage:
     > compile PynTriplets.java
     > run PynTriplets <max m,n>
   e.g.
     > run PynTriplets 50

*/

import java.awt.Point;
import java.math.*;
import java.util.*;


public class PynTriplets
{
  private static final int MAX_WIDTH = 800;
  private static final int BOX_SIZE = 15;


  public static void main(String[] args)
  {
    if (args.length != 1) {
      System.out.println("Usage: run PynTriplets <max m,n>");
      return;
    }
    int max = Math.abs(Nut.parseInt(args[0]));

    ArrayList<Point> coords = new ArrayList<>();  // list of (m,n) pairs
    ArrayList<PynTriplet> triplets = new ArrayList<>();  // list of pyn triplets

    for (int n=1; n < max; n++) {
      for (int m=n+1; m <= max; m++) {   // m > n, so each pair is unique
        if (((m%2 == 0 && n%2 == 1) ||   // odd or even
             (m%2 == 1 && n%2 == 0)) &&
            (Nut.gcd(m, n) == 1)) {      // only get primitive triplets
          int a = (m * m) - (n * n);
          int b = 2 * m * n;
          int c = (m * m) + (n * n);
          // System.out.printf("(%d, %d): %d %d %d\n", m, n, a, b, c);
          coords.add( new Point(m,n)); 
          triplets.add( new PynTriplet(a, b, c));
        }
      }
    }

    // print the triplets <= 100
    Collections.sort(triplets);
    System.out.println("Triplets up to 100");
    for (PynTriplet pt : triplets) {
      if (pt.getC() > 100)
         break;
       else
         System.out.print(pt + " ");
    }
    System.out.println();

    // reduce the grid's box size for large max
    int boxSize = BOX_SIZE;
    while (boxSize*max > MAX_WIDTH) {
      boxSize--;
      if (boxSize == 0) {
        boxSize = 1;   // minimum size
        break;
      }
    }

    // draw a box diagram
    StdDraw.setCanvasSize(boxSize*max, boxSize*max);
    StdDraw.setXscale(1, max);
    StdDraw.setYscale(1, max);

    // draw a grid of empty boxes
    StdDraw.setPenColor(StdDraw.BLACK);
    for(int i=1; i <= max; i++)
      for(int j=1; j <= max; j++)
        StdDraw.square(i+0.5, j+0.5, 0.5);

    // color in the (m,n) boxes
    StdDraw.setPenColor(StdDraw.BLUE);
    for(Point coord : coords)
      StdDraw.filledSquare(coord.x+0.5, coord.y+0.5, 0.5);  // (m,n)

  } /* main */


}  // end of PynTriplets class