//*** 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 Position]******"); //this will store minimum turns... //also store maximum turns storeMinimumCoins = new int[newSetSize]; storeMaximumCoins = new int[newSetSize]; //checking all values in array for (int val: minimumCoins) { //System.out.println("val counter: " + counter); //System.out.println("val posProcessed: " + posProcessed); //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 && posProcessed!=0) { //ensures it does not go ArrayIndexOutOfBoundsException if (countermax && counter!=1) { max=val; storeMaximumCoins = new int[newSetSize]; maximumCoins[0]=max; } counter++; posProcessed++; } counter=0; System.out.println("Minimum Coins is: " + min); System.out.println("Maximum Coins is: " + max); } 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, sj.toString()); } if (!outBounds) { for (int i=1; i<=DOWNvalue; i++) { //hit a wall //if (matrix[currentPosY+i][currentPosX]) //{ 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... sj.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, sj.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; sj.add( Integer.toString(matrix[currentPosY][currentPosX+i])); //} } } coinsCollectedinMove=sj.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,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,1}, //{0,0,1}, //{1,0,0}, //{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: sc.finalOutput /*Direction.completedPaths*/) { if(str!=null) { System.out.println(str); solutionFound=true; } } if (!solutionFound) { System.out.println("NO solutions"); } } 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