We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Cat and Mouse

Number: 949

Difficulty: Hard

Paid? No

Companies: Amazon, Google

Problem Description

Two players – a Mouse and a Cat – play a game on an undirected graph. The Mouse starts at node 1 and the Cat at node 2. The graph is given in an array format where graph[a] lists all nodes b for which there is an edge a-b. The Mouse and Cat alternate moves and must move to an adjacent node with the Cat not allowed to enter the hole at node 0. The game ends when: the Cat catches the Mouse (both occupy the same node), the Mouse reaches the hole (node 0), or the game repeats a position with the same player to move (resulting in a draw). When both players play optimally, return 1 if the Mouse wins, 2 if the Cat wins, or 0 if the game is a draw.

Key Insights

  • Model the game as a state-space with dp[mouse][cat][turn], where turn indicates whether it is the Mouse’s or the Cat’s move.
  • Use retrograde analysis (backward induction) starting from terminal “winning” states:
    • The Mouse wins if it reaches node 0.
    • The Cat wins if it catches the Mouse (except when the Mouse is at the hole).
  • Use topological sort/BFS in reverse over the state-space to “propagate” wins to parent states.
  • Maintain for each state the number of moves (degree) available and update the state outcome only when all moves have been exhausted, ensuring that cycles are marked as draws.
  • Handle the Cat’s restriction (cannot move to node 0) when computing legal moves.

Space and Time Complexity

Time Complexity: O(N^3) in the worst-case scenario, where N is the number of nodes (due to the state space being roughly O(N^2) and processing each move potentially examining O(N) neighbors). Space Complexity: O(N^2) for storing the state results over all possible (mouse, cat, turn) configurations.

Solution

We solve the problem using a dynamic programming approach combined with retrograde analysis (backward induction) on the state-space defined by the positions of the Mouse and Cat along with whose turn it is. The idea is to initialize the states with known outcomes (terminal states) and then “propagate” these outcomes backwards to all states that can reach them.

  1. Define the state dp[mouse][cat][turn] where turn = 0 means Mouse’s turn and turn = 1 means Cat’s turn.
  2. Initialize terminal states:
    • If the Mouse is at node 0, the Mouse wins.
    • If the Cat and Mouse are at the same node (and the Mouse is not at node 0), the Cat wins.
  3. For all other states, count the valid moves (degree) based on the problem’s rules (keeping in mind that the Cat cannot move to node 0).
  4. Use a queue to perform a reverse BFS. For a given state with a determined outcome, check all “parent” states (i.e. states that can move to the current state) and use the following rules:
    • If the current outcome is a winning move for the player who would have moved in the parent state, then the parent state is also winning.
    • Otherwise, decrease the degree for that parent state. When a state’s degree is exhausted (meaning all moves lead to losing positions), mark that state as a win for the opponent.
  5. Return the outcome for the starting state (Mouse at node 1, Cat at node 2, Mouse's turn). This technique ensures that all states are resolved under optimal play.

Code Solutions

from collections import deque

def catMouseGame(graph):
    n = len(graph)
    # Define outcomes for clarity
    MOUSE_WIN, CAT_WIN, DRAW = 1, 2, 0
    # dp[mouse][cat][turn]: outcome from state (mouse, cat, turn) where turn: 0=>mouse, 1=>cat
    dp = [[[DRAW for _ in range(2)] for _ in range(n)] for _ in range(n)]
    # degree stores the number of valid moves from this state
    degree = [[[0 for _ in range(2)] for _ in range(n)] for _ in range(n)]
    
    # Pre-calculate the number of moves (degree) from each state for both players.
    for mouse in range(n):
        for cat in range(n):
            # Mouse can move to any neighbor.
            degree[mouse][cat][0] = len(graph[mouse])
            # Cat can move to any neighbor except node 0.
            degree[mouse][cat][1] = sum(1 for neighbor in graph[cat] if neighbor != 0)
    
    queue = deque()
    
    # Initialize terminal states.
    # 1. Mouse wins if it is at the hole (node 0)
    for cat in range(n):
        for turn in range(2):
            if dp[0][cat][turn] != MOUSE_WIN:
                dp[0][cat][turn] = MOUSE_WIN
                queue.append((0, cat, turn, MOUSE_WIN))
    
    # 2. Cat wins if it catches the Mouse (mouse == cat) and mouse != 0.
    for mouse in range(1, n):
        for turn in range(2):
            if dp[mouse][mouse][turn] != CAT_WIN:
                dp[mouse][mouse][turn] = CAT_WIN
                queue.append((mouse, mouse, turn, CAT_WIN))
    
    # Helper function to get parent states.
    def get_parents(mouse, cat, turn):
        parents = []
        prev_turn = 1 - turn
        if turn == 0:
            # Current turn is mouse, so previous move was by the cat.
            # The cat could have come from any neighbor (except node 0).
            for prev_cat in graph[cat]:
                if prev_cat == 0:
                    continue
                parents.append((mouse, prev_cat))
        else:
            # Current turn is cat, so previous move was by the mouse.
            for prev_mouse in graph[mouse]:
                parents.append((prev_mouse, cat))
        return parents
    
    # Process states in reverse (backward induction).
    while queue:
        mouse, cat, turn, outcome = queue.popleft()
        prev_turn = 1 - turn  # Parent state turn.
        for prev_mouse, prev_cat in get_parents(mouse, cat, turn):
            # If the parent's outcome is still unresolved:
            if dp[prev_mouse][prev_cat][prev_turn] == DRAW:
                # If it is the parent's turn and it can force a win by moving to this state:
                if (prev_turn == 0 and outcome == MOUSE_WIN) or (prev_turn == 1 and outcome == CAT_WIN):
                    dp[prev_mouse][prev_cat][prev_turn] = outcome
                    queue.append((prev_mouse, prev_cat, prev_turn, outcome))
                else:
                    # Decrement the degree of possible moves for the parent.
                    degree[prev_mouse][prev_cat][prev_turn] -= 1
                    # If no moves remain, then the parent must lose.
                    if degree[prev_mouse][prev_cat][prev_turn] == 0:
                        win = CAT_WIN if prev_turn == 0 else MOUSE_WIN
                        dp[prev_mouse][prev_cat][prev_turn] = win
                        queue.append((prev_mouse, prev_cat, prev_turn, win))
                        
    # Return outcome of the starting state: Mouse at 1, Cat at 2, and Mouse's turn.
    return dp[1][2][0]

# Example usage:
if __name__ == "__main__":
    graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
    print(catMouseGame(graph))  # Expected output: 0
← Back to All Questions