//*** 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.... // once again, I needed to increase by 1. //I think it was related to that it was trying to perform this method before there //was an entry in the set. // the contents in here are wiped each time once called 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; //these are used so that end user gets correct information on screen. //otherwise they will not know 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.. 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 basic 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. public Direction(String valuesSet, int[][] matrix, String alternateDownRight, int newSetSize) { this.valuesSet=valuesSet; this.matrix=matrix; this.newSetSize=newSetSize; movesAlternateDownRight(); } //observe constructors with same method signature but re-arranged. 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 co-ordinates align to matrix.length and matrix[0].length..... //(maximum both dimensions, hence bottom right) if (currentPosY==(matrix.length-1) && currentPosX==(matrix[0].length-1)) { successfulFinish=true; System.out.println("*****Successful: " + valuesSet); //stores the path in the array completedPaths[count] = (valuesSet + " Subset: " + count + " " + "Coins collected{"+Direction.coinsCollectedinAllMoves+"}" + " " + " TOTAL COINS: " + totalCoins); //Every entry stored (START=>FINISH) and associated coin collection stored in maximumCoins array. maximumCoins[count] = totalCoins; //I am unsure why I had to set the counter to 0 here. //Otherwise it would reach ArrayIndexOutOfBoundsException //it is definitely related to iteration in getMinimumMaximumCoins counter=0; 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 //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 does have 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 } //this method is called each time that START => End has completed.. //unfortunately with the structure of my code, I have tried extremely hard to fix it. //but it will have instantiated the Direction class each time this method is reached. //it would have in the process re-initialised: int [] maximumCoins = new int [newSetSize+1] //this is all the data recorded for the total of coins.. //It is not affected for the first entry in the array since Direction is instantiated and it //calculates min and max based on the single entry. //once it checks the next entry in the set, it has re-initialised the variable. // I tried extremely hard by even passing the variable in the =new Direction (......) //but several other issues flared up. This means that I can not call this method during //during the main code execution and only perform it at end.... public static void getMinimumMaximumCoins() { //both minimum and maximum are 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. It makes little difference since it will perform evaluations below.... min=maximumCoins[0]; System.out.println("*******MINIMUM AND MAXIMUM OF ALL THE COINS COLLECTED [Start Position => End Position]******"); //this will store minimum turns... //also store maximum turns storeMinimumCoins = new String[newSetSize]; storeMaximumCoins = new String[newSetSize]; //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... //posProcessed will need to be greater than 0 so that it can not compare //the existing minimum in min (minimumCoins[0]) against each itself again! //normally this would not be an issue. // But if this was not included, it would think that another minimum is found with same minimum //number of Coins. And create a fresh entry in storeMinimumCoins. if (val==min && counter!=0) { //System.out.println("Current min: " + val); //System.out.println("value of counter: " + counter); //System.out.println("value of min co: " + minimumCoins.length); //ensures it does not go ArrayIndexOutOfBoundsException //it starts from 1 to ensure it does not write to the first index. //which already has minimum value as below.... //note this method has to come before if loop below //if (valmax && counter!=1) { max=val; storeMaximumCoins = new String[newSetSize]; storeMaximumCoins[0]=Direction.completedPaths[counter]; } counter++; //posProcessed++; } } System.out.println("Minimum Coins is: " + min); System.out.println("Maximum Coins is: " + max); } public static void finalResults() { System.out.println("\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=1; 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) { for (int i=1; i<=DOWNvalue; i++) { //hit a wall //in the counting of coins, need a clause that if 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])); //this can be enable for better efficiency, however all conditions //are set in the code to not process any conditions for remaining moves //due to obstructions //t=numbers.length; //} } } //moves downwards along Y axis from existing position. //checks if it exceeds the height of the matrix... if (currentPosY + DOWNvalue =matrix[0].length) { //sets flag accordingly. System.out.println("MOVEMENT IS OUT OF BOUNDS"); successfulFinish=false; outBounds=true; decision(movementPattern, sj1.toString()); } if (!outBounds) { for (int i=1; i<=RIGHTvalue; i++) { //if ((matrix[currentPosY][currentPosX+i])) //{ totalCoins = totalCoins + matrix[currentPosY][currentPosX+i]; //this can be enable for better efficiency, however all conditions //are set in the code to not process any conditions for remaining moves //due to obstructions //t=numbers.length; //break; sj1.add( Integer.toString(matrix[currentPosY][currentPosX+i])); //} } } coinsCollectedinAllMoves=sj1.toString(); //moves right along X axis from existing position. //checks if it exceeds the width of the matrix... if (currentPosX + RIGHTvalue 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 for (int i: X) { //has to be converted to String in order to store in the StringJoiner.... subsetIntToString = Integer.toString(i); //only does previous check if not the first item... if (pos>0) { //if it is same number as previously, it mantains boolean true for allSameDigit //otherwise sets it to false and locks the loop... if (previousI!=i ) { allSameDigit=false; } } //sets previousI to current i before it can be incremented above.. previousI=i; pos++; //counter for pos. } //fills StringJoiner with all repetitive numbers to get total k do { sj1.add(subsetIntToString); countSameNumber++; }while(countSameNumber<(maxRValue/X[0])); //System.out.println("*********************************"); //if the boolean is unchanged from the initiation. //note it was declared as true as part of the declaration.... if (allSameDigit) { System.out.println("\nk is equal to: " + k); System.out.println("This is the solution: " + sj1.toString()); //can also uncomment and continue execution if required... System.exit(0); } 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 //System.out.println("newset size: " + newSetSize); if (newSetSize>currentSetSize) //if larger, i.e a new combination, it will inform end user.. { } 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]) { //System.out.println("Match found in backupValuesSet: " + m); //System.out.println("Match found in valuesSet: " + valuesSet[n]); valuesSet[n]="ALREADY PROCESSED"; //System.out.println("valuesSet[n]" + " set to " + valuesSet[n]+"\n"); } 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 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}, //{5,0,1,6,4}, //{0,4,1,3,2}, //{1,0,0,9,6}, {0,0,1}, {0,1,1}, {1,0,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+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 Staircase and main execution of code... sc = new Staircase (Combinations (n,r,originalNumber, m), X, r,s, maxRValue, matrix, maximumLengthMoves); } //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.... // Note these are NOT all functional solutions to the problem.. It only guarantees totals of 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************"); //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"); } //Direction.getMinimumMaximumCoins(); 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