//*** CODE ***
/*
Online Java - IDE, Code Editor, Compiler
Online Java is a quick and easy tool that helps you to build, compile, test your programs
online.
*/
// This has been created to ensure I can utilize any random functions more efficiently.
// It is a creation of the combinations (with replacement) calculator.
// It has used techniques I learnt including recursion and also memoization to speed up execution.
// I will incorporate this into Java applications I created previously..
//TEST CASES
// All done on My Approach

//NOTE THE CODE IS MASSIVELY COMMENTED OUT AND PRESERVED CRITICAL COMMENTS ON THE SCREEN....

import java.math.*;
import java.util.*;

class Staircase
{
    int r;
    
    static int triangleNumber;
    static long permutations;
    static StringJoiner sj;
    static StringJoiner valuesTriangle = new StringJoiner(",");
    static boolean processedMax=false;
    
//    static int permutationsInInt =  permutations.toInteger();
    static int numberTriangles;
    static int [][][] triangle;
    
    static String [][] outcomes;
   
    static int[] max = new int[2];  //can not re-initialise this.
    static int o=0;
    
    static int subsetEntry=0;   //this is required to output the subset entry
    
    boolean executeOnce=false;  //ensure condition will only execute once.. 
    //if numbers are heterogeneous, the full code execution will prevail...
    
    int[] S; // this is the array containing the steps
    int p; // this is random number generated
    int cycles=0; // this is number of cycles completed for each c(n,r).. It is reset each time....
    int maxRValue;  // this is defined here also since there are limitations which is up to r=63
    
    static int totalcycles=0;   // this is useful to know the total cycles... Its static, so will keep running..
    
    //this has to be static since class is instantiated on each combination (n,r)
    //it needs to mantain value to ensure the offset from which the successful subsets are returned are not repeated...
    static int difference = 0;  //used to get difference in set size and offset to display results on screen...
   
    //it has to be static since every time the class is instantiated, it will lose its value otherwise....
    //this is now a good indicator to see the cycle on the screen and occurrence of subset totalling k.
    static int i=0;
    
    static String outcome;
    
    static List <String> backupValuesSet = new ArrayList<>();
    
    String temp;
    
    Set<String> st; // this will contain the combinations for achieving total k
    Random rand = new Random(); // object created of type Random.
    // there is no sense of X getting smaller since its with replacement....
    // need to only add the stringJoiner (converted into string) into the set if the total is equal to N
    // if total goes over, it will continue adding until all cycles for C^R (n,r) has finished
    // Combinations is total of combinations for C^R(n,r)
    // r is the sample size... This can exceed n.. but there is also limit to r....
    
    static String[] valuesSet;   // this will be used to hold all values from the set... this will be modified..
    String []backupValuesSetBeforeModification;  // this will hold all values from set... (this will never be modified...)
    
