I want to build a code to go over any sequence of 0 and 1 and calculate how many different ways it can pass through the number just "jumping" between the '1's. Also it can jump no more than 3 digits per time.
For example, number 100110101 it could be like: 1xx1xx1x1 or 1xx11x1x1 (passing through all the '1').
Another example could be 1011011101: 1x11x111x1 (passing through all '1') or 1xx1x111x1 or 1x1xx1x1x1 and so on...
The important is not to jump more than 3 digits. And the number will always start and finish with 1 as well.
I've got the following code and I think it is working.
public int calculate(String number){
if(number.length()<3){ //left fill with 0
if(number.length()==2) number = "0" number;
else number = "00" number;
}
if(number.length() == 3){ //for 001, 101, 011, 111
if (number.equalsIgnoreCase("111")) return 2; //2 possible ways
else return 1; //any other combination will have just one way
}
String aux = number.substring(1,4);//take the 3 next digits
//recursive calls to calculate it
if (aux.equalsIgnoreCase("001")) return calculate(number.substring(3, number.length()));
else if (aux.equalsIgnoreCase("010")) return calculate(number.substring(2, number.length()));
else if (aux.equalsIgnoreCase("011")) return calculate(number.substring(2, number.length())) calculate(number.substring(3, number.length()));
else if (aux.equalsIgnoreCase("100")) return calculate(number.substring(1, number.length()));
else if (aux.equalsIgnoreCase("101")) return calculate(number.substring(1, number.length())) calculate(number.substring(3, number.length()));
else if (aux.equalsIgnoreCase("110")) return calculate(number.substring(1, number.length())) calculate(number.substring(2, number.length()));
else if (aux.equalsIgnoreCase("111")) return calculate(number.substring(1, number.length())) calculate(number.substring(2, number.length())) calculate(number.substring(3, number.length()));
return 0;
}
The question is: I also wanna make sure that it is not allowed to jump 3 digits twice in a row. Something like 1xx1xx1 is not allowed. However since I'm using recursive calls I don't know if that's possible.
CodePudding user response:
One way to prevent jumping 3 digits twice in a row is to pass extra state information to calculate()
; the extra data you pass would be a boolean indicating whether or not the last jump was of length 3. Then in your initial call to calculate()
, just make sure to indicate that the last jump was not of length 3 (so the first jump is allowed to be of length 3).
CodePudding user response:
private static int countPossibilities(String inputString) {
final char validChar = '1';
final char maxDistance = 3; // max consecutive jumps. eg: maxDistance for '1xxx1' is 3.
if (inputString.length() == 1) {
return 1;
}
var indexForMaxPossibleJump = Math.min(maxDistance 1, inputString.length() - 1);
if (inputString.charAt(indexForMaxPossibleJump) != validChar) {
indexForMaxPossibleJump = inputString.substring(0, indexForMaxPossibleJump).lastIndexOf(validChar);
}
// No jumps possible.
if (indexForMaxPossibleJump == 0) {
return 0;
}
int finalCount = 0;
var remainingString = inputString.substring(indexForMaxPossibleJump);
var maxJumpingString = inputString.substring(1, indexForMaxPossibleJump);
// calculate count if we are not jumping to max distance. i.e., taking intermediate step on 1.
for (var i = 0; i < maxJumpingString.length(); i ) {
if (maxJumpingString.charAt(i) != validChar) {
continue;
}
var countOfString = countPossibilities(maxJumpingString.substring(i) remainingString);
finalCount = countOfString;
}
// calculate count if we are jumping to max distance.
var countOfRemainingString = countPossibilities(remainingString);
finalCount = countOfRemainingString;
return finalCount;
}