Battle Moves - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 30 mins
  • 🛠️ Topics: Grid Traversal, Matrix Navigation

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 do if all possible moves have been made already?
    • Return an empty list if there are no valid moves.
  • Can I revisit moves?
    • No, any move in past_moves is invalid.
HAPPY CASE
Input: battle = [
    ['X', 'O', 'O', 'X', 'X'],
    ['O', 'O', 'O', 'X', 'X'],
    ['X', 'X', 'X', 'O', 'O'],
    ['X', 'X', 'X', 'X', 'O'],
    ['O', 'O', 'O', 'X', 'O']
], row = 3, column = 2, past_moves = []
Output: [(3, 1), (3, 3), (2, 2)]
Explanation: The valid adjacent cells (3, 1), (3, 3), and (2, 2) all belong to your territory.

EDGE CASE
Input: battle = [
    ['X', 'O', 'O', 'X', 'X'],
    ['O', 'O', 'O', 'X', 'X'],
    ['X', 'X', 'X', 'O', 'O'],
    ['X', 'X', 'X', 'X', 'O'],
    ['O', 'O', 'O', 'X', 'O']
], row = 0, column = 0, past_moves = []
Output: []
Explanation: All possible moves from this position are out of bounds or in enemy territory.

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:

  • Matrix Navigation: This problem involves moving in a grid and checking neighboring cells.
  • Bounds Checking: Ensure that any movement remains within the grid's valid indices.
  • Move Filtering: Remove moves that are in past_moves to avoid revisiting locations.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: From the given position (row, column), check all four directions (up, down, left, right) to see if the adjacent cells are within the grid bounds, belong to your kingdom's territory (X), and have not been visited before (i.e., not in past_moves).

1) Define the possible moves from the current position: up, down, left, right.
2) Initialize an empty list to store valid next moves.
3) Convert `past_moves` into a set for faster lookup.
4) For each candidate move:
    a) Check if the move is within the bounds of the grid.
    b) Check if the move leads to a cell that is part of your kingdom's captured territory (i.e., `X`).
    c) Check if the move is not in `past_moves`.
5) Add any valid move to the list of next moves.
6) Return the list of valid next moves.

⚠️ Common Mistakes

  • Forgetting to check grid boundaries can result in out-of-bounds errors.
  • Failing to account for already visited moves can lead to repeated moves.

4: I-mplement

Implement the code to solve the algorithm.

def next_moves(battle, row, column, past_moves):
    
    # Holds each candidate position (moving down, up, right, left)
    moves = [
        (row + 1, column),  # down
        (row - 1, column),  # up
        (row, column + 1),  # right
        (row, column - 1)   # left
    ]
    
    possible = []
    
    # Convert past_moves to a set for faster lookup
    past_moves_set = set(past_moves)
    
    # For each candidate move
    for r, c in moves:
        # Check that the move is within bounds and is part of your territory (X)
        if (0 <= r < len(battle)
            and 0 <= c < len(battle[0])
            and battle[r][c] == 'X'
            and (r, c) not in past_moves_set):
            # If it satisfies all requirements, add it to the possible moves
            possible.append((r, c))
    
    return possible

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: battle = [ ['X', 'O', 'O', 'X', 'X'], ['O', 'O', 'O', 'X', 'X'], ['X', 'X', 'X', 'O', 'O'], ['X', 'X', 'X', 'X', 'O'], ['O', 'O', 'O', 'X', 'O'] ], row = 3, column = 2, past_moves = []
  • Expected Output: [(3, 1), (3, 3), (2, 2)]
  • Watchlist:
    • Ensure that past_moves_set is correctly used to filter out previous moves.
    • Verify that only valid adjacent cells are being included in the result.

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(1) because we are only checking four adjacent cells.
  • Space Complexity: O(1) as no additional space is required except for the result list.