    public Staircase(long permutations, int[] X, int r, Set<String> st, int[][][] triangle, int numberTriangles, String [][] outcomes)
    {
        this.outcomes=outcomes;
        this.permutations=permutations;
        this.numberTriangles=numberTriangles;
        this.r=r;
        this.triangle=triangle;
        this.S=S;
        this.st=st;
        this.maxRValue=maxRValue;
        
        
        System.out.println("Permutations: " + permutations);
        System.out.println(outcomes[0].length);
        
        sj = new StringJoiner(","); // creating StringJoiner for the final output
        boolean invalidIndex=false;
        
        int currentSetSize=0; // holds size of set before entry added
        int newSetSize; // holds size of set after entry added
        //int count=0;
        
        
        int stepsCounter=0;
        
        
       
        int steps; // it will hold value of step generated randomly from r
       
        String subsetIntToString=""; //  since it needs to add number back into the StringJoiner, 
        //it has to be converted into a String first....
        
        int pos=0;  // used to index array X. Required so that it can check if previous number holds same value...
        //it will only increment at end of the loop to ensure correct validation check...
        
        int previousI=0; //value of previous number in X array.. used to set the correct boolean as to whether all numbers
        //are same in X[]
        //As per my documentation, there is a serious issue if all the numbers are same in selection..
        // Since it will create a massive hindrance since the r value in combinations will be driven too high...
        //code below will ensure scenario does not arise...
        
        int n=0;  // this is index used when comparing the valuesSet with backupValuesSet
       
        //System.out.println("*********************************");
        
        System.out.println("*************INITIAL VALUE OF  CYCLES: " + cycles);
        
        do
        {
            for (int q=0; q<r;q++) // processing up to r only since this is the sample size
            {
                if (invalidIndex)
                {
                    sj=new StringJoiner(",");
                    invalidIndex=false;
                    stepsCounter=0;
                }
                
                //in ideal world, it would need something like this
                //do while loop since we know that ...
                //on a row 0:  [0][0][0]
                //on a row 1:  [1][0][0]  and [1][0][1]
                //the last index available is less than or equal to row number..
                //i.e  it will not attempt to perform moves such as (1,1,0)
                //since indexing  [0][0][1] is invalid.
                
                //we know that Set size is governed based on P(3,3) = 27
                //if we try to reduce number of entries.. the scope of permutation will
                //be much larger than expectations.
                //since there are no permutations to fulfill 27.
                
                //we can perhaps examine this closer
                //since  (1,X,X) or  (2,X,X) are of no use whatsoever = 66% entries = 18 entries...
                //Also   (0,2,X) = 1 entry
                
                //I am examining this in my documentation..
                
                //do
                //{
                //System.out.println("generated: " + rand.nextInt(X.length));
                //System.out.println(q);
                //p= rand.nextInt(X.length); // if length 3, it will give index numbers 0-2... This is suitable
                int temp1 = rand.nextInt(X.length);
                
                  if (temp1<=q)
                {
                    //System.out.println("\ntemp1: " + temp1);
                    //System.out.println("q: " + q);
                    
                    //System.out.println("generated: " + rand.nextInt(X.length));
                    p= temp1;
                    stepsCounter++;
                    //rand.nextInt(X.length); 
                }
                else
                {
                    //q=0;
                    
                    //it also needs to set a flag here...
                    //since the q=0 will only take effect once it has reached
                    //end of execution of the for loop..
                    invalidIndex=true;
                    
                    break;
                    
                   
                    
                }
                
            //}while (p>q);
                
                
                steps = X[p]; // step value
                //System.out.println("\nrandom number from original subset is : " + steps);
                sj.add(Integer.toString(X[p])); //adds the step into StringJoiner
                
                //stepsCounter++;
                
                //if ()
                
                currentSetSize=st.size(); //current size of set
                
                //System.out.println("This is performing: " + (q+1) +" of " + r + "(r)");

                //reminding end user value N and running total
                //System.out.println("TOTAL HERE: " + total + "    k Value is: " + k);
                
                if (q==r-1) // if its on the last loop..
                {
                    System.out.println("value of stepsCounter: " + stepsCounter);
                //This would be the point where code is changed.
                //it would only perform this condition.
                st.add(sj.toString()); // it will only add it if the conditions are met above (size of r and Total=N)
                stepsCounter=0;
                sj = new StringJoiner(",");
                }
            }
            
            newSetSize = st.size(); // new set size
            
            if (newSetSize>currentSetSize) //if larger, i.e a new combination, it will inform end user..
            {
                //System.out.println("This has been added into the set:");
                
            }
            cycles++; //increases cycles
            //it is increasing cycle every time its on the end of completing do while loop
            
            //grand total of cycles completed in the code....
            totalcycles++;
            
            //System.out.println("Number of cycles: " + cycles + "\n");
            // can not set this to a certain set size... since it is giving total combinations (with replacement) and not 
            // related to placing items in certain order in which once combinations are known.
            // There are most likely distributions in statistics which might assist with the cycles...
            // Otherwise, this can only be placed in speculatively like throwing dice (a fixed time) and getting total....
            //the safest option for the maximum iterations is combinations x 10, but its subjective.
            //but in reality there is no guarantee that it would have covered all combinations at least once in that duration...
        
        }while (cycles<permutations*40);
        //}while (cycles<70);
        
        // this is now getting the String in the set...
        //initially i will be 0 and it will output entire contents of the set..
        //once it has completed it first time, it will continue from its last position.
        //this is taken to be difference.... 
        //however since this has failed, I opted for a new techniques.
        
        //At this point in time, both are identical copies....
        valuesSet = st.toArray(new String[st.size()]);
        backupValuesSetBeforeModification = st.toArray(new String[st.size()]);
        
        // This next part was pivotal to ensure my technique was correct.
        //the backupValuesSet is populated below in following technique...
        //basically it is getting an untouched version of the String array above.
        //it is basically copy of the set which occurs several lines down....
        //backupValuesSet= new ArrayList<>(Arrays.asList(backupValuesSetBeforeModification));
        //So as expected when it hits hit and the set is empty, it will always show no content....
        //the reason why backupValuesSet is occuring after the valuesSet is since it can only make a backup once
        //valuesSet has been processed.
        //This also creates an effect of incremental backup in which backupValuesSet is one interation behind the valuesSet.
        //For this exercise it is purposeful since backupValuesSet can be searched against valuesSet
        //for duplicate values and eradicate them....
        
        System.out.println("******************Contents of the backup set");
        
        for (String g: backupValuesSet)
        {
            System.out.println(g);
        }
        
        
        ///again this is copy of the set.... It can be expected that once it starts populating, the valuesSet
        //will always be larger than backupValuesSet
        
        System.out.println("******************Contents of the valuesSet");
        
        for (String g: valuesSet)
        {
            System.out.println(g);
        }
        
        
        
        //checking every value in the backupValuesSet and setting it to ALREADY PROCESSED in 
        //valuesSet if it appears....
        
        for (String m: backupValuesSet)
        {
            n=0;
            do
            {
                if (m==valuesSet[n])
                {
                    System.out.println("Match found in backupValuesSet: " + m);
                    System.out.println("Match found in valuesSet: " + valuesSet[n]);
                    
                    valuesSet[n]="ALREADY PROCESSED";
                    System.out.println("valuesSet[n]" + " set to " + valuesSet[n]+"\n");
                    
                }
                
                n++;
                
            }while (n<valuesSet.length);
            //keep processing for all items in valuesSet
        }
        
        
        System.out.println("*************NEW VALUE CYCLES: " + cycles);
        System.out.println("*************RUNNING TOTAL CYCLES: " + totalcycles);
        
        System.out.println("***PROCESSING SET AT INDEX: " + (difference));
        System.out.println("**ENDING AT INDEX:***** " + st.size());
        
        
        //need be careful with this code, since if there is "ALREADY PROCESSED IN THE VALUESSET"
        //it will copy it again into the backupValuesSet
        //backup has to be restored from backupValuesSetBeforeModification.
        
        backupValuesSet= new ArrayList<>(Arrays.asList(backupValuesSetBeforeModification)); 
        
        
        //this now processes each String in the ValuesSet (which will be Strings not outputted yet)
        for (int entry=0; entry<valuesSet.length; entry++)
        {
            if (valuesSet[entry]!="ALREADY PROCESSED")    //as per above, it needs bypass these
            {
                subsetEntry++;    //static variable, it will keep track of combinations in the subset...
                
            
            System.out.println(valuesSet[entry] + "    Subset: " + subsetEntry  + "  at cycle number: " + totalcycles);
            System.out.println("********");
            System.out.println(triangleNumber);
            System.out.println(permutations);
            
            
            obtainMoves(valuesSet[entry], numberTriangles, permutations, outcomes);
            }
        }
        //on first time it reaches above,    currentSetSize will be 0....
        //next time, currentsetSize will be previously newSetSize....
        //so it will perform incremental difference...
        
        //Set is zero index,  so it would have completed 5 items at  s.get(4)
        //s.size() is actual length...
        //if set size was 5 after  first  C(n,r) ,  it would have processed 0,1,2,3,4
        //difference would  be  5-0 = 5
        //so this is correct start point.....
        
        difference = newSetSize;
        
        }  //end of constructor...
        
