Taro Logo

Cat and Mouse II

#351 Most AskedHard
47 views
Topics:
GraphsDynamic Programming

A game is played by a cat and a mouse named Cat and Mouse.

The environment is represented by a grid of size rows x cols, where each element is a wall, floor, player (Cat, Mouse), or food.

  • Players are represented by the characters 'C'(Cat),'M'(Mouse).
  • Floors are represented by the character '.' and can be walked on.
  • Walls are represented by the character '#' and cannot be walked on.
  • Food is represented by the character 'F' and can be walked on.
  • There is only one of each character 'C', 'M', and 'F' in grid.

Mouse and Cat play according to the following rules:

  • Mouse moves first, then they take turns to move.
  • During each turn, Cat and Mouse can jump in one of the four directions (left, right, up, down). They cannot jump over the wall nor outside of the grid.
  • catJump, mouseJump are the maximum lengths Cat and Mouse can jump at a time, respectively. Cat and Mouse can jump less than the maximum length.
  • Staying in the same position is allowed.
  • Mouse can jump over Cat.

The game can end in 4 ways:

  • If Cat occupies the same position as Mouse, Cat wins.
  • If Cat reaches the food first, Cat wins.
  • If Mouse reaches the food first, Mouse wins.
  • If Mouse cannot get to the food within 1000 turns, Cat wins.

Given a rows x cols matrix grid and two integers catJump and mouseJump, return true if Mouse can win the game if both Cat and Mouse play optimally, otherwise return false.

Example 1:

Input: grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2
Output: true
Explanation: Cat cannot catch Mouse on its turn nor can it get the food before Mouse.

Example 2:

Input: grid = ["M.C...F"], catJump = 1, mouseJump = 4
Output: true

Example 3:

Input: grid = ["M.C...F"], catJump = 1, mouseJump = 3
Output: false

Constraints:

  • rows == grid.length
  • cols = grid[i].length
  • 1 <= rows, cols <= 8
  • grid[i][j] consist only of characters 'C', 'M', 'F', '.', and '#'.
  • There is only one of each character 'C', 'M', and 'F' in grid.
  • 1 <= catJump, mouseJump <= 8

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the dimensions of the grid and the maximum value of 'jump'? Are there any constraints on these values?
  2. Can the initial positions of the cat and mouse, and the food, be the same? Can the cat, mouse, or food positions be outside the grid?
  3. If the mouse can never reach the food, what should I return?
  4. If both the cat and the mouse reach the food in the same number of moves, who wins (or is it a draw)?
  5. Can the grid contain any obstacles or other elements besides the empty space?

Brute Force Solution

Approach

The brute force approach to the Cat and Mouse II game involves trying every possible sequence of moves for both the cat and the mouse. We explore all combinations of movements until we find a scenario where the mouse wins or we've exhausted all possibilities.

Here's how the algorithm would work step-by-step:

  1. Imagine the game board and the current positions of the cat and mouse.
  2. Enumerate all possible moves the mouse can make from its current position.
  3. For each of the mouse's possible moves, enumerate all possible moves the cat can make in response.
  4. For each of these cat-mouse move combinations, check if the mouse has won (reached the food) or if the cat has won (caught the mouse).
  5. If neither player has won, consider this new board state and recursively repeat the process, exploring all possible mouse moves followed by all possible cat moves from *this* new state.
  6. Continue exploring these possibilities until we find a sequence of moves where the mouse wins, the cat wins, or we reach a point where we've exceeded a move limit or visited a state too many times.
  7. If the mouse can eventually win through at least one path of moves, we determine that the mouse wins overall. Otherwise, the cat wins.

Code Implementation

