//*** 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 newSetSize;
    static int counter;
    StringJoiner sj1 = new StringJoiner(",");
    static String coinsCollectedinAllMoves;
    static int [] maximumCoins = new int [5000];
    static String [] storeMinimumCoins = new String [newSetSize+1];
    static String [] storeMaximumCoins = new String [newSetSize+1];
    static int min;
    static int max;
    static int totalCoins;
    static int RIGHTvalue; 
    static int DOWNvalue;
    String valuesSet;
    static int currentPosX;
    static int currentPosY;
    static boolean successfulFinish=true;
    static int FirstCoinDownMove;
    static int FirstCoinRightMove;
    static String alternatingDownRight = "Alternating DOWN => RIGHT => DOWN .......";
    static String alternatingRightDown = "Alternating RIGHT => DOWN => RIGHT.......";
    static String[] completedPaths = new String [5000];
    static int count;
    static String [] numbers;
    static boolean outBounds=false;
    static int[][] matrix;
    
    enum Directions
    {
        DOWN(DOWNvalue), RIGHT(RIGHTvalue);
            
        int size;
            
        Directions(int size)
        {
            this.size=size;
        }
    }
    
    public Direction(String valuesSet, int[][] matrix, String alternateDownRight, int newSetSize)
    {
        this.valuesSet=valuesSet;
        this.matrix=matrix;
        this.newSetSize=newSetSize;
        movesAlternateDownRight();
    }
    
    public Direction(String valuesSet, String alternateRightDown, int[][] matrix, int newSetSize)
    {
        this.valuesSet=valuesSet;
        this.matrix=matrix;
        this.newSetSize=newSetSize;
        movesAlternateRightDown();
    }
    
    public void decision(String movementPattern, String coinsCollectedinAllMoves)
    {
        System.out.println("********DECISION!!!*****************");
        System.out.println("You are currently at " + "["+currentPosY+"]"+"["+currentPosX+"]" + " on the matrix");
        System.out.println("************************************");
        
        successfulFinish=false;
        
        if (currentPosY==(matrix.length-1) && currentPosX==(matrix[0].length-1))
        {
            successfulFinish=true;
            System.out.println("*****Successful: " + valuesSet);
            
            completedPaths[count] = (valuesSet +  "    Subset: " + count + "     " +  "Coins collected{"+Direction.coinsCollectedinAllMoves+"}" + "   " +  "   TOTAL COINS: " + totalCoins + " " + "("+movementPattern+")");
            maximumCoins[count] = totalCoins;
            getMinimumMaximumCoins();
                
            System.out.println("Stored total coins: " + maximumCoins[count]);
            count++;
        }
        currentPosX=0;
        currentPosY=0;
        
        if (!successfulFinish)
        {
            totalCoins=0;
        }
        
        sj1 = new StringJoiner(",");
        coinsCollectedinAllMoves=" ";
        }
        
        public static void getMinimumMaximumCoins()
        {
            max=maximumCoins[0];
            min=maximumCoins[0];
        
            System.out.println("*******MINIMUM AND MAXIMUM OF ALL THE COINS COLLECTED  [Start Position => End Position]******");
    
            storeMinimumCoins = new String[5000];
            storeMaximumCoins = new String[5000];
            
            for (int val: maximumCoins)
            {
                if (val==min && counter!=0)
                {
                    if (counter<maximumCoins.length)
                    {
                        storeMinimumCoins[counter]=Direction.completedPaths[counter];
                    }
                }
                
                if (val==max && counter!=0)
                {
                    if (counter<maximumCoins.length)
                    {
                        storeMaximumCoins[counter]=Direction.completedPaths[counter];
                    }
                }
               
                if (val<min && counter!=0)
                {
                    min=val;
                    storeMinimumCoins = new String[newSetSize];
                    storeMinimumCoins[0]=Direction.completedPaths[counter];
                }
                if (val>max && counter!=0)
                {
                    max=val;
                    storeMaximumCoins = new String[newSetSize];
                    storeMaximumCoins[0]=Direction.completedPaths[counter];
                }
            }
            counter++;
            System.out.println("Minimum Coins is: " +  min);
            System.out.println("Maximum Coins is: " +  max);
        }
        
    public static void finalResults()
    {
        System.out.println("\n\n\nMinimum Coins is: " +  min);
        
        //This is non-functional / giving wrong content...
        //refer to the output in the solutions....
        /*
        for (String s: storeMinimumCoins)
        {
            if (s!=null)
            {
                System.out.println(s);
            }
        }
        */
        System.out.println("\nMaximum Coins is: " +  max);
        
        counter=0; 
        System.out.println("\n\n");
    }
    
    public void movesDown(int t, String movementPattern)
    {
        DOWNvalue = Integer.valueOf(numbers[t]);
        System.out.println("Performing this movement: " + "(" + Directions.DOWN + "):  " + DOWNvalue);
        
        if (currentPosY + DOWNvalue >=matrix.length)
        {
            System.out.println("MOVEMENT IS OUT OF BOUNDS");
            successfulFinish=false;
            outBounds=true;
            decision(movementPattern, sj1.toString());
        }
        if (!outBounds)
        {
            if (t==0)
            {
                FirstCoinDownMove = matrix[currentPosY][currentPosX];
                        
                sj1.add(Integer.toString(FirstCoinDownMove));
            }
            
            for (int i=1; i<=DOWNvalue; i++)
            {
                totalCoins = totalCoins + matrix[currentPosY+i][currentPosX];
                sj1.add( Integer.toString(matrix[currentPosY+i][currentPosX]));
            }
        }
        totalCoins = totalCoins + FirstCoinDownMove;
        FirstCoinDownMove=0;
        coinsCollectedinAllMoves=sj1.toString();
        
        if (currentPosY + DOWNvalue <matrix.length && successfulFinish)
        {
            System.out.println("Successfully moved " + DOWNvalue + " downwards");
            currentPosY = currentPosY +  DOWNvalue;
            
            if ((t==numbers.length-1))
            {
                decision(movementPattern, sj1.toString());
            }
        }
    }
    
    public void movesRight(int t, String movementPattern)
    {
        RIGHTvalue=Integer.valueOf(numbers[t]);
        System.out.println("Performing this movement: " + "(" + Directions.RIGHT + "):  " + RIGHTvalue);
        
        if (currentPosX + RIGHTvalue >=matrix[0].length)
        {
            System.out.println("MOVEMENT IS OUT OF BOUNDS");
            successfulFinish=false;
            outBounds=true;
            decision(movementPattern, sj1.toString());
        }
        
        if (!outBounds)
        {
            if (t==0)
            {
                FirstCoinRightMove = matrix[currentPosY][currentPosX];
                sj1.add(Integer.toString(FirstCoinRightMove));
            }
            for (int i=1; i<=RIGHTvalue; i++)
            {
                totalCoins = totalCoins + matrix[currentPosY][currentPosX+i];
                sj1.add(Integer.toString(matrix[currentPosY][currentPosX+i]));
            }
        }
        totalCoins = totalCoins + FirstCoinRightMove;
        FirstCoinRightMove=0;
        coinsCollectedinAllMoves=sj1.toString();
        
        if (currentPosX + RIGHTvalue <matrix[0].length && successfulFinish)
        {
            System.out.println("Successfully moved " + RIGHTvalue + " to the right");
            currentPosX = currentPosX +  RIGHTvalue;
            
            if ((t==numbers.length-1))
            {
                decision(movementPattern, coinsCollectedinAllMoves);
            }
        }
    }
    
    public void movesAlternateDownRight()
    {
        numbers = valuesSet.split(",");
        System.out.println("\n\n"+ "{"+valuesSet + "}"+  "   will be evaluated against the " + matrix[0].length + "x" + matrix.length + " matrix********");
        System.out.println(alternatingDownRight);    
        successfulFinish=true;
        outBounds=false;
            
        for (int t=0; t<numbers.length; t++)
        {
            if (successfulFinish && !outBounds)
            {
                System.out.println("You are currently at " + "["+currentPosY+"]"+"["+currentPosX+"]" + " on the matrix");
                
                if (t%2==0)
                {
                    movesDown(t, alternatingDownRight);
                }
                else
                {
                    movesRight(t, alternatingDownRight );
                }  //end of else  for else-if statement...
            }
        }   //end of for (int t=0; t<val.length; t++)
    }  //end of method
    
    public void movesAlternateRightDown()
    {
        numbers = valuesSet.split(",");
        System.out.println("\n\n"+ "{"+valuesSet + "}"+  "   will be evaluated against the " + matrix[0].length + "x" + matrix.length + " matrix********");
        System.out.println(alternatingRightDown);    
        successfulFinish=true;
        outBounds=false;
            
        for (int t=0; t<numbers.length; t++)
        {
            if (successfulFinish && !outBounds)
            {
                System.out.println("You are currently at " + "["+currentPosY+"]"+"["+currentPosX+"]" + " on the matrix");
                
                if (t%2==0)
                {
                    movesRight(t, alternatingRightDown);
                }
                else
                {
                    movesDown(t, alternatingRightDown);
                }
            }
        }   //end of for (int t=0; t<val.length; t++)
    }  //end of method
}  //end of class
        

