//*** 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=true;
    static String alternatingDownRight = "Alternating DOWN => RIGHT => DOWN .......";
    static String alternatingRightDown = "Alternating RIGHT => DOWN => RIGHT.......";
    static String[] completedPaths = new String [1000];
    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)
    {
        this.valuesSet=valuesSet;
        this.matrix=matrix;
        movesAlternateDownRight();
    }
    
    public Direction(String valuesSet, String alternateRightDown, int[][] matrix)
    {
        this.valuesSet=valuesSet;
        this.matrix=matrix;
        movesAlternateRightDown();
    }
    
    public void decision(String movementPattern)
    {
        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);
                count++;
                completedPaths[count] = (valuesSet +  "    Subset: " + count + "  " + movementPattern);
            }
            currentPosX=0;  
            currentPosY=0;
    }
    
    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);
        }
        
        if (!outBounds)
        {
            for (int i=1; i<=DOWNvalue; i++)
            {
                if (matrix[currentPosY+i][currentPosX]==1)
                {
                    System.out.println("hit a wall at" + "["+(currentPosY+i) +"]" + "[" +currentPosX +  "]" + " - discard sequence" );
                    successfulFinish=false;
                    decision(movementPattern);
                    i=DOWNvalue;
                }       
            }
        }
        
        if (currentPosY + DOWNvalue <matrix.length && successfulFinish)
        {
            System.out.println("Successfully moved " + DOWNvalue + " downwards");
            currentPosY = currentPosY +  DOWNvalue;
            
            if ((t==numbers.length-1))
            {
                decision(movementPattern);
            }
        }
    }
    
    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);
        }
        if (!outBounds)
        {
            for (int i=1; i<=RIGHTvalue; i++)
            {
                if ((matrix[currentPosY][currentPosX+i]==1))
                {
                    System.out.println("hit a wall at" + "["+currentPosY +"]" + "[" +(currentPosX+RIGHTvalue) +  "]" + " - discard sequence" );
                    successfulFinish=false;
                    decision(movementPattern);
                    i=RIGHTvalue;
                }           
            }
        }
        
        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);
            }
        }
    }
    
    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++)
        {
            System.out.println("Index: " + t  + " of: " + valuesSet);
                
            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 else  for else-if statement...
            }
        }   //end of for (int t=0; t<val.length; t++)
    }  //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 (startToFinishRightDown(valuesSet[entry]))
                {
                    subsetEntry++;    
                    System.out.println(valuesSet[entry] + "   " + "("+Direction.alternatingRightDown+")" +"    Subset: " + subsetEntry  + "  at cycle number: " + totalcycles +"\n");
                }
                if (startToFinishDownRight(valuesSet[entry]))
                {
                    subsetEntry++;
                    System.out.println(valuesSet[entry] + "   " + "("+Direction.alternatingDownRight+")" +"    Subset: " + subsetEntry  + "  at cycle number: " + totalcycles +"\n");
                }
            }
        }
        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);
        return d.successfulFinish;
    }
        
    public static boolean startToFinishDownRight(String valuesSet)
    {
        Direction d = new Direction(valuesSet, matrix, "DownRight");
        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,1,0,0,0},
                                {1,0,0,0,0,0,0,0,0,0},
                                {0,0,1,0,1,1,1,1,0,1},
                                {0,0,1,0,0,1,1,0,0,0},
                                {0,0,1,0,0,0,1,1,1,0},
            */
                                {0,0,0,0,1,0,0,0},
                                {1,0,0,0,0,0,0,0},
                                {0,1,0,1,1,1,0,1},
                                {0,1,0,1,1,0,0,0},
                                {0,1,0,0,1,1,1,0},
                                
                                //{0,0,1},
                                //{0,0,1},
                                //{1,0,0},
                              
                                 //{0,0,1},
                                 //{0,1,1},
                                 //{1,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;
    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+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");
    
    System.out.println("\n***********SOLUTIONS************");
    for (String str: Direction.completedPaths)
    {
        if(str!=null)
        {
            System.out.println(str);
            solutionFound=true;
        }
    }
    if (!solutionFound)
    {
        System.out.println("NO solutions");
    }
    }//end main 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