def cat_and_mouse_ii_brute_force(grid, cat_jump, mouse_jump, food):
    rows = len(grid)
    cols = len(grid[0])

    mouse_start = None
    cat_start = None

    for row_index in range(rows):
        for col_index in range(cols):
            if grid[row_index][col_index] == 'M':
                mouse_start = (row_index, col_index)
            elif grid[row_index][col_index] == 'C':
                cat_start = (row_index, col_index)

    def get_possible_moves(position, jump_distance):
        possible_moves = []
        row, col = position

        # Stay in place
        possible_moves.append((row, col))

        # Move in all four directions
        for move_row in range(row - jump_distance, row + jump_distance + 1):
            for move_col in range(col - jump_distance, col + jump_distance + 1):
                if abs(move_row - row) + abs(move_col - col) <= jump_distance:
                    if 0 <= move_row < rows and 0 <= move_col < cols and grid[move_row][move_col] != '#':
                        possible_moves.append((move_row, move_col))

        return possible_moves

    def mouse_wins(mouse_position, food_position):
        return mouse_position == food_position

    def cat_wins(mouse_position, cat_position):
        return mouse_position == cat_position

    def solve(mouse_position, cat_position, move_count):
        # Limit the number of moves to prevent infinite recursion
        if move_count > 100:
            return False

        # Check if the mouse wins
        if mouse_wins(mouse_position, food):
            return True

        # Check if the cat wins
        if cat_wins(mouse_position, cat_position):
            return False

        # Iterate through all possible mouse moves
        mouse_moves = get_possible_moves(mouse_position, mouse_jump)

        for next_mouse_position in mouse_moves:
            # Iterate through all possible cat moves
            cat_moves = get_possible_moves(cat_position, cat_jump)

            all_cat_wins = True
            for next_cat_position in cat_moves:

                # Recursively call the solve function after cat makes move
                if solve(next_mouse_position, next_cat_position, move_count + 1):
                    all_cat_wins = False
                    break

            # If the cat loses in ALL possibilities, mouse wins.
            if all_cat_wins:
                return True

        # If the mouse can't win in any possible scenario, cat wins.
        return False

    return solve(mouse_start, cat_start, 0)

Big(O) Analysis

Time Complexity
O((m*n)^(catJump+mouseJump)^turns) – The brute force approach explores every possible move sequence. The number of reachable positions for each player on the m*n board is limited by their jump distances, catJump and mouseJump, leading to roughly (m*n)^(catJump+mouseJump) possible locations for each turn. Since the algorithm searches up to 'turns' number of moves, the time complexity grows exponentially with the number of turns and the board size and jump distances, resulting in O((m*n)^(catJump+mouseJump)^turns).
Space Complexity
O(R * C * D) – The algorithm uses recursion to explore all possible move sequences. The maximum depth of the recursion is limited by the move limit, let's call it D. At each level of the recursion, we essentially store the current state of the game, which consists of the mouse's position, the cat's position, and the food's position. The mouse and cat positions are defined by their row and column indices. If R is the number of rows and C is the number of columns on the board, then there are at most R * C possible locations for the mouse and the cat, respectively. The recursion stack can grow up to D levels deep, thus creating a space complexity of O(R * C * D), where D is the number of moves.

Optimal Solution

Approach

This is a game of cat and mouse, but it takes place on a grid. We need to figure out if the cat can catch the mouse before the mouse escapes, considering both can only move a certain distance each turn.

Here's how the algorithm would work step-by-step:

  1. The core idea is to see if we can reach a point in the game where we already know the answer. This happens when one of them wins or if we've been in the same position too many times, signaling a draw.
  2. Let's start by thinking about what it means for the mouse to win. The mouse wins if it can reach the food before the cat catches it or reach the edge of the board to escape.
  3. Now, what if the cat catches the mouse? That means the cat is close enough to the mouse (on the same spot or within its jump distance).
  4. We'll explore all possible moves by both the cat and mouse, one turn at a time. We can use something like a method that looks at the possible positions they can move to at each turn.
  5. To avoid infinite loops, we remember the game states we have already visited. A 'game state' is just the positions of the cat and mouse and the number of turns taken.
  6. If a game state repeats, it's a draw because neither player can force a win, and we stop exploring from that point.
  7. After checking all the possible moves within a limited number of turns, we can decide whether the cat catches the mouse, the mouse escapes, or it's a draw.

Code Implementation

