//*** 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.
*/

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

class Direction
{
    static int RIGHTvalue;    
    static int DOWNvalue;
    String valuesSet;
    static int currentPosX;
    static int currentPosY;
    static boolean successfulFinish=false;
    static int[][] matrix;
    
    enum Directions
    {
        DOWN(DOWNvalue), RIGHT(RIGHTvalue);
        int size;
            
        Directions(int size)
        {
            this.size=size;
        }
    }
    
    public Direction(String valuesSet, int[][] matrix)
    {
        this.valuesSet=valuesSet;
        this.matrix=matrix;
        moves();
    }
    
    public void moves()
    {
        String[] numbers = valuesSet.split(",");
        successfulFinish=true;
        System.out.println("\n\n"+ "{"+valuesSet + "}"+  "   will be evaluated against the " + matrix[0].length + "x" + matrix.length + " matrix********");
        
        for (int t=0; t<numbers.length; t++)
        {
            System.out.println("You are currently at " + "["+currentPosY+"]"+"["+currentPosX+"]" + " on the matrix");
            
            if (t%2==0)
            {
                DOWNvalue = Integer.valueOf(numbers[t]);
                System.out.println("Performing this movement: " + "(" + Directions.DOWN + "):  " + DOWNvalue);
                
                if (currentPosY + DOWNvalue <matrix.length)
                {
                    System.out.println("Successfully moved " + DOWNvalue + " downwards");
                    currentPosY = currentPosY +  DOWNvalue;
                }
                else
                {
                    System.out.println("MOVEMENT IS OUT OF BOUNDS");
                    successfulFinish=false;
                }
            }
            else
            {
                RIGHTvalue=Integer.valueOf(numbers[t]);
                System.out.println("Performing this movement: " + "(" + Directions.RIGHT + "):  " + RIGHTvalue);
                
                if (currentPosX + RIGHTvalue <matrix[0].length)
                {
                    System.out.println("Successfully moved " + RIGHTvalue + " to the right");
                    currentPosX = currentPosX +  RIGHTvalue;
                }
                else
                {
                    System.out.println("MOVEMENT IS OUT OF BOUNDS");
                    successfulFinish=false;
                }
            }//end of else  for else-if statement...
        }//end of for (int t=0; t<val.length; t++)
            
        System.out.println("********DECISION!!!*****************");
        System.out.println("You are currently at " + "["+currentPosY+"]"+"["+currentPosX+"]" + " on the matrix");
        System.out.println("************************************");
            
        if (currentPosY==(matrix.length-1) && currentPosX==(matrix[0].length-1))
        {
            successfulFinish=true;
            System.out.println("*****Successful: " + valuesSet);
        }
            currentPosX=0;
            currentPosY=0;
    }  //end of method
}  //end of class

class Staircase
{
    static int subsetEntry=0;
    static int k;
    int[] S;
    static int[][] matrix;
    int p;
    int total;
    int cycles=0;
    int maxRValue;
    static int totalcycles=0;
    static int difference = 0;
    static int i=0;
    static List <String> backupValuesSet = new ArrayList<>();
    
    Set<String> st;
    Random rand = new Random();
    static String[] valuesSet;
    String []backupValuesSetBeforeModification;
    
    public Staircase(long combinations, int[] X, int r, Set<String> st, int maxRValue, int[][] matrix, int maximumLengthMoves)
    {
        this.k=maximumLengthMoves;
        this.matrix=matrix;
        this.S=S;
        this.st=st;
        this.maxRValue=maxRValue;
        System.out.println("Combinations: " + combinations);
        StringJoiner sj = new StringJoiner(",");
        StringJoiner sj1 = new StringJoiner(",");
        int currentSetSize=0;
        int newSetSize;
        int q;
        int steps;
        boolean allSameDigit=true;
        String subsetIntToString="";
        int countSameNumber=0;
        int pos=0;
        int previousI=0;
        int n=0;
        
        for (int i: X)
        {
            subsetIntToString =  Integer.toString(i);
            if (pos>0)
            {
                if (previousI!=i )
                {
                    allSameDigit=false;
                }
            }
            previousI=i;
            pos++;
        }
        
        do
        {
            sj1.add(subsetIntToString);
            countSameNumber++;
        }while(countSameNumber<(maxRValue/X[0]));
        
        if (allSameDigit)
        {
            System.out.println("\nk is equal to: " + k);
            System.out.println("This is the solution: " +  sj1.toString());
            System.exit(0);
        }
        
        System.out.println("*************INITIAL VALUE OF  CYCLES: " + cycles);
        
        do
        {
            for (q=0; q<r;q++)
            {
                p= rand.nextInt(X.length);
                steps = X[p];
                sj.add(Integer.toString(X[p]));
                currentSetSize=st.size();
                total=total+steps;
                
                if (total==k)
                {
                    st.add(sj.toString());
                }
                
                if (q==r-1)
                {
                    sj = new StringJoiner(",");
                    total=0;
                }
            }
            
            if (total>k)
            {
                total=0;
                sj = new StringJoiner(",");
            }
            
            newSetSize = st.size();
            
            if (newSetSize>currentSetSize)
            {
                
            }
            cycles++;
            totalcycles++;
            
        }while (cycles<combinations*1000);
        //}while (cycles<70);
        
        valuesSet = st.toArray(new String[st.size()]);
        backupValuesSetBeforeModification = st.toArray(new String[st.size()]);
        
        for (String m: backupValuesSet)
        {
            n=0;
            do
            {
                if (m==valuesSet[n])
                {
                    valuesSet[n]="ALREADY PROCESSED";
                }
                
                n++;
                
            }while (n<valuesSet.length);
        }
        
        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());
        
