/*
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.util.Random;
import java.util.*;

interface Movable
{
    Set <String> outcomes = new HashSet<>();
    
    
    public void assignSnakesLadders();
    public void setGrid();
    public void checkSnakesLadder();
    public void defineMoves();
    public void diceThrow();
    public boolean performMove();
    public boolean checkValidMove();
    public boolean everyPossibleDieRoll();
    public void getMinimumMaximumMoves();
    
}


class RandomSnakesLadders extends SnakesLadders implements Movable 
{
    //to hold all enum values....
   
    
    
    int [][][] moves = new int [100][6][2];
    int minimumMoves[] = new int[1000];
    int gridNumber;
    int m;
   
    
    int boardsCompleted;
    
    int totalMoves;
    
    boolean allPreviousCompletedMoves=true;
    int i;
    int j;
    int currentPosition;
    int newPosition;
    int diceValue;
    int [][] Board;
    int count;
    
    //all information stored here is transactional showing how it traverses the board...
    //the content is not equipped to answer smallest number of turns it takes.....
    StringJoiner sj = new StringJoiner(" ");
    
    int grids=100;
    String [] path = new String[1000];
    
    
    public RandomSnakesLadders(PositionSnakesLadders[] psl)
    {
        assignSnakesLadders();
        
    }
    
    //this is using logic described below....
    //since if there is snake head or ladder climb at certain grid locations, it is impossible to have
    //moves from this location. It can also be seen in the grid number breakdown...
    //the 2d array populated of moves...
    //the only purpose is to ensure that every grid is landed on and every move completed from each.
    //it is unrelated to the combinations....
    //testing to see if the random algorithm is satisfactory...
    
    //there is flaw in the method.
    //it is checking if each grid has completed all the Die rolls.
    //for some reason even though I checked to see the below code.
    //Reason is to check if there is an endPos for all the die values...
    // For some reason, the index i still seems to reference psl[m]
    //of exactly where there is a match...
    // This is not overly critical..
    //But as part of the coding, it would be great to know after how many 
    //random simulated attempts that it performed all moves..
    // This would help ascertain difficulty of game etc....
    
    //if snake or ladder not at this position on grid... 
    //if (psl[m].startPos!=i)
    
    //I have even tried to nest do loop inside for loop and vice versa to no avail.
    
    
    public boolean everyPossibleDieRoll()
    {
        //System.out.println("*********MUST BE HERE");
        
        int i=0;
        
       
            
            do{
                //System.out.println("Enum: " + psl[m].startPos);
                
                 for (i=0; i<grids; i++)
                 {
                     
                     //this would be where grid number coincides with snake/ladder inception.
                     if (psl[m].startPos==i)
                     {
                     
                     }
                     
                     
                     //if snake or ladder not at this position on grid...
                     if (psl[m].startPos!=i)
                     {
                         //System.out.println("****CHECKING****: " + i);
                         //if its not completed all die value moves, everyPossibleDieRoll is false..
                         
                         for (int p=0; p<6; p++)
                         {
                             if (moves[i][p][1]==0)   // for some reason, the i index is the position of the actual snakes and ladders startPos
                             {
                                 //i is grid number,    p is dice value  
                                //System.out.println("endpoint for: " + i + " " + p + "  " + moves[i][p][1]);
                                
                                    //System.out.println("grid: " + i);
                                    //System.out.println("snake or ladder: " + psl[m]);
                                    //System.out.println("startposition: " + psl[m].startPos);
                                    //System.out.println("endpoint for: " + i + " " + p + "  " + moves[i][p][1]);
                                    
                                    allPreviousCompletedMoves=false;
                             }
                         }
                         
                     }
            
            
            
        //this will break, but it also has to force the inner do while to break
        //it is only possible if it is passed value false on the basis that
        //allPreviousCompletedMoves=true;
        
        if (allPreviousCompletedMoves)
        {
            System.out.println("***SHOULD REACH HERE WHEN ALL MOVES DONE!!!!****************");
            break;
        }
            
            }    
                
             m++;
            }while(m<lengthEnum);
            
            m=0;
        
        return allPreviousCompletedMoves;
    }
    
    
    public void defineMoves()
    {
        
        //[startPos] [ dicevalue] [ two elements, startPos and endPos ] 
        //this might be startPos on the grid between  1-99 
        //(excluding squares with Snake Head or base of ladder)…
        //{         diceValue{startPos,  endPos},  diceValue{startPos,  endPos}     };
        
    }
    
    public void diceThrow()
    {
        Random rand = new Random();
        
        do
        {
            //System.out.println("Value start1: " + allPreviousCompletedMoves);
     
        do
        {
        diceValue = (rand.nextInt(6)+1);
        //System.out.println("Value start2: " + allPreviousCompletedMoves);
        
        System.out.println("\nDie Value thrown:" + diceValue);
        
        //it would write the details here into the 3D array...
        //this is subject to be overwritten if it falls under snakes and ladders category.
        
        
        //due to zero indexing, subtraction of 1 from diceValue
        moves[currentPosition][diceValue-1][0]=currentPosition;
        moves[currentPosition][diceValue-1][1]=currentPosition+diceValue;
        
        //it has to also store the movements in a String since this is the only technique
        //for Set to differentiate if this path has been taken....
        
        sj.add(Integer.toString(diceValue));
        sj.add("{");
        sj.add(Integer.toString(currentPosition));
        sj.add(",");
        
        }while (performMove() && newPosition!=100);
        
        boardsCompleted++;
        
        System.out.println("Total moves taken: " + totalMoves);
        System.out.println("STARTING AGAIN: " + "Boards complete: " + boardsCompleted);
        
        //I kept this here to see all transactions. It can be seen that all moves have been performed.
        //but the system output below always represents false.
        //getMinimumMoves();
        
        
        System.out.println("have all moves been performed: " + allPreviousCompletedMoves);
        
        //NEED TO BE CAREFUL WITH THIS...
        //STRICTLY SPEAKING THE TOTAL MOVES IS FALSE AT THIS POINT
        //SINCE IT IT BIASED TOWARDS THE DIE ROLLS SO FAR...
        //ONLY POSSIBLE TO EXPLORE ONCE ALL MOVES FROM EACH GRID POSITION HAS BEEN DISCOVERED.
        
        sj.add("   Total moves (including board displacements beyond 100): " + Integer.toString(totalMoves));
        
        //also need to add the number of moves to the String...
        path[count]=sj.toString();
        
        outcomes.add(path[count]);
        
        
        System.out.println("******PATH*******: " + path[count]);
        System.out.println("Set size: " + outcomes.size());
        
         minimumMoves[count] = totalMoves;
        
        //ready to start again...
        //resets variables...
        sj=new StringJoiner(" ");
        currentPosition=0;
        //allPreviousCompletedMoves=true;
        totalMoves=0;
        count=0;
        newPosition=0;
        gridNumber=0;
        
    // this loop can become very expansive
    //it can potentially be adjusted to alternative..
    //Having performed research online, it states that the inner do while loop
    //will continue executing even if the outer evaluates as false..
    // so it will keep executing this:
    //while (performMove() && newPosition!=100);
    
    //so this means outer loop is purposeless until inside loop evaluates as false.
    //based on my current logic of the inner loop, it evaluates as true all time (performMove);
   
    
    //This was not intuitive logic at all.
    //And since the operations (inner) are totally unrelated to outside condition,
    
    //option is when everyPossibleDieRoll=true (to falsify the inner loop) governed by method.
    //performMove()..    This method relies on returned boolean checkValidMove().
    //it is immediately set to false....
    
    //But as described later, since I can not get  everyPossibleDieRoll() to evaluate as true,
    //it is just not bringing closure to either do while loops.
    
    //Only option is when I implement the manipulated game, to try and avoid these sections of th code.
    //it can clearly be seen visually that is has explored all the moves possible in the constraints...
    
    
    //}while (!everyPossibleDieRoll());
    
    //ensures there are 300 solutions...
    
    
    }while (outcomes.size()<500);
    
        // IT was iniitally envisaged to check the landscape of the board from the current position
        // to examine if avoiding a snake and getting maximum six values to get shortest path...
        //but in game of snakes and ladders, it might be beneficial slipping down a snake... and climbing a missed ladder since the differential
        //newPosition might be further than than getting a six.
        //The problem states smallest number of turns, hence it is utilizing the snakes and ladders to advantage.
        //and not necessarily getting a 6 on each throw...
        
        
        //when the combinations aspect is introduced, it needs to ensure there is a valid value that has
        //been inputted into each array position. This is the only way to ensure all possibilities have been explored..
        //from each position on the board..
        //it was decided to actually simulate scenario when using combinations.. since the random number aspect
        //will not satisfy the minimum turns... Random moves was for evaluation of the code...
        
    }
    
    
    public boolean performMove()
    {
        //temp=currentPosition;
        newPosition = currentPosition + diceValue;
        System.out.println("Current position on board: " + newPosition);
        
        return checkValidMove();
    }
    
    
    
    public boolean checkValidMove()
    {
        //this is only exception that it evaluates as false.
        //once it has performed every die roll.
        // it is terminating just to examine how many sets (boards traversed 0-100)
        // it can be
        
        if (allPreviousCompletedMoves)
        {
            System.out.println("Terminate method");
            return false;
        }
        
        
        
        
        System.out.println("In valid move");
        
        if (newPosition>100)
        {
            System.out.println("Roll back");
            
            newPosition=currentPosition;   //it performs a roll back
            System.out.println("new position: " + newPosition);
            
            //it has now finalised new position and can close the transaction history...
            //ready to write into path array...
            sj.add(Integer.toString(newPosition));
            sj.add("}");
            
            return true;
        }
        
        if (newPosition==100)
        {
            newPosition=currentPosition+diceValue;
            
            sj.add(Integer.toString(newPosition));
            sj.add("},  ");
            
            return true;
        }
    
    //NOTE in the below code, it can not complete board at value 100...
    //since there is typically never a ladder which takes person directly to 100.
    //in the game, it usually is challenge at the latter stages to hit exact dice value in getting
    //exactly 100...
     
     //due to zero index  (diceValue-1)
     //{         diceValue-1{startPos,  endPos},  diceValue-1{startPos,  endPos}     };
     
     //it is irrelevant if the move has happened before, however it can perform quick check
     
     //if (Board[currentPosition][diceValue-1][0]!=0)
     //{
         //move has been performed since there is an entry...
     //}
         //this is a bit wasteful checking all the entries...
         //but there is no real reference point
         
         //this will go through all enums unconditionally
         //since it does not know which is snakes and ladders, it has to check the startPos and endPos
         
         System.out.println("Checking if new position is a snake or ladder: " + newPosition);
         
         
         for (PositionSnakesLadders enum1: psl)
         {
             //if its a snake, start point is head.
             //if its a ladder, start point is the bottom.
             if (newPosition==enum1.startPos)
             {
                 //this has to be a snake since there is a descent...
                 if (enum1.startPos>enum1.endPos)
                 {
                     newPosition=enum1.endPos;
                     System.out.println("Hit a snake, moving down:" + enum1.endPos);
                     
                     //storing transaction with incurring a snake
                     sj.add(Integer.toString(newPosition));
                     sj.add("},  ");
                     
                     return true;
                     
                 }
             
              //this has to be a ladder since ascend
             if (enum1.startPos<enum1.endPos)
             {
                 System.out.println("Hit a ladder, moving up:" + enum1.endPos);
                 newPosition=enum1.endPos;
                 //storing transaction with incurring a ladder
                 sj.add(Integer.toString(newPosition));
                 sj.add("},  ");
                 
                 return true;
             }
             
             }
             
         }  //end for 
         
         //finalises current position
         currentPosition=newPosition;
         
         //it would only perform this if it has not entered above loops.
         //since it would have hit a return statement above in getting snakes or ladders...
         
         sj.add(Integer.toString(newPosition));
         sj.add("}, ");
         
         
         System.out.println(newPosition + " at end of valid move");
         
         //this is confusing part..
         //the question states smallest number of turns
         //This sounds as if it is referring to valid moves as oppose to moves which would
         //stretch beyond 100
         //it is difficult to interpret smallest number of turns, but for now 
         //taking all scenarios into consideration.
         
         
         totalMoves=totalMoves+1;
         System.out.println("Total moves taken: " + totalMoves);
         
         
         //it would remain true in all circumstances unless validated as false
         return true;
        
    }  //end boolean method
    
    
    //checking if board is valid...
    //not part of requirements.
    //but it is quite impossible creating other test scenarios without this...
    
    public void checkSnakesLadder()
    {
        for (PositionSnakesLadders enum1: psl)
        {
            //System.out.println("current value of i: " + i);
            
            //with the single Enum collection, it is not possible to validate if the endPos is greater than
            //startPos for ladder.
            //and if endPos is less than startPos for snakes...
            //since there is no way to distinguish the constants.....
            //Ignoring this aspect.
            //can potentially partition in future.
            
            j=0;
            for (PositionSnakesLadders enum2: psl)
            {
                //System.out.println("current value of j: " + j);
                
                //ensures no two enums are compared against each other....
                //this is fine....
                if (i==j  && i!=lengthEnum-1)
                {
                    j++;
                    
                    //System.out.println("Jump value of j: " + j);
                }
                
                //this logic ensures it does not exceed boundary of the available enum constants...
                if (j!=(lengthEnum-1))
                {
                    //it will store the enum value of the i loop
                    PositionSnakesLadders current = enum1;
                        
                    //looking at a real life board, it can be seen that no two elements (snake or ladders)
                    //have their ends simultaneously on any grid....
                    //so to ensure that all the logic holds, I will just run few checks for validation of
                    //data entry...
                    
                    //psl.values[0].startPos;
                        
                        //can not compare like this...
                        //since its a for each loop
                        //need to use reference to index in values....
                        
                        if (psl[i].startPos == psl[j].startPos)
                        {
                            System.out.println("Invalid board configuration1: " + current.name()  + " {" + current.startPos+","+ current.endPos+"}");
                            System.out.println("Invalid board configuration2: " + enum2.name()  + " {" + enum2.startPos+","+ enum2.endPos+"}");
                        }
                        
                        if (psl[i].endPos == psl[j].startPos)
                        {
                            System.out.println("Invalid board configuration3: " + current.name()  + " {" + current.startPos+","+ current.endPos+"}");
                            System.out.println("Invalid board configuration4: " + enum2.name()  + " {" + enum2.startPos+","+ enum2.endPos+"}");
                            
                        }
                        
                
                        //if (current.startPos == enum2.startPos)
                        if (psl[i].startPos == psl[j].startPos)
                        {
                            System.out.println("Invalid board configuration5: " + current.name()  + " {" + current.startPos+","+ current.endPos+"}");
                            System.out.println("Invalid board configuration6: " + enum2.name()  + " {" + enum2.startPos+","+ enum2.endPos+"}");
                        }
                        
                        if (psl[i].endPos == psl[j].endPos)
                        //if (current.endPos == enum2.endPos)
                        {
                            System.out.println("Invalid board configuration7: " + current.name()  + " {" + current.startPos+","+ current.endPos+"}");
                            System.out.println("Invalid board configuration8: " + enum2.name()  + " {" + enum2.startPos+","+ enum2.endPos+"}");
                            
                        }
             
                j++; 
            
                }
            }
         
         i++;   
        }
        
    }
    
    
    //this will be used to show end user movement...
    // not possible to put Snakes or ladders on integer array...
    //but it will show end user being displaced in process...
    
    public void setBoard()
    {
        Board = new int[][]  { 
                                        {100,99,98,97,96,95,94,93,92,91},
                                         {90,89,88,87,86,85,84,83,82,81},
                                        { 80,79,78,77,76,75,74,73,72,71},
                                        { 70,69,68,67,66,65,64,63,62,61},
                                        { 60,59,58,57,56,55,54,53,52,51},
                                        { 50,49,48,47,46,45,44,43,42,41},
                                        { 40,39,38,37,36,35,34,33,32,31},
                                        { 30,29,28,27,26,25,24,23,22,21},
                                        { 20,19,18,17,16,15,14,13,12,11},
                                        { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1},
                                        
                                        };
        
        
    }
    
    
    
    // without converting the board other than int[][], this method will always ensure that
    //all values of the enum
    //since the 
    public void assignSnakesLadders()
    {
        //validates the board....
        checkSnakesLadder();
        
    }
    
     public void setGrid()
    {
        
    }
    
    
    public void getMinimumMaximumMoves()
    {
        min=minimumMoves[0]; 
        max=minimumMoves[0];
        
        for (int val: minimumMoves)
        {
            if (val!=0)
            {
            if (val<min)
            {
                min=val;
            }
            }
            
            
            if (val>max)
            {
                max=val;
            }
            
            
        }
        
        System.out.println("The minimum moves is: " +  min);
        System.out.println("The maximum moves is: " +  max);
        
        System.out.println("*******ANALYSIS OF ALL THE MOVES UNDERTAKEN  [Start Position => End Position]******");
    
        for (int[][] arr : moves) 
        {
            System.out.println("Grid number: " + gridNumber + "   " + Arrays.deepToString(arr));
            gridNumber++;
        }
        
    }
    
}


//Driver class

//Not sure if this was the right approach extends...
// Completed this due to the PositionSnakesLadders values....

//SnakesLaddersManipulated extends SnakesLadders
//RandomSnakesLadders extends SnakesLadders implements Movable
//Combination extends SnakesLadders



public class SnakesLadders
{
     static PositionSnakesLadders[] psl;
     static int lengthEnum;
     static int max;
     static int min;
    
    enum PositionSnakesLadders
    {
        
        SNAKE1(16,6), SNAKE2(48,26), SNAKE3(49,11), SNAKE4(56,53), SNAKE5(62,19), SNAKE6(64,60),  SNAKE7(87,24), SNAKE8(93,73), SNAKE9(95,75), SNAKE10(98,78),
        LADDERS1(1,38), LADDERS2(4,14), LADDERS3(9,31), LADDERS4(21,42), LADDERS5(28,84), LADDERS6(36,44),  LADDERS7(51,67), LADDERS8(71,91), LADDERS9(80,100);
        
        
        int startPos;
        int endPos;
        
        
        PositionSnakesLadders(int startPos, int endPos)
        {
            this.startPos=startPos;
            this.endPos=endPos;
        }
        
    }
    
    
    
    public static void main(String[] args) {
        System.out.println("Welcome to Online IDE!! Happy Coding :)");
        
        psl = PositionSnakesLadders.values();
        lengthEnum = psl.length;
        
        //this performs the game via random generated die
        //ensures the board has valid input...
        //only checks ensure startpos and endpoint don't conflict..
        
        RandomSnakesLadders sl = new RandomSnakesLadders(psl);
        
        //starts die throw once ready....
        sl.diceThrow();
        
        System.out.println("\n");
        
        //this gets minimum moves in a random simulated environment of die...
        sl.getMinimumMaximumMoves();
        
        
        //this will initiate the process of simulated environment using fixed
        //die roll in order to satisfy all combinations of snakes laddders
        //from  C(all elements in enum,    r from 0 to it's entire length)
        //Note it will use without replacement....
        
        //**** NEED TO IMPLEMENT THIS PART ******* (AS PER DOCUMENTATION)
        Combination c = new Combination(PositionSnakesLadders.values());
        
       
}
}

class SnakesLaddersManipulated extends SnakesLadders
{
    public SnakesLaddersManipulated(long combinations, PositionSnakesLadders[] psl)
    {
        
        Set<PositionSnakesLadders> set1;

        // Adding the elements
        set1 = EnumSet.of(PositionSnakesLadders.SNAKE1);
        
    }
}



class Combination extends SnakesLadders
{
    public Combination(PositionSnakesLadders[] psl)
{
    System.out.println("Welcome to Online IDE!! Happy Coding :)");
    int originalNumber=0; // for moment it is declared a 0 to keep next line content...
    
    int n=originalNumber;
    
    int r; // this does not need be in for loop. user defined
    
    Set <String> s = new HashSet<>(); // it will contain all combinations...
    
    
    int [] X = new int []{1,1,1,1,1,1}; //user defined
    
    
    int minimum; // the smallest value in X. This will assist with generating r value...
    
    int maxRValue; //upper limit for r in the loop to process 0<r<=maxRValue+1
    
    
    Map <Integer, Long> m; // this can stay outside loop since its not impacted by size of n and r
    
    
    originalNumber=n; // this will remain constant during a full iteration..
    
    m= new HashMap<>(); //new instance is required to start process again...
    //r can be estimated as follows based on:
    //Maximum length of a combination is approximately (N/ minimum value in X)
    
    
    
    maxRValue=64;
    //informs end user of constraints...
    //System.out.println("Maximum value of r: " + (maxRValue+ 1) + " has been set using minimum value in set: " + minimum + " , which should be in proximity to N(" + Staircase.k + ")");
    //additional 1 added due to potential rounding errors
    
    //as per the findings in the documentation.....
    if (maxRValue>=64)
    {
        System.out.println("Value is too high computationally. It will be reduced to: " + (maxRValue-1));
    }

    
    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)+")!");
        
        //creates instance of main execution of code...
        
        SnakesLaddersManipulated smc = new SnakesLaddersManipulated(Combinations (n,r,originalNumber,m), psl);
        
        //sc = new Staircase (Combinations (n,r,originalNumber, m), X, r,s, maxRValue);
        
    }
    
    //this will output all the unique combinations onto the screen...
    // It might be worthwhile and experimenting with similar changes to myself in the code...
    // And ensure there are enough execution cycles left in the code to see these....
    //unfortunately due to my code logic, I simply could not get unique subsets during the main program execution...
    // This will be something I might try again in the future, or seek assistance from someone more knowledgable than me..
    
    
    
}

public static long Combinations (int n, int r, int originalNumber, Map factorialResults)
{
    long result=0;
    int denominator1; //denominator split two parts since there are two factorial calculations
    int denominator2; //denominator split two parts since there are two factorial calculations
    int Numerator=n+r-1; // Numerator
    int zero=0;
    long zeroFactorial = 1;
    // if no sample or objects, there are no outcomes...
    if (originalNumber==0 && r==0)
    {
        System.out.println("n and r can not both be equal to zero");
        //System.exit(0);
        
        return 0;
        
    }
    //this situation would occur if n is 0 only and r is any positive number accept 0 (if statement above)
    //for instance (C^R (n,r)) = (0,3) 0+3-1 = 2 2<3

    if (originalNumber==0 && originalNumber+r-1<r)
    {
        System.out.println("n+r-1 must be > or = to r");
        //System.exit(0);
        return 0;
        
    }
    
    if (Numerator>=1)
    {
        result = ((n+r-1)* (Combinations (n-1, r,originalNumber, factorialResults)));
        // this completes factorial for numerator
        factorialResults.put(Numerator,result); //result stored in the Map
        //factorialResults.put(n-1,result); //result stored in the Map
        //System.out.println("getting result back out numerator: " + (Numerator) + " " + factorialResults.get(n+r-1));
        
        if (n==originalNumber) // this will occur once
        {
            denominator1 = r;
            denominator2 = originalNumber-1;
            factorialResults.put(zero,zeroFactorial); //0! is equal to 1
            
            if (factorialResults.containsKey(denominator1) && factorialResults.containsKey(denominator2))
            {
                long returnValue = result / ((long)factorialResults.get(denominator1) *(long)factorialResults.get(denominator2));
                return returnValue;
                
            }
            
        }
        return result;
        
    }
    return 1; // it will reach here only when condition not met (Numerator>=1)
    }
    
}