Solution to planning bunnies escape?

[tanzeelrana]

I have a python solution and a java solution but both seem to be exceeding the time limit can someone help me on the code ?

Python Code

 from collections import deque

 def memodict(f):
    """ Memoization decorator for a function taking a single argument """
    class memodict(dict):

        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret
    return memodict().__getitem__

 @memodict
 def adjacent_to((maze_dim, point)):
    neighbors = (
        (point[0] - 1, point[1]),
        (point[0], point[1] - 1),
        (point[0], point[1] + 1),
        (point[0] + 1, point[1]))

    return [p for p in neighbors if 0 <= p[0] < maze_dim[0] and 0 <= p[1] < maze_dim[1]]

 def removable(maz, ii, jj):
    counter = 0
    for p in adjacent_to(((len(maz), len(maz[0])), (ii, jj))):
        if not maz[p[0]][p[1]]:
            if counter:
                return True
            counter += 1
    return False

 def answer(maze):

    path_length = 0

    if not maze:
        return

    dims = (len(maze), len(maze[0]))
    end_point = (dims[0]-1, dims[1]-1)

    # list of walls that can be removed
    passable_walls = set()
    for i in xrange(dims[0]):
        for j in xrange(dims[1]):
            if maze[i][j] == 1 and removable(maze, i, j):
                passable_walls.add((i, j))

    shortest_path = 0
    best_possible = dims[0] + dims[1] - 1

    path_mat = [[None] * dims[1] for _ in xrange(dims[0])]  # tracker matrix for shortest path
    path_mat[dims[0]-1][dims[1]-1] = 0  # set the starting point to destination (lower right corner)

    for wall in passable_walls:
        temp_maze = maze
        if wall:
            temp_maze[wall[0]][wall[1]] = 0

        stat_mat = [['-'] * dims[1] for _ in xrange(dims[0])]  # status of visited and non visited cells

        q = deque()
        q.append(end_point)

        while q:
            curr = q.popleft()

            if curr == (0,0):
                break

            for next in adjacent_to((dims, curr)):
                if temp_maze[next[0]][next[1]] == 0:  # Not a wall
                    temp = path_mat[curr[0]][curr[1]] + 1
                    if temp < path_mat[next[0]][next[1]] or path_mat[next[0]][next[1]] == None:  # there is a shorter path to this cell
                        path_mat[next[0]][next[1]] = temp
                    if stat_mat[next[0]][next[1]] != '+':  # Not visited yet
                        q.append(next)

            stat_mat[curr[0]][curr[1]] = '+'  # mark it as visited

        if path_mat[0][0]+1 <= best_possible:
            break        

    if shortest_path == 0 or path_mat[0][0]+1 < shortest_path:
        shortest_path = path_mat[0][0]+1

    return shortest_path

Java Code :

package googleTest;

public class Answer {

    public static int answer(int[][] maze) {

        // Your code goes here.
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        return dfs(0, 0, true, visited, maze, 1);
    }

    private static int dfs(int x, int y, boolean allowRemove, boolean[][] visited, int[][] maze, int len){
        if(x == maze.length - 1 && y == maze[0].length - 1){
            return len;
        }
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};
        visited[x][y] = true;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < 4; i++){
           int nx = dx[i] + x;
           int ny = dy[i] + y;
           if(nx < 0 || ny < 0 || nx >= maze.length || ny >= maze[0].length || visited[nx][ny]){
               continue;
           }
           if(maze[nx][ny] == 0){
               min = Math.min(dfs(nx, ny, allowRemove, visited, maze, len + 1), min);
           }else if(allowRemove){
               min = Math.min(dfs(nx, ny, false, visited, maze, len + 1), min);
           }
           if(min == maze.length + maze[0].length - 1){
               break;
           }
        }
        visited[x][y] = false;
        return min;
    }

    public static void main(String[] args) {
        int[][] maze1 = new int[][]{{ 0, 1, 1, 0},{ 0, 0, 0, 1 },{ 1, 1, 0, 0 },{ 1, 1, 1, 0 }};
        System.out.println(answer(maze1));
        int [][] maze2 = new int[][] {{0, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 0}, {0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0}};
        System.out.println(answer(maze2));
    }

}

[ivanseed]

Just had a quick look over the Java.

I think the first step you would want to calculate the shortest distance from start to finish using Dijkstra for example to give you an upper bound.vNow you know that there could be a better possible solution, depending on how you represent data you could store the shortest path to each point from start so you know how long it takes to get from start to every node.

Because you know the current upper bound; go to each wall and calculate distance from wall to end without crossing any other walls again. You will get an answer wallToEndDistance which you will need to add to startToWallDistance. Compare totalDistance to currentMin. You only need to calculate the algorithm for the starting node, and every wall that startToWallDistance < currentMin. After you exhausted all possible walls you have the min, I think you were calculating DFS too many times as it was recursive but really distance calculations should only be called 1-30 times.

There is actually a way to do this using A if you prefer to use that, the data structure used by A may be more helpful.

It might be worth storing the nodes aa a data structure that contains x y isWall and distance, distance = startToNode, then also having a list of wall nodes. This way you can just refer to your list and see which wall you have not calculated all the shortest distance for. For weight you can just use isWall*100000 + 1 for example.