def cat_and_mouse(grid, cat_jump, mouse_jump, food):
    rows = len(grid)
    cols = len(grid[0])
    mouse_start = None
    cat_start = None
    for row_index in range(rows):
        for col_index in range(cols):
            if grid[row_index][col_index] == 'M':
                mouse_start = (row_index, col_index)
            elif grid[row_index][col_index] == 'C':
                cat_start = (row_index, col_index)

    def get_neighbors(row, col, jump):
        neighbors = []
        for delta_row in range(-jump, jump + 1):
            for delta_col in range(-jump, jump + 1):
                if abs(delta_row) + abs(delta_col) <= jump:
                    new_row = row + delta_row
                    new_col = col + delta_col
                    if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] != '#':
                        neighbors.append((new_row, new_col))
        return neighbors

    def can_win(mouse_row, mouse_col, cat_row, cat_col, turn, visited):
        # Early exit for repeated states.
        if turn > 1000:
            return False
        if (mouse_row, mouse_col, cat_row, cat_col, turn) in visited:
            return False

        visited.add((mouse_row, mouse_col, cat_row, cat_col, turn))

        # Mouse's turn
        if turn % 2 == 0:
            neighbors = get_neighbors(mouse_row, mouse_col, mouse_jump)
            for next_mouse_row, next_mouse_col in neighbors:

                # Check if the mouse reaches food
                if next_mouse_row == food[0] and next_mouse_col == food[1]:
                    return True

                # Recursive call for the cat's turn
                if not can_win(next_mouse_row, next_mouse_col, cat_row, cat_col, turn + 1, visited):
                    return True
            return False
        else:
            # Cat's turn
            neighbors = get_neighbors(cat_row, cat_col, cat_jump)
            for next_cat_row, next_cat_col in neighbors:
                # Cat catches mouse
                if next_cat_row == mouse_row and next_cat_col == mouse_col:
                    return False

                # If cat can't catch mouse, keep recursing
                if not can_win(mouse_row, mouse_col, next_cat_row, next_cat_col, turn + 1, visited):
                    return True
            return False

    visited = set()

    # Starts game from the beginning
    return can_win(mouse_start[0], mouse_start[1], cat_start[0], cat_start[1], 0, visited)

Big(O) Analysis

Time Complexity
O(m * n * c * d * maxTurns) – Let m and n represent the dimensions of the board. The possible positions for the mouse and cat are O(m * n) each. Let c and d be the maximum move distances for the cat and mouse respectively. In each turn, the cat can move in O(c) directions and the mouse in O(d) directions. The maximum number of turns to consider is bounded by maxTurns (to avoid infinite loops). Therefore, the overall time complexity is O(m * n * c * d * maxTurns) because we explore all possible game states within the limited turns.
Space Complexity
O(R * C * turns) – The algorithm utilizes a visited set to store game states to avoid infinite loops, where a game state consists of the mouse position, cat position, and turn number. The grid has R rows and C columns, so the mouse and cat positions each have R * C possible locations. The maximum number of turns is bounded, call it 'turns', since we stop exploring after a certain number of turns. Therefore, the visited set can store up to (R * C) * (R * C) * turns game states. This simplifies to O(R^2 * C^2 * turns), which, if we consider R and C as related to input size N, can be further simplified to O(N^2 * turns), but since we were given R and C we will use O(R * C * turns).

Edge Cases

maze is null or empty (0x0)
How to Handle:
Return false immediately as there is no maze.
mouse or cat start position is outside the maze boundaries
How to Handle:
Return false since they start outside the grid.
jump is zero
How to Handle:
If jump is zero, the cat and mouse cannot move, so return whether the mouse and cat start at the same position.
cat and mouse start at the same position
How to Handle:
If the cat and mouse start at the same location and the cat's move range is greater or equal than the mouse's move range, the cat will immediately win; return true.
maze is a single cell
How to Handle:
Check whether the cat and mouse positions are the same, returning true only if they are.
mouse reaches food before cat can reach it
How to Handle:
Use BFS to check if food is reachable by the mouse before the cat.
cat and mouse can move infinitely without reaching the food or each other
How to Handle:
Employ a visited state check (memoization) to avoid infinite loops and determine if a win/lose state has already been reached.
Integer overflow in jump calculation or state representation
How to Handle:
Ensure all jump calculations are within integer limits, and if memoization is used, consider carefully how the state is represented to avoid overflow issues.
0/1916 completed