Castle Path - codepath/compsci_guides GitHub Wiki

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

Unit 11 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 45 mins
  • 🛠️ Topics: Grid Traversal, Breadth-First Search, 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?
  • Can I move diagonally?
    • No, only horizontal and vertical adjacent moves are allowed.
  • What should I return if I start at the castle?
    • Return the starting position as the path.
  • Can I travel through bandit towns?
    • No, towns marked O are impassable.
  • Can there be multiple valid paths?
    • Yes, any valid path can be returned.
HAPPY CASE
Input: kingdom = [
    ['X', 'O', 'X', 'X', 'O'],
    ['X', 'X', 'X', 'X', 'O'],
    ['O', 'O', 'X', 'X', 'O'],
    ['X', 'O', 'X', 'X', 'X']
], town = (0, 0), castle = (3, 4)
Output: [(0, 0), (1, 0), (1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 4)]
Explanation: This is one valid path from the starting town to the castle.

EDGE CASE
Input: kingdom = [
    ['X', 'O', 'X', 'X', 'O'],
    ['X', 'X', 'X', 'X', 'O'],
    ['O', 'O', 'X', 'X', 'O'],
    ['X', 'O', 'X', 'X', 'X']
], town = (0, 4), castle = (3, 4)
Output: None
Explanation: There is no path from the starting position (0, 4) to the castle (3, 4) because the path is blocked by bandits.

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 Grid Traversal problems, we want to consider the following approaches:

  • Breadth-First Search (BFS): BFS is well-suited for finding the shortest path in an unweighted grid where all edges (moves) have equal cost.
  • Graph Representation: Treat the grid as a graph where each town is a node, and edges exist between safe neighboring towns.
  • Queue: Use a queue to implement BFS and track the current position and path.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use BFS to explore the grid, starting from the given town, and track the path taken. At each step, only consider moves to safe neighboring towns (marked X) that have not been visited yet. Stop once the castle is reached and return the path. If no valid path exists, return None.

1) Define a helper function `get_neighbors` to return valid adjacent safe towns.
2) Initialize a BFS queue with the starting position and path so far.
3) Use a set to keep track of visited towns.
4) Perform BFS:
    a) For each position, check its valid neighbors.
    b) If a neighbor is the castle, return the path.
    c) If not, add the neighbor to the queue and mark it as visited.
5) If BFS completes without finding the castle, return `None`.

⚠️ Common Mistakes

  • Forgetting to mark towns as visited can lead to infinite loops.
  • Not accounting for cases where the starting position is the same as the castle.
  • Failing to handle edge cases where no path exists.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

# Helper function to get valid neighboring towns
def get_neighbors(position, kingdom, visited):
    row, col = position
    moves = [
        (row + 1, col),  # down
        (row - 1, col),  # up
        (row, col + 1),  # right
        (row, col - 1)   # left
    ]
    
    neighbors = []
    for r, c in moves:
        if (0 <= r < len(kingdom)
            and 0 <= c < len(kingdom[0])
            and kingdom[r][c] == 'X'
            and (r, c) not in visited):
            neighbors.append((r, c))
    
    return neighbors

# Main function to find the path to the castle
def path_to_castle(kingdom, town, castle):
    if town == castle:
        return [town]
    
    # Initialize BFS queue and visited set
    queue = deque([(town, [town])])  # (current position, path so far)
    visited = set([town])
    
    while queue:
        current_position, path = queue.popleft()
        
        # Get all valid neighboring towns (marked 'X' and not visited)
        for neighbor in get_neighbors(current_position, kingdom, visited):
            if neighbor == castle:
                return path + [neighbor]  # Return the full path if we reach the castle
            
            # If not the castle, add to the queue and mark as visited
            visited.add(neighbor)
            queue.append((neighbor, path + [neighbor]))
    
    # If BFS completes without finding the castle, return None
    return None

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: kingdom = [ ['X', 'O', 'X', 'X', 'O'], ['X', 'X', 'X', 'X', 'O'], ['O', 'O', 'X', 'X', 'O'], ['X', 'O', 'X', 'X', 'X'] ], town = (0, 0), castle = (3, 4)
  • Expected Output: [(0, 0), (1, 0), (1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 4)]
  • Watchlist:
    • Ensure that all valid neighbors are correctly identified.
    • Check that the path is constructed correctly during BFS.
    • Verify that BFS stops as soon as the castle is reached.

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 in the worst case, we must explore all towns in the kingdom.
  • Space Complexity: O(m * n) due to the queue and the visited set.