2
\$\begingroup\$

This is a question I received as part of the Foobar challenge:

You're awfullyclose to destroying the LAMBCHOP doomsday device and freeing Commander Lambda's bunny prisoners, but once they're free of the prison blocks, the bunnies are going to need to escape Lambda's space station via the escape pods as quickly as possible. Unfortunately, the halls of the space station are a maze of corridors and dead ends that will be a deathtrap for the escaping bunnies. Fortunately, Commander Lambda has put you in charge of a remodeling project that will give you the opportunity to make things a little easier for the bunnies. Unfortunately (again), you can't just remove all obstacles between the bunnies and the escape pods - at most you can remove one wall per escape pod path, both to maintain structural integrity of the station and to avoid arousing Commander Lambda's suspicions.

You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the prison is at the top left (0,0) and the door into an escape pod is at the bottom right (w-1,h-1).

Write a function answer(map) that generates the length of the shortest path from the prison door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans. The path length is the total number of nodes you pass through, counting both the entrance and exit nodes. The starting and ending positions are always passable (0). The map will always be solvable, though you may or may not need to remove a wall. The height and width of the map can be from 2 to 20. Moves can only be made in cardinal directions; no diagonal moves are allowed.

This is the code Foobar says that is taking too much time to execute. How can I make it faster?

Test cases

Inputs:

(int) maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]

Output:

(int) 7

Inputs:

(int) maze = [[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]]

Output:

(int) 11

def bfs(maze, start_point):
    import collections
    queue_positions = collections.deque()
    queue_positions.append(start_point)
    len_maze = len(maze[0])
    hei_maze = len(maze)
    step_map = [[0 for i in range(len_maze)] for j in range(hei_maze)]
    step_map[start_point[0]][start_point[1]] = 1
    while queue_positions:
        c_pos = queue_positions.popleft()
        if c_pos[1] == len_maze - 1 and c_pos[0] == hei_maze - 1:
            return step_map
        #go up
        if c_pos[0] > 0 and step_map[c_pos[0] - 1][c_pos[1]] == 0 and maze[c_pos[0] - 1][c_pos[1]] == 0:
            step_map[c_pos[0] - 1][c_pos[1]] = c_pos[2] + 1
            queue_positions.append([c_pos[0] - 1, c_pos[1],c_pos[2] + 1])
        #go down
        if c_pos[0] < hei_maze - 1 and step_map[c_pos[0] + 1][c_pos[1]] == 0 and maze[c_pos[0] + 1][c_pos[1]] == 0:
            step_map[c_pos[0] + 1][c_pos[1]] = c_pos[2] + 1
            queue_positions.append([c_pos[0] + 1, c_pos[1],c_pos[2] + 1])
        #go left
        if c_pos[1] > 0 and step_map[c_pos[0]][c_pos[1] - 1] == 0 and maze[c_pos[0]][c_pos[1] - 1] == 0:
            step_map[c_pos[0]][c_pos[1] - 1] = c_pos[2] + 1
            queue_positions.append([c_pos[0], c_pos[1] - 1, c_pos[2] + 1])
        #go right
        if c_pos[1] < len_maze - 1 and step_map[c_pos[0]][c_pos[1] + 1] == 0 and maze[c_pos[0]][c_pos[1] + 1] == 0:
            step_map[c_pos[0]][c_pos[1] + 1] = c_pos[2] + 1
            queue_positions.append([c_pos[0], c_pos[1] + 1, c_pos[2] + 1])
        print step_map
    return step_map

# print bfs(maze, [0,0,1])

def find_certified_pos(maze, step_map, pos):
    count = 0
    len_maze = len(maze[0])
    hei_maze = len(maze)
    least_step = 1 << 31
    for i, j in [[1,0], [-1,0], [0,1], [0,-1]]:
        i2 = pos[0] + i
        j2 = pos[1] + j
        if i2 < 0 or i2 == hei_maze or j2 < 0 or j2 == len_maze:
            continue
        elif maze[i2][j2] == 0:
            count += 1
            if step_map[i2][j2] > 0:
                least_step = min(step_map[i2][j2], least_step)
    if count >= 2 or (pos[0] == hei_maze - 1 and pos[1] == len_maze - 1):
        return least_step
    else:
        return False

def find_shortest_one_move_path(maze):
    len_maze = len(maze[0])
    hei_maze = len(maze)
    step_map = bfs(maze, [0,0,1])
    print step_map
    best_step = step_map[hei_maze-1][len_maze-1]
    print "best" + str(best_step)
    if best_step == len_maze + hei_maze - 1:
        return best_step
    least_step = 0
    answer_step = 1 << 31
    for i in range(hei_maze):
        for j in range(len_maze):
            if maze[i][j] == 1:
                least_step = find_certified_pos(maze, step_map, [i, j])
            if least_step:
                step = bfs(maze, [i, j, 1])
                if step[hei_maze-1][len_maze-1] != 0:
                    answer_step = min(least_step + step[hei_maze-1][len_maze-1], answer_step)
            if answer_step == hei_maze + len_maze - 1:
                return answer_step
    return answer_step
\$\endgroup\$
  • \$\begingroup\$ Please fix your indentation. The easiest way to post code is to paste it into the question editor, highlight it, and press Ctrl-K to mark it as a code block. \$\endgroup\$ – 200_success Sep 11 '17 at 14:19
  • \$\begingroup\$ i have done it please check it \$\endgroup\$ – Anand Sep 11 '17 at 14:22
  • \$\begingroup\$ Welcome to the site: you may want to read [mcve], and re-word your question accordingly. \$\endgroup\$ – boardrider Sep 12 '17 at 9:25
  • \$\begingroup\$ @boardrider Note that on Code Review we actually don't want just a minimal example. We want the actual implementation, because only then can you see other bad things the OP does. Therefore, there is no link to [mcve] here :) \$\endgroup\$ – Graipher Sep 13 '17 at 7:32
  • \$\begingroup\$ Unfortunately, @Graipher, there's no entry in the site's help that shows only the [cve] aspects of [mcve]. I hoped the OP would be smart enough to take the applicable lessons from [mcve] while ignoring the inapplicable ones. Maybe the powers-that-be on codereview.stackexchange.com could adapt the SO [mcve] to a [cve] suitable for codereview.stackexchange.com? \$\endgroup\$ – boardrider Sep 13 '17 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.