913. Cat and Mouse - Leetcode Solution

Code Implementation

class Solution:
    def catMouseGame(self, graph):
        from collections import deque
        N = len(graph)
        DRAW, MOUSE, CAT = 0, 1, 2

        color = [[[DRAW] * N for _ in range(N)] for _ in range(2)]
        degree = [[[0] * N for _ in range(N)] for _ in range(2)]

        for m in range(N):
            for c in range(N):
                degree[0][m][c] = len(graph[m])
                degree[1][m][c] = len([k for k in graph[c] if k != 0])

        queue = deque()
        for i in range(N):
            for t in range(2):
                color[t][0][i] = MOUSE
                queue.append((t, 0, i, MOUSE))
                if i != 0:
                    color[t][i][i] = CAT
                    queue.append((t, i, i, CAT))

        while queue:
            t, m, c, result = queue.popleft()
            for t2, m2, c2 in self.parents(graph, t, m, c):
                if color[t2][m2][c2] == DRAW:
                    if (t2 == 0 and result == MOUSE) or (t2 == 1 and result == CAT):
                        color[t2][m2][c2] = result
                        queue.append((t2, m2, c2, result))
                    else:
                        degree[t2][m2][c2] -= 1
                        if degree[t2][m2][c2] == 0:
                            color[t2][m2][c2] = result
                            queue.append((t2, m2, c2, result))
        return color[0][1][2]

    def parents(self, graph, t, m, c):
        if t == 1:
            for m2 in graph[m]:
                yield 0, m2, c
        else:
            for c2 in graph[c]:
                if c2 != 0:
                    yield 1, m, c2

class Solution {
public:
    int catMouseGame(vector<vector<int>>& graph) {
        int N = graph.size();
        const int DRAW = 0, MOUSE = 1, CAT = 2;
        vector<vector<vector<int>>> color(2, vector<vector<int>>(N, vector<int>(N, DRAW)));
        vector<vector<vector<int>>> degree(2, vector<vector<int>>(N, vector<int>(N, 0)));

        for (int m = 0; m < N; ++m) {
            for (int c = 0; c < N; ++c) {
                degree[0][m][c] = graph[m].size();
                int cnt = 0;
                for (int k : graph[c]) if (k != 0) cnt++;
                degree[1][m][c] = cnt;
            }
        }

        queue<tuple<int,int,int,int>> q;
        for (int i = 0; i < N; ++i) {
            for (int t = 0; t < 2; ++t) {
                color[t][0][i] = MOUSE;
                q.emplace(t, 0, i, MOUSE);
                if (i != 0) {
                    color[t][i][i] = CAT;
                    q.emplace(t, i, i, CAT);
                }
            }
        }

        while (!q.empty()) {
            auto [t, m, c, result] = q.front(); q.pop();
            for (auto [t2, m2, c2] : parents(graph, t, m, c)) {
                if (color[t2][m2][c2] == DRAW) {
                    if ((t2 == 0 && result == MOUSE) || (t2 == 1 && result == CAT)) {
                        color[t2][m2][c2] = result;
                        q.emplace(t2, m2, c2, result);
                    } else {
                        degree[t2][m2][c2]--;
                        if (degree[t2][m2][c2] == 0) {
                            color[t2][m2][c2] = result;
                            q.emplace(t2, m2, c2, result);
                        }
                    }
                }
            }
        }
        return color[0][1][2];
    }

    vector<tuple<int,int,int>> parents(vector<vector<int>>& graph, int t, int m, int c) {
        vector<tuple<int,int,int>> res;
        if (t == 1) {
            for (int m2 : graph[m])
                res.emplace_back(0, m2, c);
        } else {
            for (int c2 : graph[c])
                if (c2 != 0)
                    res.emplace_back(1, m, c2);
        }
        return res;
    }
};

