Recursion Return Wrong List Of Lists

I try to solve a problem and one part of it is to find all paths from (0, 0) to the right most point of the 2d array. This is my code: def route_finder_helper(x, y, current_path, f

Solution 1:

This is the corrected answer:

def route_finder_helper(x, y, current_path, filler, list_of_lists):

    current_path[filler] = (x, y)

    if x ==0and y ==0:
        return list_of_lists + [current_path[:]]

    if x ==0:
        return route_finder_helper(x, y -1, current_path, filler -1, list_of_lists)

    if y ==0:
        return route_finder_helper(x -1, y, current_path, filler -1, list_of_lists)

    return route_finder_helper(x-1, y, current_path, filler -1, list_of_lists) + \
           route_finder_helper(x, y-1, current_path, filler -1, list_of_lists)

x_coordinate =2
y_coordinate =2
path_length = (x_coordinate +1) + (y_coordinate +1) -1
start_filling = path_length -1current_path= [0] * path_length
paths = route_finder_helper(x_coordinate, y_coordinate, current_path, start_filling, [])
print(paths)

Output:

[[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)], 
[(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)], 
[(0, 0), (1, 0), (1, 1), (1, 2), (2, 2)], 
[(0, 0), (0, 1), (1, 1), (2, 1), (2, 2)], 
[(0, 0), (1, 0), (1, 1), (2, 1), (2, 2)], 
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]]

The correction here is:

return list_of_lists + [current_path[:]]

where I add a copy by using current_path[:]

Solution 2:

The logic of the code is correct, the problem that you have is that you are dealing with a list which is a mutable item. This means that every variable which has a reference to the list, gets an updated list when you change it for only one variable:

a = [1, 2, 3]
b = a
a[0] = -1
print(b)
>>> [-1, 2, 3]

Something like this also happens in your code when you append to the list_of_lists. Simply changing the append to this:

# return list_of_lists.append(current_path)  <-old code
return list_of_lists + [current_path]  <-new code

This guarantees that you start a new list every time the code ends up there, instead of appending to a list where other parts of the code have a reference to as well.

If this is a new concept for you in Python there are plenty of nice blogs which explain this in more detail than me, e.g. here

complete code:

def route_finder_helper(x, y, current_path, filler, list_of_lists):

    current_path[filler] = (x, y)

    if x ==0and y ==0:
        return list_of_lists + [current_path]

    if x ==0:
        return route_finder_helper(x, y -1, current_path, filler -1, list_of_lists)

    if y ==0:
        return route_finder_helper(x -1, y, current_path, filler -1, list_of_lists)

    return route_finder_helper(x-1, y, current_path, filler -1, list_of_lists) + \
           route_finder_helper(x, y-1, current_path, filler -1, list_of_lists)

x_coordinate =2
y_coordinate =2
path_length = (x_coordinate +1) + (y_coordinate +1) -1
start_filling = path_length -1current_path= [0] * path_length
paths = route_finder_helper(x_coordinate, y_coordinate, current_path, start_filling, [])
print(paths)
>>> [[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]]