Please find invisible bug in my code on a route planner exercise

Question

I am trying to solve this exercise:

As a part of the route planner, the route_exists method is used as a quick filter if the destination is reachable, before using more computationally intensive procedures for finding the optimal route. The roads on the map are rasterized and produce a matrix of boolean values - True if the road is present or False if it is not. The roads in the matrix are connected only if the road is immediately left, right, below or above it. Finish the route_exists method so that it returns True if the destination is reachable or False if it is not. The from_row and from_column parameters are the starting row and column in the map_matrix. The to_row and to_column are the destination row and column in the map_matrix. The map_matrix parameter is the above mentioned matrix produced from the map. For example, the following code should return True since destination is reachable:

map_matrix = [
    [True, False, False],
    [True, True, False],
    [False, True, True]
];

route_exists(0, 0, 2, 2, map_matrix)

My solution with recursion:

def route_exists(from_row, from_column, to_row, to_column, map_matrix):
    if route_exists2(from_row, from_column, to_row, to_column, map_matrix):
        return True
    else:
        return False
def route_exists2(from_row, from_column, to_row, to_column, map_matrix):
    if (from_row<0 or from_row>=len(map_matrix) or from_column<0 or from_column>=len(map_matrix[0])):
        return False
    if map_matrix[from_row][from_column]:
        map_matrix[from_row][from_column]=False #traversed
        if (from_row == to_row and from_column ==to_column):
            return True
        return (route_exists2(from_row-1, from_column, to_row, to_column, map_matrix) or
                route_exists2(from_row, from_column-1, to_row, to_column, map_matrix) or
                route_exists2(from_row, from_column+1, to_row, to_column, map_matrix) or
                route_exists2(from_row+1, from_column, to_row, to_column, map_matrix))
        
if __name__ == '__main__':
    map_matrix = [
        [True, False, False],
        [True, True, False],
        [False, True, True]
    ];

    print(route_exists(0, 0, 2, 2, map_matrix))

I only get 50% on the 4 test cases of this exercise with logical errors and I can't recreate the bug from the test cases.

Answer 1

The final solution that @Frank Yellin mentioned.

def route_exists(from_row, from_column, to_row, to_column, map_matrix):
    visited = [[False for i in range(len(map_matrix[0]))] for j in range(len(map_matrix))]
    
    def route_exists2(from_row, from_column, to_row, to_column, map_matrix):
        if (from_row<0 or from_row>=len(map_matrix) or from_column<0 or from_column>=len(map_matrix[0]) or visited[from_row][from_column]==True):
            return False
        if map_matrix[from_row][from_column]:
            visited[from_row][from_column]=True
            #map_matrix[from_row][from_column]=False #traversed
            if (from_row == to_row and from_column ==to_column):
                return True
            return (route_exists2(from_row-1, from_column, to_row, to_column, map_matrix) or
                    route_exists2(from_row, from_column-1, to_row, to_column, map_matrix) or
                    route_exists2(from_row, from_column+1, to_row, to_column, map_matrix) or
                    route_exists2(from_row+1, from_column, to_row, to_column, map_matrix))

    
    if route_exists2(from_row, from_column, to_row, to_column, map_matrix):
        return True
    else:
        return False
    
    
if __name__ == '__main__':
    map_matrix = [
        [True, False, False],
        [True, True, False],
        [False, True, True]
    ];
    

    print(route_exists(0, 0, 2, 2, map_matrix))

It scores 4/4!

Answer 2

One possible approach is to map all the possible valid destinations given a start point, and then check if the desired destination is contemplated. I guess this is what you are trying to achieve on your recursive call by trying to split the end of your route_exists() in several route_exists() calls. But the problem, as pointed by Frank Yellin, is that when a first recursive call is fully resolved your are setting all the roads of that path to False, thus avoiding other possible paths to use those roads. I would rather try to store the last new routes and interact over them.

def route_exists(start_x, start_y, end_x, end_y, map_matrix):
    possible_routes = [[[start_x, start_y]]]
        # each route is a list of [x, y] points indicating all the route roads  
    added_routes = 0
    
    while True:
        routes_count = len(possible_routes)
        for route in possible_routes[-added_routes:]:
            # check only the active new rotes and their possible roads
            for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                road_x = route[-1][0] + x
                road_y = route[-1][1] + y
                    # the possible road at the route end
                try:
                    if map_matrix[road_x][road_y]: # the road exists
                        if [road_x, road_y] not in route: # not going backwards
                            new_route = route + [[road_x, road_y]]
                            if new_route not in possible_routes:
                                possible_routes.append(new_route)
                except:
                    pass

        added_routes = len(possible_routes) - routes_count
        if added_routes == 0:
            break

    destinations = [r[-1] for r in possible_routes]
    if [end_x, end_y] in destinations:
        return True
    else:
        return False

this method checks and stores all possible roads and I guess it will solve the problem, but it will consume memory as the map_matrix goes bigger so I encourage you to change it as your needs.

Answer 3

You need to change the end to be:

result = (rout_exists2..........)
map_matrix[from_row][from_column] = True
return result

When you've made a recursive call and then return back to your caller, you need to undo any changes that you've made to the state.

===== Expanding my answer ======

Imagine the outer call to route_exists2(). It wants to make four recursive calls to route_exists2(), and the matrix it wants to pass to each of those four recursive calls is the matrix it received, with one cell changed. But each of those four recursive calls could further modify the matrix, and those changes are never undone.