Escape the Dungeon - codepath/compsci_guides GitHub Wiki

Unit 11 Session 2 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 45 mins
  • 🛠️ Topics: Grid Traversal, Breadth-First Search (BFS), Pathfinding

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • How do movements in the dungeon work?
    • You continue moving in a direction until you hit a wall, at which point you can stop and choose a new direction.
  • Can you stop at the exit even if you pass through it during a roll?
    • No, you must stop exactly at the exit to escape.
HAPPY CASE
Input: dungeon = [
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 1, 1],
    [0, 0, 0, 0, 0]
], position = (0, 4), exit = (4, 4)
Output: True
Explanation: You can escape by rolling left to (0,1), down to (4,1), and right to (4,4).

EDGE CASE
Input: dungeon = [
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 1, 1],
    [0, 0, 0, 0, 0]
], position = (0, 4), exit = (3, 2)
Output: False
Explanation: No way to stop at the exit.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Pathfinding problems, we want to consider the following approaches:

  • Breadth-First Search (BFS): BFS is a suitable choice for finding the shortest path in an unweighted grid.
  • Grid Traversal: We need to simulate movement in the grid by continuously moving in one direction until hitting a wall, then attempting new directions.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Start BFS from the given position and explore all possible moves in the dungeon. Each time you stop, enqueue the new position and continue exploring. If you stop at the exit, return True. If BFS completes without stopping at the exit, return False.

1) Define a helper function `next_position` to calculate the next stop in the given direction.
2) Initialize BFS from the starting position, tracking visited cells to avoid cycles.
3) For each position in the BFS queue:
    a) Attempt to move in all four directions.
    b) If you stop at the exit, return `True`.
    c) Otherwise, enqueue the new position and continue BFS.
4) If BFS completes without finding the exit, return `False`.

⚠️ Common Mistakes

  • Forgetting to mark cells as visited after stopping.
  • Not handling the case where the start and exit are the same.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

# Helper function to calculate the next stop in the given direction
def next_position(dungeon, row, col, direction):
    moves = {
        'up': (-1, 0),
        'down': (1, 0),
        'left': (0, -1),
        'right': (0, 1)
    }
    
    dr, dc = moves[direction]
    while 0 <= row + dr < len(dungeon) and 0 <= col + dc < len(dungeon[0]) and dungeon[row + dr][col + dc] == 0:
        row += dr
        col += dc
    
    return row, col

# Main function to check if you can escape the dungeon
def can_escape_dungeon(dungeon, position, exit):
    rows, cols = len(dungeon), len(dungeon[0])
    start_row, start_col = position
    exit_row, exit_col = exit
    
    # If starting point is already the exit
    if (start_row, start_col) == (exit_row, exit_col):
        return True
    
    visited = set()
    queue = deque([(start_row, start_col)])  # Start BFS from the given position
    visited.add((start_row, start_col))
    
    directions = ['up', 'down', 'left', 'right']
    
    while queue:
        current_row, current_col = queue.popleft()
        
        for direction in directions:
            new_row, new_col = next_position(dungeon, current_row, current_col, direction)
            
            if (new_row, new_col) == (exit_row, exit_col):
                return True
            
            if (new_row, new_col) not in visited:
                visited.add((new_row, new_col))
                queue.append((new_row, new_col))
    
    return False

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

  • Input: dungeon = [ [0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [1, 1, 0, 1, 1], [0, 0, 0, 0, 0] ], position = (0, 4), exit = (4, 4)
  • Expected Output: True
  • Watchlist:
    • Ensure that BFS correctly explores all valid moves.
    • Verify that stopping positions are calculated correctly.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume m is the number of rows and n is the number of columns in the grid.

  • Time Complexity: O(m * n) because each cell is visited once during BFS.
  • Space Complexity: O(m * n) due to the BFS queue and visited set.