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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Cat and Mouse

Difficulty: Hard

Problem Description

A game on an undirected graph is played by two players, Mouse and Cat, who alternate turns. The graph is represented as a list where graph[a] contains all nodes b such that ab is an edge of the graph. The Mouse starts at node 1, the Cat starts at node 2, and there is a hole at node 0. The game ends when the Cat occupies the same node as the Mouse (Cat wins), the Mouse reaches the Hole (Mouse wins), or if a position is repeated (the game is a draw). Given the graph, return 1 if the mouse wins, 2 if the cat wins, or 0 if the game is a draw.

Key Insights

  • The game can be modeled as a state-space search problem where the states are determined by the positions of the Mouse and Cat.
  • The players must play optimally, meaning they will always make the best possible move to secure a win.
  • The problem can be solved using dynamic programming or minimax algorithms with memoization to avoid recalculating results for the same states.
  • The Cat cannot move to the Hole (node 0), adding a constraint to its movement options.

Space and Time Complexity

Time Complexity: O(N^3) - where N is the number of nodes in the graph, because we may have to explore all combinations of Mouse and Cat positions with depth equal to the number of nodes.

Space Complexity: O(N^2) - for memoization storage to keep track of win/lose/draw states for each combination of Mouse and Cat positions.

Solution

The solution involves using a recursive function to evaluate the game state for the Mouse and Cat at their respective positions. We use memoization to store the results of previous computations to avoid redundant calculations. The function checks all possible moves for both the Mouse and Cat, determining if one of them can win or force a draw. The game's outcome is determined based on the players' optimal strategies.

Code Solutions

def catMouseGame(graph):
    from functools import lru_cache
    
    @lru_cache(None)
    def dfs(mouse, cat, turn):
        if mouse == 0: return 1  # Mouse wins
        if mouse == cat: return 2  # Cat wins
        if turn == 0:  # Mouse's turn
            for next_mouse in graph[mouse]:
                result = dfs(next_mouse, cat, 1)
                if result == 1: return 1  # If Mouse can win
            return 0  # If no winning move, it's a draw
        else:  # Cat's turn
            for next_cat in graph[cat]:
                if next_cat == 0: continue  # Cat cannot move to hole
                result = dfs(mouse, next_cat, 0)
                if result == 2: return 2  # If Cat can win
            return 0  # If no winning move, it's a draw
            
    return dfs(1, 2, 0)  # Start with Mouse at 1, Cat at 2
← Back to All Questions