Home > Blockchain >  Java recursive calls
Java recursive calls

Time:09-30

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;
        }
  • Related