        public void obtainMoves(String moves, int numberTriangles, long permutations, String[][] outcomes)
        {
            
            int[] nMoves = new int [r];
            int i=0;
            StringTokenizer sTok = new StringTokenizer(moves,",");
            
            while (sTok.hasMoreTokens())
            {
                temp=sTok.nextToken();
                
                nMoves[i]= Integer.valueOf(temp);
                i++;
            }
            
            performMoves(nMoves,numberTriangles,permutations, outcomes);
        }
        
        public void performMoves(int[] nMoves, int numberTriangles, long permutations, String [][]outcomes)
        {
            boolean invalidSubset=false;
            int total=0;
            
//            System.out.println("***There are triangles configured*** : " + numberTriangles);
            
            //This is counting through triangles
            for (int j=0; j<triangle[0].length; j++)
            {
                System.out.println("TRIANGLE " + (j));
            
            for (int k: nMoves)
            {
                //System.out.println("MOVES STORED: " + k);
                System.out.println("Elements in: " + i + " row of triangle:" + j);
                
                //it is expecting these to remain consistent:
                //triangle[i][j][k]
                //triangle[i][j][k]
                //triangle[i][j][k]
                
                System.out.println("Value at triangle: " + j + "  [" + i +  "]" + "[" +j + "]" + "[" +k + "]" + ":  "  + triangle[i][j][k]);
                
              total=triangle[i][j][k] + total;
              valuesTriangle.add(Integer.toString(triangle[i][j][k]));
              
              i++;  
            }
            
            i=0;
            
            System.out.println("*******TOTAL: " + total +"\n");
            
            processedMax=false;
            
            outcome = "Triangle: " + j +  "     Subset: " + subsetEntry + "  " +"(" + valuesTriangle + "):  " + "Maximum value: " + total;
            valuesTriangle = new StringJoiner(",");
            
             if (total>max[j])
            {
                max[j]=total;
                
                //can not do this!!!
                //it will also wipe out data for other triangles...
                //outcomes = new String[2][(int)permutations];
                
                //need to wipe max information for that given triangle ONLY
                //need to wipe value in all rows for that given triangle.
                
                int index=0;
                
                System.out.println(numberTriangles);
                System.out.println(permutations);
                
                //outcomes = new String[triangleNumber][(int)permutations];
                System.out.println("test");
                System.out.println(outcomes[0].length);
                System.out.println(outcomes[1].length);
                
                    do
                    {
                        System.out.println("val j: " + j);
                        System.out.println("val index: " + index);
                        System.out.println("val perm: " + permutations);
                        System.out.println("val length row: " + outcomes[j].length);
                        
                        outcomes[j][index]=null;
                        index++;
                        
                    }while (index<permutations);
                    
               
                index=0;
                
                outcomes[j][0]=outcome;
                System.out.println("IN HERE: " + outcomes[j][0]);
                o++;
                processedMax=true;
            }
            
            if (total==max[j] && !processedMax)
            {
                
                outcomes[j][o] = outcome;
                System.out.println("IN HERE1: " + outcomes[j][o]);
                max[j]=total;
                o++;
            }
            
            valuesTriangle=new StringJoiner(",");
            total=0;
            }
            
            for (int c: max)
            {
                System.out.println("Highest total " + "triangle(" + triangleNumber+")" + "is: " + max[triangleNumber]);
                triangleNumber++;
            }
            triangleNumber=0;
            
            //the total presented here before value cleared...
            
            //at moment, just focussing on the first triangle...
            //expecting it to be  1, 2, 3  up to (n+1)
            
        }
}

