Cat and Mouse

Hard

Asked by:

39 views

Topics:

GraphsDynamic Programming

A game on an undirected graph is played by two players, Mouse and Cat, who alternate turns.

The graph is given as follows: graph[a] is a list of all nodes b such that ab is an edge of the graph.

The mouse starts at node 1 and goes first, the cat starts at node 2 and goes second, and there is a hole at node 0.

During each player's turn, they must travel along one edge of the graph that meets where they are. For example, if the Mouse is at node 1, it must travel to any node in graph[1].

Additionally, it is not allowed for the Cat to travel to the Hole (node 0).

Then, the game can end in three ways:

If ever the Cat occupies the same node as the Mouse, the Cat wins.
If ever the Mouse reaches the Hole, the Mouse wins.
If ever a position is repeated (i.e., the players are in the same position as a previous turn, and it is the same player's turn to move), the game is a draw.

Given a graph, and assuming both players play optimally, return

1 if the mouse wins the game,
2 if the cat wins the game, or
0 if the game is a draw.

Example 1:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0

Example 2:

Input: graph = [[1,3],[0],[3],[0,2]]
Output: 1

Constraints:

3 <= graph.length <= 50
1 <= graph[i].length < graph.length
0 <= graph[i][j] < graph.length
graph[i][j] != i
graph[i] is unique.
The mouse and the cat can always move.

Try coding it in LeetCode

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:

What are the constraints on the coordinates for the cat and mouse? Are they positive integers, and is there a maximum value?
If the cat can't catch the mouse, what should the function return? Should it return -1, or some other indicator?
Can the cat and mouse occupy the same starting position?
Is the graph represented as an adjacency list, adjacency matrix, or some other data structure? And if the graph is empty, should I return -1?
Is the movement simultaneous, or does the cat move first, and then the mouse?

Brute Force Solution

Approach

The brute force approach to the cat and mouse problem involves exploring every possible sequence of moves for both the cat and the mouse. We simulate all possible games to determine the outcome. By exhaustively searching all possible game states, we guarantee finding the solution if one exists.

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

Consider all possible moves the cat could make from its starting location.
For each of these cat moves, consider all possible moves the mouse could then make.
Continue this process, alternating between cat and mouse moves, exploring all possible sequences of moves up to a reasonable limit.
For each sequence of moves, check if the cat catches the mouse or if the mouse escapes within the move limit.
If the cat catches the mouse in a sequence, the cat wins. If the mouse escapes within the move limit, the mouse wins. If all possible moves lead to a draw, the game results in a draw.
Repeat this process for every possible initial set of moves by the cat to find the winner or the draw outcome.

Code Implementation

def cat_and_mouse_brute_force(graph, cat_start, mouse_start, max_moves):
    number_of_nodes = len(graph)

    def get_result(cat_position, mouse_position, moves_remaining):
        # Cat wins if it catches the mouse
        if cat_position == mouse_position:
            return 1

        # Mouse wins if it reaches 0 before cat catches
        if moves_remaining == 0:
            return 2

        # Mouse wins if it reaches hole (node 0) before cat catches
        if mouse_position == 0:
            return 2

        # Iterate through all the possible mouse moves.
        mouse_wins = False
        for next_mouse_position in graph[mouse_position]:
            # Assume the cat will now try to minimize the chance mouse wins.
            cat_loses = True
            for next_cat_position in graph[cat_position]:
                if next_cat_position == 0:
                    continue

                result = get_result(next_cat_position, next_mouse_position, moves_remaining - 1)

                # If there's a path where cat can win, cat doesn't lose
                if result != 2:
                    cat_loses = False

            # If cat loses, then the mouse wins
            if cat_loses:
                mouse_wins = True
                break

        # Mouse can't win, therefore cat must win
        if not mouse_wins:
            return 1
        else:
            return 2

    return get_result(cat_start, mouse_start, 2 * max_moves)

Big(O) Analysis

Time Complexity

O((n^2)^m) – The brute force approach explores every possible sequence of moves up to 'm' moves, where 'm' is the move limit. In each move, both the cat and the mouse can potentially move to any of the 'n' possible locations (assuming there are 'n' locations or nodes in the graph). Thus, for each move, there are roughly n*n possibilities to explore (cat's possible moves multiplied by the mouse's possible moves). Since this process is repeated up to 'm' times, the total number of possible move sequences grows exponentially to (n*n)^m. This means the time complexity is O((n^2)^m).

Space Complexity

O(K^M) – The brute force approach explores all possible sequences of moves up to a certain limit. Let K be the maximum number of possible moves a cat or mouse can make from a given position, and let M be the maximum number of moves considered (move limit). The algorithm implicitly uses a call stack to explore these moves recursively, where each level in the call stack corresponds to a cat or mouse move. In the worst case, the depth of this call stack can reach M, and each call explores K possible branches. Therefore, the space used by the call stack grows exponentially with the number of moves considered, resulting in a space complexity of O(K^M).

Optimal Solution

Approach

This problem involves figuring out who wins a game of cat and mouse on a graph. The clever approach recognizes that certain positions are traps, leading to predictable outcomes, and avoids unnecessary searching.

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

Understand that if either the cat or the mouse reaches the location '0', the cat wins.
Consider positions where the mouse can't move because the cat has blocked all adjacent spots; the cat wins in those scenarios too.
Start identifying winning and losing positions for both the cat and the mouse, beginning with the end-game scenarios (reaching location '0' or the mouse being trapped).
Work backward from these end-game positions. If the mouse can move to a position where the cat always loses, that's a winning position for the mouse. Conversely, if the cat can move to a position where the mouse always loses, it's a winning position for the cat.
Keep repeating this process, marking positions as winning or losing for either the cat or the mouse based on whether they can force the other player into a losing position.
If you reach a point where you can't determine whether a position is winning or losing for either player within a certain number of turns, it's a draw.
The outcome starting from the initial positions of the cat and mouse on the graph determines the winner.

Code Implementation

def cat_and_mouse(graph):    number_of_nodes = len(graph)
    MOUSE_WIN = 1
    CAT_WIN = 2
    DRAW = 0
    cache = {}    def get_result(mouse_position, cat_position, turns):      if turns > 2 * number_of_nodes:        return DRAW
      if (mouse_position, cat_position, turns) in cache:        return cache[(mouse_position, cat_position, turns)]
      # Mouse wins if it reaches hole.      if mouse_position == 0:        return MOUSE_WIN
      # Cat wins if it reaches the mouse or hole first.      if cat_position == 0 or cat_position == mouse_position:        return CAT_WIN
      if turns % 2 == 0:  # Mouse's turn        # Mouse tries to move to a losing position for the cat.        mouse_can_win = False
        for next_mouse_position in graph[mouse_position]:          result = get_result(next_mouse_position, cat_position, turns + 1)
          if result == MOUSE_WIN:            mouse_can_win = True            break        if mouse_can_win:          cache[(mouse_position, cat_position, turns)] = MOUSE_WIN          return MOUSE_WIN        else:          # If no move leads to mouse win, it's a loss or draw.          cache[(mouse_position, cat_position, turns)] = CAT_WIN          return CAT_WIN      else:  # Cat's turn        # Cat tries to move to a losing position for the mouse.        cat_can_win = False
        for next_cat_position in graph[cat_position]:          if next_cat_position != 0: #Cat cannot move to 0 on its turn.            result = get_result(mouse_position, next_cat_position, turns + 1)
            if result == CAT_WIN:              cat_can_win = True              break        if cat_can_win:          cache[(mouse_position, cat_position, turns)] = CAT_WIN          return CAT_WIN        else:          #If no move leads to cat win, it's a loss or draw.          cache[(mouse_position, cat_position, turns)] = DRAW          return DRAW    # Start the game from position 1,2, and 0 turns.    return get_result(1, 2, 0)

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm explores all possible game states, where a state is defined by the positions of the mouse, the cat, and the current turn (mouse or cat). In the worst case, the number of possible states is proportional to n*n*2, where n is the number of nodes in the graph. The breadth-first search visits each state at most once to determine if it's a winning or losing state. For each state, we need to iterate through the neighbors of the mouse and cat to find potential next states which can take O(m) time in the worst case, where m is the number of edges in the graph. Therefore, the overall time complexity becomes O(n*n*m) which can be simplified to O(n*m), considering the initial positions of the mouse and cat are fixed.

Space Complexity

O(N^2 * C) – The space complexity is primarily determined by the size of the memoization table used to store the results of subproblems (winning or losing positions for cat and mouse). This table has dimensions related to possible positions for the mouse, the cat, and the number of turns (or a win/lose/draw indicator). If we consider that the mouse and cat can each be in up to N locations (nodes in the graph), and we need to store information about each combination of mouse position, cat position, and turn count (or win/lose/draw), the memoization table can grow to a size proportional to N * N * C, where C is a constant maximum number of moves. Thus, the auxiliary space used is O(N^2 * C). The queue used for the breadth-first search in marking winning/losing positions also has a space complexity of O(N^2 * C) in the worst case where all combinations of mouse and cat positions are enqueued.

Edge Cases

Case	How to Handle
Null or empty input arrays for cat and mouse positions	Return an appropriate error value, such as -1, or throw an exception if the input is invalid.
Cat and mouse start at the same position	If the cat and mouse positions are identical, the game is immediately over and return 0.
Cat's speed is zero	If the cat's speed is zero, the mouse automatically wins unless they start at the same point.
Mouse's speed is zero	If the mouse's speed is zero, the cat automatically wins unless they start at the same point.
Integer overflow when calculating distances	Use appropriate data types or modular arithmetic to prevent integer overflow when computing large distances or time steps.
Large speed values potentially resulting in very small time steps	Use double or long data type for speed and time step calculations to avoid precision issues.
The finish point is the same as the start position of the cat	If the finish point is the start position of the cat, the cat immediately wins, and return 1.
Negative speeds or distances provided as input	Return an appropriate error value, such as -1, or throw an IllegalArgumentException if the inputs are invalid.

Null or empty input arrays for cat and mouse positions

How to Handle:

Return an appropriate error value, such as -1, or throw an exception if the input is invalid.

Cat and mouse start at the same position

How to Handle:

If the cat and mouse positions are identical, the game is immediately over and return 0.

Cat's speed is zero

How to Handle:

If the cat's speed is zero, the mouse automatically wins unless they start at the same point.

Mouse's speed is zero

How to Handle:

If the mouse's speed is zero, the cat automatically wins unless they start at the same point.

Integer overflow when calculating distances

How to Handle:

Use appropriate data types or modular arithmetic to prevent integer overflow when computing large distances or time steps.

Large speed values potentially resulting in very small time steps

How to Handle:

Use double or long data type for speed and time step calculations to avoid precision issues.

The finish point is the same as the start position of the cat

How to Handle:

If the finish point is the start position of the cat, the cat immediately wins, and return 1.

Negative speeds or distances provided as input

How to Handle:

Return an appropriate error value, such as -1, or throw an IllegalArgumentException if the inputs are invalid.