class Solution {
    static final int DRAW = 0, MOUSE = 1, CAT = 2;
    public int catMouseGame(int[][] graph) {
        int N = graph.length;
        int[][][] color = new int[2][N][N];
        int[][][] degree = new int[2][N][N];

        for (int m = 0; m < N; ++m) {
            for (int c = 0; c < N; ++c) {
                degree[0][m][c] = graph[m].length;
                int cnt = 0;
                for (int k : graph[c]) if (k != 0) cnt++;
                degree[1][m][c] = cnt;
            }
        }

        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < N; ++i) {
            for (int t = 0; t < 2; ++t) {
                color[t][0][i] = MOUSE;
                queue.offer(new int[]{t, 0, i, MOUSE});
                if (i != 0) {
                    color[t][i][i] = CAT;
                    queue.offer(new int[]{t, i, i, CAT});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int t = arr[0], m = arr[1], c = arr[2], result = arr[3];
            for (int[] parent : parents(graph, t, m, c)) {
                int t2 = parent[0], m2 = parent[1], c2 = parent[2];
                if (color[t2][m2][c2] == DRAW) {
                    if ((t2 == 0 && result == MOUSE) || (t2 == 1 && result == CAT)) {
                        color[t2][m2][c2] = result;
                        queue.offer(new int[]{t2, m2, c2, result});
                    } else {
                        degree[t2][m2][c2]--;
                        if (degree[t2][m2][c2] == 0) {
                            color[t2][m2][c2] = result;
                            queue.offer(new int[]{t2, m2, c2, result});
                        }
                    }
                }
            }
        }
        return color[0][1][2];
    }

    private List<int[]> parents(int[][] graph, int t, int m, int c) {
        List<int[]> res = new ArrayList<>();
        if (t == 1) {
            for (int m2 : graph[m])
                res.add(new int[]{0, m2, c});
        } else {
            for (int c2 : graph[c])
                if (c2 != 0)
                    res.add(new int[]{1, m, c2});
        }
        return res;
    }
}

var catMouseGame = function(graph) {
    const N = graph.length;
    const DRAW = 0, MOUSE = 1, CAT = 2;
    const color = Array.from({length:2}, () => Array.from({length:N}, () => Array(N).fill(DRAW)));
    const degree = Array.from({length:2}, () => Array.from({length:N}, () => Array(N).fill(0)));

    for (let m = 0; m < N; ++m) {
        for (let c = 0; c < N; ++c) {
            degree[0][m][c] = graph[m].length;
            degree[1][m][c] = graph[c].filter(k => k !== 0).length;
        }
    }

    const queue = [];
    for (let i = 0; i < N; ++i) {
        for (let t = 0; t < 2; ++t) {
            color[t][0][i] = MOUSE;
            queue.push([t, 0, i, MOUSE]);
            if (i !== 0) {
                color[t][i][i] = CAT;
                queue.push([t, i, i, CAT]);
            }
        }
    }

    while (queue.length) {
        const [t, m, c, result] = queue.shift();
        for (const [t2, m2, c2] of parents(graph, t, m, c)) {
            if (color[t2][m2][c2] === DRAW) {
                if ((t2 === 0 && result === MOUSE) || (t2 === 1 && result === CAT)) {
                    color[t2][m2][c2] = result;
                    queue.push([t2, m2, c2, result]);
                } else {
                    degree[t2][m2][c2]--;
                    if (degree[t2][m2][c2] === 0) {
                        color[t2][m2][c2] = result;
                        queue.push([t2, m2, c2, result]);
                    }
                }
            }
        }
    }
    return color[0][1][2];

    function parents(graph, t, m, c) {
        const res = [];
        if (t === 1) {
            for (const m2 of graph[m]) {
                res.push([0, m2, c]);
            }
        } else {
            for (const c2 of graph[c]) {
                if (c2 !== 0) res.push([1, m, c2]);
            }
        }
        return res;
    }
};

Problem Description

The Cat and Mouse game is played on a directed graph represented by an adjacency list graph. There are two players: the Mouse (starting at node 1) and the Cat (starting at node 2). The Mouse moves first, and then the Cat moves, and they alternate turns. Both can move to any node connected by an edge from their current position. The Cat cannot move to node 0, which is the "hole".

The game ends if:

The Mouse reaches node 0 (the Mouse wins).
The Cat catches the Mouse (they occupy the same node, the Cat wins).
The game repeats a position (draw).

The goal is to determine who will win the game if both players play optimally, starting from the initial positions. The function should return:

1 if the Mouse wins,
2 if the Cat wins,
0 if the game is a draw.

Thought Process

At first glance, it seems like the problem can be solved by simulating every possible move for both players. However, since the game can loop indefinitely, a naive brute-force search would either miss cycles (draws) or run into infinite recursion. The challenge is to handle cycles and avoid redundant computation.

To improve upon brute-force, we need to recognize that the outcome of the game from any position depends only on the current state: whose turn it is, the Mouse's position, and the Cat's position. If we can compute and store the result for every possible state, we can avoid recomputation and detect cycles to mark draws.

This leads us to a dynamic programming or retrograde analysis (working backwards from known winning positions) approach, where we propagate outcomes from terminal positions (where the winner is known) backward to earlier states.

Solution Approach

State Representation:
- Each game state is defined by three parameters: the turn (0 for Mouse, 1 for Cat), the Mouse's position, and the Cat's position.
Base Cases:
- If the Mouse is at node 0, the Mouse wins.
- If the Mouse and Cat are at the same node (except node 0), the Cat wins.
Retrograde Analysis:
- We initialize all base cases and use a queue to propagate the outcome to all possible parent states.
- For each state, we determine if the current player can force a win, or if all their moves lead to a loss, or if the state is a draw.
Degree Counting:
- For each state, we keep track of the number of unexplored moves (degree). If all moves lead to a loss for the current player, then the state is a forced loss for them.
Parent Tracking:
- For each state, we can determine its "parent" states (previous moves that could have led here) and propagate results backwards to them.
Result:
- Once all states are processed, the answer is the value for (Mouse's turn, Mouse at 1, Cat at 2).

Example Walkthrough

Let's consider a small graph: graph = [[2,3],[3,4],[0,4],[0,1],[1,2]]. The nodes are 0-4. Mouse starts at 1, Cat at 2.

Base case: If Mouse is at 0, Mouse wins. If Mouse and Cat are at the same node, Cat wins.
Start from (turn=Mouse, Mouse=1, Cat=2). Mouse can move to 3 or 4. Suppose Mouse moves to 3.
Now Cat's turn: Cat at 2, Mouse at 3. Cat can move to 0 or 4 (but not 0). So Cat can only move to 4.
Continue exploring each possibility, marking each state as win/loss/draw as the outcomes propagate backward.
If all possible moves for the current player lead to a loss, that state is a forced loss. If at least one move leads to a win, it's a win for the current player.
Eventually, the result for (Mouse's turn, 1, 2) is determined.

Time and Space Complexity

Brute-force:
- There are up to O(N^3) unique states (N nodes, for Mouse, Cat, and turn), and each state can be revisited many times without memoization, leading to exponential time.
Optimized Approach:
- We process each of O(N^3) states at most once, and for each state, we look at O(N) parent states. So the total time is O(N^4).
- Space complexity is O(N^3) to store the state results and degrees.

Summary

The Cat and Mouse game is a classic example of game theory on graphs. By representing each state with the player turn and positions of Mouse and Cat, and propagating win/loss/draw outcomes from terminal states using retrograde analysis, we efficiently solve the problem. The key insight is to avoid redundant computation by memoizing results and to handle cycles (draws) explicitly. This approach is both elegant and effective for complex game scenarios.

AlgoMap.io

Want Help Cracking FAANG?