Recusive fxn not returning what's expected

Question

So I was working on a hackerrank easy problem. It was actually pretty easy but I'm caught on something that I'm sure is very small but I can't find it and I was hoping you guys could help pinpoint the problem.

The name of the problem is "Jumping on The Clouds" and a paraphrased summary is this:

"The player can jump on any cumulus cloud having a number that is equal to the number of the current cloud plus 1 or 2

. The player must avoid the thunderheads. Determine the minimum number of jumps it will take to jump from the starting postion to the last cloud. It is always possible to win the game.

For each game, you will get an array of clouds numbered 0 if they are safe or 1 if they must be avoided. "

To simplify, you get an array of 0's and 1's and you must find the minimum amount of jumps it takes to get to the end of the array. You can only jump 1 or 2 spots at a time and you are guaranteed that the last cloud is "safe".

I immediately saw that this could be solved two ways, 1. as a graph theory problem, 2. as a tree implementation.

I chose to use the tree implementation.

Here is my code:

def jumpingOnClouds(c):
    if len(c) <= 1:
        print("at end of string")
        return 0
    
    elif c[0] == 1:
        print("dead end")
        return -1
    
    else:
        one = jumpingOnClouds(c[1:])    
        two = jumpingOnClouds(c[2:])
        if one == -1 and two > 0:
            print("chose 2")
            return two + 1
        elif two == -1 and one > 0:
            print("chose 1")
            return one + 1
        else:
            print("both were viable")
            return min(one, two) + 1

Simple right?

except it doesnt return correctly.

What I tried was: 1: I changed whats returned at the end of the string from "1" to "0" as it is now. This is because when I had it as 1 it always returned 1 number too high. So if the minimum is 3 it would return 4, etc..

2: When I return 0 at the end of the string it sometimes just stays as and returns 0.

An example of this is with the input [0,0,1,0,0,1,0] which returns 0 with my current code.

Sorry for such a long post but I was trying to follow the community's rules and not anger anybody. Thanks for the help!

Sample inputs and outputs:

[000010] -> 3
[0010010] -> 4
[000100] -> 3
[0100010] -> 3

quamrana_4834 · Answer

Ok, its the testing of one and two where you are tripping up:

def jumpingOnClouds(c):
    if len(c) <= 1:
        #print("at end of string")
        return 0
    
    elif c[0] == 1:
        #print("dead end")
        return -1
    
    else:
        one = jumpingOnClouds(c[1:])    
        two = jumpingOnClouds(c[2:])
        if one == -1 and two >= 0:
            #print("chose 2")
            return two + 1
        elif two == -1 and one >= 0:
            #print("chose 1")
            return one + 1
        else:
            #print("both were viable")
            return min(one, two) + 1

for game in [[0,0,0,0,1,0],[0,0,1,0,0,1,0],[0,0,0,1,0,0],[0,1,0,0,0,1,0]]:
    print(f'{game} -> {jumpingOnClouds(game)}')

Output as given

Recusive fxn not returning what's expected

1 Answers