        backupValuesSet= new ArrayList<>(Arrays.asList(backupValuesSetBeforeModification)); 
        
        for (int entry=0; entry<valuesSet.length; entry++)
        {
            if (valuesSet[entry]!="ALREADY PROCESSED")
            {
                //if it completes a successful move...
                if (startToFinish(valuesSet[entry]))
                {
                    subsetEntry++;    //static variable, it will keep track of number successful combinations
                    System.out.println(valuesSet[entry] + "    Subset: " + subsetEntry  + "  at cycle number: " + totalcycles +"\n");
                }
            }
        }
        
        System.out.println("There are: " + (subsetEntry*2) + " possibilities SO FAR");
        System.out.println("The DOWN and RIGHT can be inversed along its path for alternate solution");
            
        difference = newSetSize;
        
    }  //end of constructor...
    
    public static boolean startToFinish(String valuesSet)
    {
        Direction d = new Direction(valuesSet, matrix);
        return d.successfulFinish;
    }
}  //end of staircase class...
        
        
public class Combination
{
    static Staircase sc;
    
    public static void main(String[] args)
    {
        System.out.println("Welcome to Online IDE!! Happy Coding :)");
        int originalNumber=0;
        int n=originalNumber;
        int r;
        Set <String> s = new HashSet<>();
        int[][] matrix = new int[][]{
                                {0,0,0,0,0},
                                {0,0,0,0,0},
                                {0,0,0,0,0},
                                {0,0,0,0,0},
                                {0,0,0,0,0},
                                };
    
        int [] X = new int [matrix[0].length-1];
        
        for (int k=0; k<matrix[0].length-1; k++)
        {
            X[k]= k+1;
        }
        System.out.println("These are possible moves in: " + matrix.length + "x" + matrix[0].length + " matrix:\t" +   Arrays.toString(X));
        int maximumLengthMoves = (matrix.length-1) + (matrix[0].length-1);
        System.out.println("Fixed number moves from START to END: " + maximumLengthMoves);
    
        int counter=0;
        int minimum;
        int maxRValue;
        Map <Integer, Long> m;
        n=X.length;
        originalNumber=n;
        m= new HashMap<>();
        minimum=X[0];

        for (int i=0; i<X.length;i++)
        {
            if (X[i]<minimum && X[i]!=0)
            {
                minimum=X[i];
            }
        }
        maxRValue=(maximumLengthMoves)/minimum;
        System.out.println(Staircase.k);
        System.out.println(minimum);
    
        if (maxRValue>=64)
        {
            System.out.println("Value of r=" + maxRValue + " is too high computationally. It will be reduced to: " + (maxRValue-1));
        }
        
        System.out.println("Maximum r value: " + maxRValue);
        
        for (r=0; r<=maxRValue+1; r++)
        {
            System.out.println("\n***COMBINATIONS*** (WITH REPLACEMENT)");
            System.out.println("C^R(n + r) = " + "(n+r-1)! / r!(n-1)!");
            System.out.println("C^R(" + n+","+r+") = " + (n+r-1)+ "!" + " / " + r+"!"+"("+(n-1)+")!");
            sc = new Staircase (Combinations (n,r,originalNumber, m), X, r,s, maxRValue, matrix, maximumLengthMoves);
        }
    
        /*
        System.out.println("\n\n*************ALL UNIQUE ENTRIES*************");
        Iterator iterator = sc.st.iterator();
        while (iterator.hasNext())
        {
            System.out.println(iterator.next());
            counter++;
        }
    
    */
        //System.out.println(counter + " unique combinations");
        
        if (FoundSubset()==null)
        {
            System.out.println("No Solution found");
        }
    }//end of main method
    
    public static String FoundSubset()
    {
        try
        {
            if (sc.valuesSet[0].isEmpty())
            {
                return null;
            }
        }
        catch (ArrayIndexOutOfBoundsException e)
        {
            return null;
        }
        return "";
    } //end of method


    public static long Combinations (int n, int r, int originalNumber, Map factorialResults)
    {
        long result=0;
        int denominator1;
        int denominator2;
        int Numerator=n+r-1;
        int zero=0;
        long zeroFactorial = 1;
    
        if (originalNumber==0 && r==0)
        {
            System.out.println("n and r can not both be equal to zero");
            return 0;
        }
    
        if (originalNumber==0 && originalNumber+r-1<r)
        {
            System.out.println("n+r-1 must be > or = to r");
            return 0;
        }
        if (Numerator>=1)
        {
            result = ((n+r-1)* (Combinations (n-1, r,originalNumber, factorialResults)));
            factorialResults.put(Numerator,result);
            
            if (n==originalNumber)
            {
                denominator1 = r;
                denominator2 = originalNumber-1;
                factorialResults.put(zero,zeroFactorial);
                
                if (factorialResults.containsKey(denominator1) && factorialResults.containsKey(denominator2))
                {
                    long returnValue = result / ((long)factorialResults.get(denominator1) *(long)factorialResults.get(denominator2));
                    return returnValue;
                }
            }
            return result;
        }  //end of if  Numerator>=1
        return 1;
    }  //end of combinations method.
}  //end of class Combination