Keeping the variable 's value in recursive function, python 3.3

Question

I managed to do it, some other way. but I have a question, I had this code before

def jumphunt(start, mylist, count = 0):
    if count < len(mylist):
        place = mylist[start]
        print(place)
        if place == 0:
            return True
        elif start >= len(mylist) or start < 0:
            return False
        move_left = (start - place)
        move_right = (start + place)
        return jumphunt(move_right, mylist, count+1) or jumphunt(move_left, mylist, count+1)
    else:
        return False

but for some reason it's not trying both ways to get to the last item on the list.

for example: [1,2,2,3,4,5,3,2,1,7,0] and ,start=mylist[0] it supposed to jump like this (from 1-2-4-1-left to 2-left to 5-right to 0) but it keeps trying to go right and then index is out of range etc.

I thought that if u use return of or this or that, it will try both until it reaches True, why won't it work here?

Thanks!

what is int? You should not be using variable names like that, because it is a type keyword in many languages, and it will confuse people. — AJMansfield
– AJMansfield, Commented Nov 15, 2013 at 17:01

AJMansfield · Accepted Answer · 2013-11-16 13:59:23Z

2

Include the value you want to keep as a default parameter for the method, like this:

def my_func(int, list, i=0):
    a = (i + int)
    if int == 0:
        return True
    elif a > len(list):
        i -= int
    else:
        i += int
    int = list[i]
    my_func(int, list, i)

Bear in mind that it may not even always be possible to arrive at the end of the list doing the jumping pattern you describe, and even if it is possible, this method may choose the wrong branch.

A better algorithm would look like this:

def branching_search(list, start):
    marks = [0]*len(list)
    pos = start
    while list[pos]!=0:
        marks[pos]++
        if marks[pos] % 2 == 0 and pos + list[pos] < len(list):
            pos += list[pos]
        elif marks[pos] % 2 == 1 and pos - list[pos] >= 0:
            pos -= list[pos]
        else:
            return False
        if all(item == 0 or item > 1 for item in list)
            return False
    return True

This way, if it comes to an item that it has already visited, it will decide to go the opposite direction that it went last time. Also, if it comes to an item that it can't leave without going out-of-bounds, or if there is not way to get to the end, it will give up and return.

EDIT: I realized there are a number of flaws in this algorithm! Although it is better than the first approach, it is not guaranteed to work, although the reasons are somewhat complicated.

Just imagine this array (the unimportant elements are left blank):

1, 2,  , 5,  ,  ,  ,  , 5, 0

The first two elements would get only one mark (thus the loop checking condition would not work), but it would still get stuck looping between the two fives.

Here is a method that will always work:

def flood_search(list):

    marks = [[]]*len(list)
    marks[0] = [0]
    still_moving = True

    while still_moving:
        still_moving = False

        for pos in range(0,len(list)):
            if marks[pos]:
                if pos + list[pos] < len(list) and not marks[pos + list[pos]]:
                    marks[pos + list[pos]] = marks[pos] + [list[pos]];
                    pos += list[pos]
                    still_moving = True

                if pos - list[pos] >= 0 and not marks[pos - list[pos]]:
                    marks[pos - list[pos]] = marks[pos] + [-list[pos]];
                    pos -= list[pos]
                    still_moving = True

    return marks[-1]

This works by taking every possible branch at the same time.

You can also use the method to get the actual route taken to get to the end. It can still be used as a condition, since it returns an empty list if no path is found (a falsy value), or a list containing the path if a path is found (a truthy value).

However, you can always just use list[-1] to get the last item.

edited Nov 16, 2013 at 13:59

answered Nov 15, 2013 at 17:04

AJMansfield

4,2123 gold badges32 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Mumfordwiz Over a year ago

I'm only using int, here for example it can be any int.

AJMansfield Over a year ago

@dav_sap That would be because you didn't call my_func with i as a parameter.

Mumfordwiz Over a year ago

yea I got it working, but it's not giving me exactly what I need, but maybe that's something with my code,

Mumfordwiz Over a year ago

I'm trying to understand where the line that says, that if it goes to an item that it already visited, that means there is no way out and return False.

Mumfordwiz Over a year ago

@AJ is it this one?if all(item == 0 || item > 2 for item in list)

|

Collectives™ on Stack Overflow

Keeping the variable 's value in recursive function, python 3.3

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related