//*** 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.... //What has been done so far... //if the move is destined to go out bounds, it is ready to make a decision... //if it hits the wall, right now it is continuing with rest path... This is incorrect, it should also make a decision //This is no different from the previous example and moves will supersede where applicable.. //but for now, the alternation of moves is not correct... //since there is no aspect of symmetry due to being blocked by wall //but what we know is that current FaceBook code performs a down movement first and then right movement... //this can be detrimental now... //since in the following grid.. if the sequence was {1,2,1} {down, right, down} according to code... //it would perform down 1 and make decision.... //{0,0,0}, //{1,0,1}, //{1,0,0}, //but if {1,2,1} {right, down, right} was conducted, it can be seen a successful path //from top left to bottom right. //NOTE, THE ALTERNATION TECHNIQUE IS STILL CORRECT... BUT IT MATTERS WHICH ONE IS UNDERTAKEN FIRST ALSO. //if the conditions were removed t%2==0 and associated else statement... //it would now perform each move {1,2,1} for both down and right... //this is incorrect logic also.... //only technique to overcome this is isolate the code in the main for loop. //there would still be an issue here, since its no different to existing code in alternating sequence. //for (int t=0; t END) //used in conjunction with StringJoiner static String coinsCollectedinAllMoves; //This is main objective.. //keeps track of all coins collected in successful (START => END) //tried numerous ways, but unable to set this in other technique since // it is growing content alongside newSetSize //it can not be re-initialised since the content will be lost.. static int [] maximumCoins = new int [5000]; //these will store completed paths and their totals. //it is an array since there can be multiple paths with same number coins.. //the minimum is not requirement, but is a useful measure to have.... // the contents in here are wiped each time once in the method //getMinimumMaximumCoins() static String [] storeMinimumCoins = new String [newSetSize+1]; static String [] storeMaximumCoins = new String [newSetSize+1]; //Used in getMinimumMaximumCoins() to hold the current minimum and maximum. static int min; static int max; //keeps track of total coins... static int totalCoins; //used in conjunction with enum. Although value is assigned here, // I struggled to utilize Direction.RIGHT.size. So the variable was referenced directly.. //I have used irregular naming convention since it is a prompt that it is associated to enum Constant... static int RIGHTvalue; //used in conjunction with enum. Although value is assigned here, // I struggled to utilize Direction.DOWN.size. So the variable was referenced directly.. //I have used irregular naming convention since it is a prompt that it is associated to enum Constant... static int DOWNvalue; //it contains numbers that totals up to moves (START=> END) String valuesSet; //position along the X axis of the matrix. static int currentPosX; //position along the negative Y axis of the matrix. static int currentPosY; //to evaluate if final position is [4][4] for instance on a 5x5 matrix. static boolean successfulFinish=true; //this is used when it commences from matrix[0][0] //it stores this value static int FirstCoinDownMove; static int FirstCoinRightMove; //these are used so that end user gets correct information on screen. //otherwise they will not know which alternation was undertaken from successfulFinish static String alternatingDownRight = "Alternating DOWN => RIGHT => DOWN ......."; static String alternatingRightDown = "Alternating RIGHT => DOWN => RIGHT......."; //since this variable is being populated similar time to the set, //it is unknown the size of this variable. 1000 is being provided.. //once again, it can not be re-initialised once data has been filled into it. static String[] completedPaths = new String [1000]; //used in array maximumCoins to keep track of all outcomes... static int count; //This has conversion of the movements (START=> END) into String array. //it is formed on basis of .split(","); static String [] numbers; //flag to ascertain if out of bounds... static boolean outBounds=false; //the matrix representing start point top left and end point bottom right... static int[][] matrix; //defines constants RIGHT AND DOWN as per question. enum Directions { DOWN(DOWNvalue), RIGHT(RIGHTvalue); //did not manage to utilize the below code in enum due to initialisation issues... //similar problem carried forward from SnakesLadders int size; Directions(int size) { this.size=size; } } //observe constructors with same method signature but re-arranged. //The String alternateDownRight is a placeholder so that correct Direction constructor can be called. public Direction(String valuesSet, int[][] matrix, String alternateDownRight, int newSetSize) { this.valuesSet=valuesSet; this.matrix=matrix; this.newSetSize=newSetSize; //The String in signature correlates to the method (alternating down=>right from inception) movesAlternateDownRight(); } //observe constructors with same method signature but re-arranged. //The String alternateRightDown is a placeholder so that correct Direction constructor can be called. public Direction(String valuesSet, String alternateRightDown, int[][] matrix, int newSetSize) { this.valuesSet=valuesSet; this.matrix=matrix; this.newSetSize=newSetSize; movesAlternateRightDown(); } //This method is called in four points of the code: //Out of bounds (right move) //Out of bounds (down move) //successful (right move) //successful (down move) //The parameter String movementPattern receives the argument alternatingDownRight //alternatingDownRight is the String value "DOWN=>RIGHT=DOWN" //It is required here to store correct level of information in completedPaths //The parameter coinsCollectedinAllMoves receives the argument sj1.toString(). //As a reminder, whilst the methods moveRight and movesDown are executed, it knows that //move will not be out of bound.. So it records move into sj1... //it is converted to a String and passed into this method... 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("************************************"); //this is universal flag for all situations. It is assumed finish does not complete. //it momentarily covers both scenarios above: // Out of bounds // Performing a move successfulFinish=false; //if co-ordinates align to matrix.length and matrix[0].length..... //(maximum both dimensions, hence bottom right), it is successfulFinish if (currentPosY==(matrix.length-1) && currentPosX==(matrix[0].length-1)) { successfulFinish=true; System.out.println("*****Successful: " + valuesSet); //stores the path in the array //note the purpose of this array is: //once it has found all outcomes, it can perform the official solutions output at //end in a tidy manner completedPaths[count] = (valuesSet + " Subset: " + count + " " + "Coins collected{"+Direction.coinsCollectedinAllMoves+"}" + " " + " TOTAL COINS: " + totalCoins + " " + "("+movementPattern+")"); //Every entry stored (START=>FINISH) and associated coin collection stored in maximumCoins array. maximumCoins[count] = totalCoins; //this shows the current minimum and maximum coin collected in move (START=>FINISH) getMinimumMaximumCoins(); System.out.println("Stored total coins: " + maximumCoins[count]); count++; // sets next position in array. } currentPosX=0; //resets value only once all numbers processed in subset currentPosY=0; //resets value only once all numbers processed in subset //DO NOT THINK ANYTHING ELSE NEEDS RESETTING... //new addition to existing code. //this value can not be wiped prematurely since it is used later on when //outputting the results.... //it can only clear the results if NOT successfulFinish. //the value HAS to be cleared however (once displayed on screen) in order to start //total again for (START=>FINISH) if (!successfulFinish) { totalCoins=0; } //using a separate StringJoiner to ensure running into no issues.. //it was almost difficult to imagine that we are at no point concerned with moves undertaken //it is the value in the matrix[][] //this keeps the values of the coins into a StringJoiner.. sj1 = new StringJoiner(","); coinsCollectedinAllMoves=" "; //not necessary... string will be overwritten anyhow.. } public static void getMinimumMaximumCoins() { //both minimum and maximum are initially the first item.. //System.out.println("min:" + maximumCoins[0]); //this array maximumCoins has all the values for coins collected during execution. //System.out.println("max:" + maximumCoins[0]); max=maximumCoins[0]; //since minimumCoins is currently empty when it reaches here first time, it will take first value //from maximumCoins. min=maximumCoins[0]; System.out.println("*******MINIMUM AND MAXIMUM OF ALL THE COINS COLLECTED [Start Position => End Position]******"); //this will store minimum turns compared against min //also will store maximum turns compared against max storeMinimumCoins = new String[1000]; storeMaximumCoins = new String[1000]; //checking all values in array for (int val: maximumCoins) { //can no longer use this for validation. //Since unlike Snakes and Ladders, there can be a minimum route of 0 // i.e no coins on entire path!! //also we know the entire set will constitute a valid entry inputted as part of the //start => end on the matrix... So there is no need to worry about any entries //being 0 (default value of integer array) for int [] minimumCoins = new int [newSetSize]; //if (val!=0) //{ //need index here. otherwise val already minimum will loop... //it doesnt need to compare maximumCoins[0] with itself //since it is already stored in storeMaximumCoins[0]. //if counter condition was not included, val==min //it would think that another minimum is found with same minimum //number of Coins. And create a fresh entry in storeMinimumCoins. //counter will be zero first time it reaches here... //so it will skip this... if (val==min && counter!=0) { //it will count from index 0 to length of array containing all the coin totals.... if (countermax && counter!=0) { max=val; storeMaximumCoins = new String[newSetSize]; storeMaximumCoins[0]=Direction.completedPaths[counter]; //System.out.println("Stored as new maximum: " + 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); for (String s: storeMinimumCoins) { if (s!=null) { System.out.println(s); } } System.out.println("\nMaximum Coins is: " + max); for (String s: storeMaximumCoins) { if (s!=null) { System.out.println(s); } } counter=0; System.out.println("\n\n"); } public void movesDown(int t, String movementPattern) { //assigns it to value. //as described earlier, unable to utilize it to desired effect with Direction.DOWN.size DOWNvalue = Integer.valueOf(numbers[t]); System.out.println("Performing this movement: " + "(" + Directions.DOWN + "): " + DOWNvalue); if (currentPosY + DOWNvalue >=matrix.length) { //there can not be a successful finish if it is out of bounds.. System.out.println("MOVEMENT IS OUT OF BOUNDS"); successfulFinish=false; outBounds=true; decision(movementPattern, sj1.toString()); } if (!outBounds) { //it needs to add this number once only to the StringJoiner.. //this is the first number... //only want to capture the first coin in the move if //its first move in the matrix. //otherwise the intersection will be captured multiple times along the path. 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]; //also need a StringJoiner here to record the actual number coins at each grid //along the move. It is not the moves that are of interest, it is the coins at //positions in the moves... sj1.add( Integer.toString(matrix[currentPosY+i][currentPosX])); //t=numbers.length; //break; } } //it needs to also get the coins at the start position!!! //the total coins is now total of all steps in the move //as well as the start position. totalCoins = totalCoins + FirstCoinDownMove; //this has to be reset... FirstCoinDownMove=0; //This keeps record of coins in the movesDown coinsCollectedinAllMoves=sj1.toString(); //moves downwards along Y axis from existing position. //checks if it exceeds the height of the matrix... if (currentPosY + DOWNvalue End) public void movesRight(int t, String movementPattern) { //again, not able to use it with Direction.RIGHT.size in enum RIGHTvalue=Integer.valueOf(numbers[t]); System.out.println("Performing this movement: " + "(" + Directions.RIGHT + "): " + RIGHTvalue); //length is not zero index. //so moving [0][0] with Rightvalue=3 would be matrix[0][3] //on a 3 x 3 matrix, matrix[0].length would be 3... //it can be seen it is out of bounds.. if (currentPosX + RIGHTvalue >=matrix[0].length) { //sets flag accordingly. System.out.println("MOVEMENT IS OUT OF BOUNDS"); successfulFinish=false; outBounds=true; decision(movementPattern, sj1.toString()); } if (!outBounds) { //it needs to add this number once only to the StringJoiner.. //this is the first number... if (t==0) { FirstCoinRightMove = matrix[currentPosY][currentPosX]; sj1.add(Integer.toString(FirstCoinRightMove)); } for (int i=1; i<=RIGHTvalue; i++) { //the total coins is now total of all steps in the move //as well as the start position. totalCoins = totalCoins + matrix[currentPosY][currentPosX+i]; //t=numbers.length; //break; sj1.add(Integer.toString(matrix[currentPosY][currentPosX+i])); } } //it needs to also get the coins at the start position!!! //the total coins is now total of all steps in the move //as well as the start position. totalCoins = totalCoins + FirstCoinRightMove; FirstCoinRightMove=0; //This keeps record of coins in the movesRight coinsCollectedinAllMoves=sj1.toString(); //moves right along X axis from existing position. //checks if it exceeds the width of the matrix... if (currentPosX + RIGHTvalue END or finished elsewhere on the matrix.. if ((t==numbers.length-1)) { decision(movementPattern, coinsCollectedinAllMoves); } } } //method to test moves in the matrix public void movesAlternateDownRight() { //the numbers are partitioned into a String array... numbers = valuesSet.split(","); //this is storing all movements in array. //also it is assigned to variables upValue and downValue //these are referenced in the enum also and used to assigned value to the constants UP and DOWN... //not going to physically test the dimensions of the storage location in the array. //Although this is possible and can use try and catch.. System.out.println("\n\n"+ "{"+valuesSet + "}"+ " will be evaluated against the " + matrix[0].length + "x" + matrix.length + " matrix********"); System.out.println(alternatingDownRight); //it goes through all the numbers that compromised subset which totalled matrix[0].length + "x" + matrix.length + " matrix********"); successfulFinish=true; outBounds=false; for (int t=0; t backupValuesSet = new ArrayList<>(); Set 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...) static int newSetSize; // holds size of set after entry added public Staircase(long combinations, int[] X, int r, Set 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(","); // creating StringJoiner for the final output StringJoiner sj1 = new StringJoiner(","); //creating StringJoiner to construct if all numbers same in X [] int currentSetSize=0; // holds size of set before entry added //int count=0; int q; //used in the for loop to iterate through r int steps; // it will hold value of step generated randomly from r boolean allSameDigit=true; // this is used to check if X array contains all number 1's.... String subsetIntToString=""; // since it needs to add number back into the StringJoiner, //it has to be converted into a String first.... int countSameNumber=0; //used tdo fill StringJoiner in preparation if all numbers same in X[] 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 { //sets count back to 1 when it has finished. This is visual check to ensure that r is not exceeded for (q=0; qk) { total=0; //resets total sj = new StringJoiner(","); //creates new instance, resets contents... } newSetSize = st.size(); // new set size 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(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.... //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]) { valuesSet[n]="ALREADY PROCESSED"; } n++; }while (n(Arrays.asList(backupValuesSetBeforeModification)); //this now processes each String in the ValuesSet (which will be Strings not outputted yet) for (int entry=0; entry END) //THIS IS THE STARTING POINT OF MOST CODE IN THIS TYPE OF COMBINATION CODE //ANY ERRORS HAVE TO BE TRACED FROM HERE FORWARDS.... 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++; //static variable, it will keep track of number successful combinations } //if it completes a successful move... if (startToFinishDownRight(valuesSet[entry])) { System.out.println (valuesSet[entry] + " Subset: " + subsetEntry + " " + "Coins collected{"+Direction.coinsCollectedinAllMoves+"}" + " " + " TOTAL COINS: " + Direction.totalCoins +" " + "("+Direction.alternatingDownRight+")"); //extremely critical, since it has performed the above screen output, it needs set variable back to 0 Direction.totalCoins=0; subsetEntry++; //static variable, it will keep track of number successful combinations } } //end of if } //end of for //*** THIS LINE HAS BEEN REMOVED AS PER LATTER PART IN MY DOCUMENTATION **** 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"); //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... //this method instantiates Direction class. //this does processing for movement in matrix based on values in subsets //totalling k.. //if it successfully finishes at last position (bottom right) of matrix, true is returned. public static boolean startToFinishRightDown(String valuesSet) { //this is the associated constructor //public Direction(String valuesSet, String alternateRightDown, int[][] matrix) Direction d = new Direction(valuesSet, "RightDown", matrix, newSetSize); return d.successfulFinish; } public static boolean startToFinishDownRight(String valuesSet) { //this is the associated constructor //public Direction(String valuesSet, int[][] matrix, String alternateDownRight) Direction d = new Direction(valuesSet, matrix, "DownRight", newSetSize); return d.successfulFinish; } } //end of staircase class... public class Combination { static Staircase sc; //object of type Staircase public static void main(String[] args) { 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 s = new HashSet<>(); // it will contain all combinations... //this can be defined any dimensions for the L x W int[][] matrix = new int[][]{ //{0,0,0,0,0,0,1,0,0,7}, //{1,0,0,0,0,0,0,6,0,0}, //{0,0,9,0,1,1,1,1,0,1}, //{0,0,1,0,0,1,1,9,0,0}, //{0,0,1,0,0,0,1,1,1,0}, {0,0,1,6,4}, {0,4,1,3,2}, {0,0,0,9,6}, {0,0,0,0,0}, //{0,0,1}, //{4,1,1}, //{6,9,0}, }; //array is defined based on Matrix dimension //it has to be one less since it needs to exclude index of the start //position when moving right to end of matrix.... //likewise when moving downwards, it has to exclude the new starting position. //it will store possible moves. int [] X = new int [matrix[0].length-1]; //all possible values from 1 to length of the matrix. //using this approach to permit varying matrix sizes readily for (int k=0; k 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)); 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) //used to calculate minimum value in X[] array containing all possible length of moves.. minimum=X[0]; for (int i=0; i=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)+")!"); //creates instance of Staircase and main execution of code... sc = new Staircase (Combinations (n,r,originalNumber, m), X, r,s, maxRValue, matrix, maximumLengthMoves); } System.out.println("\n\n\n***********SOLUTIONS************"); //it will print out all the values stored in completedPaths for (String str: Direction.completedPaths) ////sc.finalOutput { if(str!=null) { System.out.println(str); solutionFound=true; } } if (!solutionFound) { System.out.println("NO solutions"); } //Unfortunately it is giving misinformation, so has been turned off... //Will aim to fix in the future. //Direction.finalResults(); System.out.println("\n\n"); } 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 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; } //end of if Numerator>=1 return 1; // it will reach here only when condition not met (Numerator>=1) } //end of combinations method. } //end of class Combination