public class Permutation
{
    static int triangleNumber=0;
    
    static Staircase sc; //object of type Staircase
    
    static int numberTriangles;
    
     
    
    
    public static void main(String[] args) 
    {
        System.out.println("Welcome to Online IDE!! Happy Coding :)");
        
        
    Set <String> s = new HashSet<>(); // it will contain all combinations...
    int n;
    int r;
    int [] X = new int []{0,1,2};  
    // we know on top row of triangle 0 index will cover only element
    //we know on 2nd row, indexes are 0 and 1
    //we know on 3rd row, index is 0,1,2
    
    int [ ][ ][ ] triangle = new int[ ][ ][ ] { 
                                        { {1},  {2}  }, 
                                        { {2,3}, {5,6}  },
                                        { {1,5,1}, {7,3,2}  },
                                      };
    
    numberTriangles=triangle[0].length;
    
    
    int counter=0; // used in iterating set to keep count..
    
    //need to understand this example will use replacement
    //since 0 index for instance is applicable in each row.
    
    Map <Integer, Long> m; // this can stay outside loop since its not impacted by size of n and r
    
    n=X.length; //length of the array X of steps
    
    //System.out.println("Staircase size is:  " + Staircase.k);
    //System.out.println("Steps are: " + Arrays.toString(X));
    
    m= new HashMap<>(); //new instance is required to start process again...
    
     r=n;
     
    long perms = Permutations(n,r);
    
    String [][] outcomes = new String[numberTriangles][(int)(perms)];
     
     
     //System.out.println("VALUE of r: " + r);
     
     //it will select an index to represent each row...
     //to ensure that it fulfills, the challenge, it will try
     //value in the set, extract values.. And try numbers in that order
     //and progress through the triangle..
    
        System.out.println("***PERMUTATIONS***(WITH REPLACEMENT)");
        System.out.println("PR(n,r) = nr");
        System.out.println(Permutations (n,r));
        
        System.out.println("PASSING THIS ACROSS: **********");
        System.out.println(numberTriangles);
        System.out.println(Permutations (n,r));
    
    //creates instance of Staircase and main execution of code...
    sc = new Staircase (Permutations (n,r), X, r,s, triangle, numberTriangles, outcomes);

    System.out.println("\n\n*************SUMMARY HIGHEST RESULTS*************");
    
    System.out.println("*******TRIANGLES*********");
    for (int q=0;q<triangle.length;q++)
    {
      System.out.println(Arrays.deepToString(triangle[q]));
      triangleNumber++;
    
    }
    
    triangleNumber=0;
    
    do
    {
    for (String str: sc.outcomes[triangleNumber])
    {
        
        if (str!=null)
        {
            
            System.out.println(str);
        }
    }
    triangleNumber++;
    }while(triangleNumber<triangle[0].length);

   
}
    
    public static long Permutations (int n, int r)
    {
        System.out.println("P^R(" + n+","+r+") = " + "Math.pow(n,r)");
        return (long)Math.pow(n,r);
        
    }
}