class Staircase
{
    String coinsCollectedinMoveString;
    String subsetCycleInformation;
    String direction;
    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;
    
    static int newSetSize;
    
    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 q;
        int steps;
        boolean allSameDigit=true;
        String subsetIntToString="";
        int countSameNumber=0;
        int pos=0;
        int previousI=0;
        int n=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();
            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 (startToFinishRightDown(valuesSet[entry]))
                {
                    System.out.println (valuesSet[entry] +  "    Subset: " + subsetEntry + "     " +  "Coins collected{"+Direction.coinsCollectedinAllMoves+"}" + "   " +  "   TOTAL COINS: " + Direction.totalCoins   +"  " + "("+Direction.alternatingRightDown+")" );
                    Direction.totalCoins=0;  
                    subsetEntry++;
                }
                if (startToFinishDownRight(valuesSet[entry]))
                {
                    System.out.println (valuesSet[entry] +  "    Subset: " + subsetEntry + "     " +  "Coins collected{"+Direction.coinsCollectedinAllMoves+"}" + "   " +  "   TOTAL COINS: " + Direction.totalCoins +"  " + "("+Direction.alternatingDownRight+")");
                    
                    Direction.totalCoins=0;
                    subsetEntry++;
                }
            } //end of if
        }  //end of for
        
        System.out.println("There are: " + (subsetEntry) + " possibilities SO FAR");
        System.out.println("Tested via alternating DOWN and RIGHT along path and also RIGHT and DOWN");
        difference = newSetSize;
    }//end of constructor...
    
    public static boolean startToFinishRightDown(String valuesSet)
    {
        Direction d = new Direction(valuesSet, "RightDown", matrix, newSetSize);
        return d.successfulFinish;
    }
    
    public static boolean startToFinishDownRight(String valuesSet)
    {
        Direction d = new Direction(valuesSet, matrix, "DownRight", newSetSize);
        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<>();
    
        //this can be defined any dimensions for the L x W
        int[][] matrix = new int[][]{
                        /*
                                {0,0,0,6,0,0,1,0,0},
                                {1,0,0,0,0,0,0,6,0},
                                {0,0,9,0,9,4,1,1,0},
                                {0,0,1,0,0,1,1,9,0},
                                {0,0,1,0,0,0,1,1,1},
                                {4,5,6,3,2,9,9,7,2},
                                {4,9,0,8,7,6,2,1,3},
                         */
                                {0,0,0,6,4},
                                {0,4,0,3,2},
                                {0,0,0,0,6},
                                {0,0,0,0,0},
                              
                                 //{0,0,1},
                                 //{4,1,1},
                                 //{6,9,0},
                                 
                                 //{0,3,1,1},
                                 //{2,0,0,4},
                                 //{1,5,3,1},
                                };
                                
        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=1;
        int minimum;
        int maxRValue;
        boolean solutionFound=false;
    
        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;
        
        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; 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\n***********SOLUTIONS************");
    
        for (String str: Direction.completedPaths)
        {
            if(str!=null)
            {
                System.out.println(str);
                solutionFound=true;
            }
        }
        
        if (!solutionFound)
        {
            System.out.println("NO solutions");
        }
        
        Direction.finalResults();
        System.out.println("\n\n");
    }
    
    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;
        }
        return 1;
    }
}