Home > Blockchain >  recursive algorithm on list of numbers , to find out if i have enough steps get to to the end
recursive algorithm on list of numbers , to find out if i have enough steps get to to the end

Time:12-01

If I have a list of numbers ,

for example [3,4,5,7,0,5,2] .

Every element in the list is represent the number of max steps I can move forward from this cell . a good list is when I can get to the end of the list , a bad list is when I don't have enough steps to get to the end of the list .

I try to write the following code but its not right :

def recu(li):

    if li[0] == 0:
        print("not working")
        return 'Null'

    if li[0] >= len(li):
        print('finished with success')
        return 'Null'

    if li[0] < len(li):
        print(li[li[0]:])
        return recu(li[li[0]:])




recu(list1)

can you please help me ?

CodePudding user response:

Is this the logic you are looking for?

def is_good(l):
    e = l[0]
    return False if e == 0 else True if e >= len(l) -1 else is_good(l[e:])

I tried a few lists - and that makes sense, from my understanding of the problem:

is_good([0,1,3])           # Returns False
is_good([3,3,5,0,1])       # Returns False 
is_good([1,7,2,3,0])       # Returns True
is_good([[3,4,5,7,0,5,2])  # Returns True

I assume you have to step on or beyond the last element - if you just need to go beyond

def is_good(l):
    e = l[0]
    return False if e == 0 else True if e >= len(l) else is_good(l[e:])

CodePudding user response:

You can use dynamic programming for that.

def solution(x):
    a = [False] * len(x)  # list of accessible cells
    a[0] = True  # first cell accessible
    for i, (p, k) in enumerate(zip(a, x)):
        if p:
            for j in range(i, i   k   1):
                try:
                    a[j] = True  # mark all the cells that can be reached from the processed to the cells
                except IndexError:
                    return True
    return False

print(solution([3,4,5,7,0,5,2]))

You also can use recursion:

arr = [3, 4, 5, 7, 0, 5, 2]

def f(i):
    if i   arr[i] >= len(arr):
        print(True)
        exit(0)
    for j in range(i   1, i   arr[i]   1):
        f(j)

f(0)
print(False)
  • Related