CODEWITHSUNDEEP
pythonrecursion
J.Y.P.
J.Y.P.

Reputation: 59

How to use the original list if I sent it to a recursive function that changes it?

I have a recursive function that checks if there is a path from the first to the last object of the list.

the step is the object value and it can step to both directions:

I start from the last object and check which number, if I step from it a number of steps according to its value- goes to the last one. The function is supposed to return True if I managed to link the last to the first this way.

In my function I tried to change the list after I found the number that can arrive to the last, so that the number I found will be the last. Then I changed the numbers so that the distances will be saved.

But let's say there is a number that steps to it, how will I be able to check that number afterwards? I already changed the list..

Suppose I have this list: [6, 4, 8, 2, 4, 2, 3, 6] the function will return True. The path will be 6,3,2,2,6

But the function receives only a list. So let's say I start from the end and find that 2 arrives to the end of the list. How do I continue? How do I check which object goes to 2? (this time- 2) and so on?

    def walking_on_list(lst):
for i in range(len(lst)):
    if i + lst[i] == len(lst) - 1:
        if i == 0:
            return True
        else:
            diff = len(lst) - 1 - i
            lst[-1] = lst[i]
            lst[i] = 0
            for j in range(len(lst[:found])):
                lst[j] += diff
            temp = lst[found + 1:-1]
            temp = temp[::-1]
            for k in range(len(lst[found + 1:-1])):
                lst[k + len(lst[:found]) + 1] = temp[k]

            valid_path(lst)
    elif i == len(lst) - 1:
        return False

print(walking_on_list([6, 4, 8, 2, 4, 2, 3, 6])

Upvotes: 0

Views: 116

Answers (1)

Daniel
Daniel

Reputation: 42778

Use an algorithm, that does not change the list.

def walking_on_list(lst, indices=(0,)):
    index = indices[-1] + lst[indices[-1]]
    if index == len(lst) - 1:
        return True
    if (index < len(lst) and index not in indices
        and walking_on_list(lst, indices + (index,))):
        return True
    index = indices[-1] - lst[indices[-1]]
    if (index > 0 and index not in indices
        and walking_on_list(lst, indices + (index,))):
        return True
    return False

print(walking_on_list([6, 4, 8, 2, 4, 2, 3, 6]))

Upvotes: 2

Related Questions