import java.util.Arrays; 


class Array2D
{
   public static void main (String arg[])
   {

       int[][] sqr = new int[5][5];
       // note: array elements are given default values, numbers get zero. 

       System.out.println("Here is the sqr array:");
       for (int r=0; r < sqr.length; r++) {
          System.out.println(Arrays.toString( sqr[r]));
       }

       int[][] tri;
       tri = new int[5][];        
       // note: only allocates number of columns, each row still needs to be defined. 

       for (int r=0; r < tri.length; r++) 
       {
	   tri[r] = new int[r+1];  // Allocate each row with differing size
       }

       System.out.println("-------------------------------------");

       System.out.println("Here is the tri array:");
       for (int r=0; r<tri.length; r++) {
          System.out.println(Arrays.toString( tri[r]));
       }

       System.out.println("-------------------------------------");

       int [] [] magicSquare = { {8, 1, 6} , {3, 5, 7}, {4, 9, 2} };

       int sum;
       for (int r=0; r < magicSquare.length; r++) 
       {
	   sum=0;
           for (int j=0; j < magicSquare[r].length; j++) 
	       sum +=  magicSquare[r][j];
	   
           System.out.println("Sum of row ["+ r + "] = " +sum );
       }
       for (int c=0; c < magicSquare.length; c++) 
       {
	   sum=0;
           for (int j=0; j < magicSquare.length; j++) 
	       sum +=  magicSquare[j][c];
	   
           System.out.println("Sum of column ["+ c + "] = " +sum );
       }

       sum=0;
       int sum2=0;
       for (int r=0; r < magicSquare.length; r++) 
       {      
	   sum += magicSquare[r][r];
	   sum2 += magicSquare[magicSquare.length-r-1][r];
       }
       System.out.println("Sum of diagonal 1 = " +sum );
       System.out.println("Sum of diagonal 2 = " +sum2 );
	       

       System.out.println("-------------------------------------");

       int nRows = 8;
       tri =  pingalasTri(nRows);

       System.out.println("And Here is Pingala's triangle:");
       for (int i=0; i<nRows; i++)
           System.out.println(Arrays.toString( tri[i]));
   }

    /** PINGALA'S TRIANGLE

       Sanskrit sounds can be Long (L), as in AA or Short (S), as in a. 

       The following question was studied around 400BC by the Sanskrit
       grammarian Pingala in his text "ChhandaShAstra": how many patterns
       can be formed from a given number of syllables?  

       For example, if there are 3 syllables, we can have all L's, all S's,
       or some mixture of L's and S's:

       SSS + SSL SLS LSS + SLL LSL LLS + LLL
       1        3              3          1    : total = 8

       Similarly, for four syllables, we have
       1 meter of four short syllables
       4 meters of three shorts and a long
       6 meters of two shorts and two longs
       4 meters of one short and three longs
       1 meter of four longs

       Note the pattern emerging:

       1 note	= 2 patterns        1 1   
       2 notes	= ? patterns   	   1 2 1  
       3 notes	= 8 patterns 	  1 3 3 1 
       4 notes	= 16 patterns	 1 4 6 4 1
       5 notes	= ? patterns    
       6 notes	= ? patterns    

       This is the Pingala's triangle, also known as the Pascal's Triangle. 
       This routine generates a 2D array that is the Pingala's triangle, 
       upto int n. 

    */

    public static int[][] pingalasTri(int n)
    {
        int[][] tri = new int [n][];
	for (int i = 0; i< n; i++)
	{
	    tri[i] = new int[i+1];
	    for (int j = 0; j<i+1; j++)
	    {
		tri[i][j] = (int) nCr(i,j);
	    }
	}
	return tri;
    }	    

    public static long nCr(int n, int k) 
    {
	long result = 1;
	int a=n; int b=1;
	while(a >= n-k+1)
	    {
		result = result*a; 
		while ((result%b==0) && (b<=k))
		{
		    result = result/ b;
		    b++;
		}
		a--;
	    }
	return result;
    }
}