Leetcode 913. Cat and Mouse

Problem Explanation

In this problem, we are given an undirected graph. We have two players, Mouse and Cat, who start at node 1 and 2 respectively. The game ends if Mouse reaches the Hole (node 0) before Cat can catch it, or if Cat is able to catch the Mouse before it reaches the Hole, or if players repeat their positions and it's the same player's move, we declare the game as a draw. The goal of our problem is to find out the outcome of this game, assuming both players are playing optimally.

For instance, assuming we have the following undirected graph [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]], the game would end in a draw.

We can visualize the graph as follows:

1
2
34---3---1
4|   |
52---5
6 \ /
7  0

Approach

This problem can be solved using the principles of dynamic programming in combination with graph traversal concepts. The general idea for our solution is to simulate the game using a breadth-first search (BFS) approach, starting from all possible end states for the game. The end states are when the Mouse is on Hole (node 0), the Mouse is caught by Cat or Mouse and Cat are at the same state.

We will keep a states vector to hold the different states of cat, mouse and move (cat's move or mouse's move). We also keep an outDegree array which will hold the number of states we can move to from a given state.

For each turn, we examine all possible moves and transitions from our current state to the previous state. If a previous state outcome has already been determined, we ignore it. Otherwise, if the game reaches a determined state in one step or the player has no other moves, we update the current state and add it to the queue.

We do this until we reach the initial state where mouse is at node 1 and cat is at node 2 and it's mouse's turn. The final state of that node will be the answer to our problem, whether the game is won by the Mouse, the Cat or ends in a draw.

Solution in C++

The provided solution is in C++. I will try to explain this algorithm through python language.

I will provide solutions in python, java, and javascript.

Python Solution

1
2python
3class State:
4    DRAW = 0
5    MOUSE_WIN = 1
6    CAT_WIN = 2
7
8class Solution:
9    def catMouseGame(self, graph):
10        n = len(graph)
11        states = [[[State.DRAW for _ in range(2)] for _ in range(n)] for _ in range(n)]
12        outDegree = [[[0 for _ in range(2)] for _ in range(n)] for _ in range(n)]
13        q = []
14        
15        for cat in range(n):
16            for mouse in range(n):
17                outDegree[cat][mouse][0] = len(graph[mouse]) 
18                outDegree[cat][mouse][1] = len(graph[cat]) - (0 in graph[cat])
19        
20        for cat in range(1, n):
21            for move in range(2):
22                states[cat][0][move] = State.MOUSE_WIN
23                states[cat][cat][move] = State.CAT_WIN
24                q.extend([(cat, 0, move, State.MOUSE_WIN), (cat, cat, move, State.CAT_WIN)])
25        
26        while q:
27            cat, mouse, move, state = q.pop()
28            if cat == 2 and mouse == 1 and move == 0:
29                return state.value
30            prevMove = move ^ 1
31            for prev in graph[prevMove == 1 and cat or mouse]:
32                prevCat = prev if prevMove else cat
33                if prevCat == 0: continue
34                prevMouse = prev if not prevMove else mouse
35                if states[prevCat][prevMouse][prevMove] != State.DRAW: continue
36                if prevMove == 0 and state == State.MOUSE_WIN or prevMove == 1 and state == State.CAT_WIN or not outDegree[prevCat][prevMouse][prevMove]:
37                    states[prevCat][prevMouse][prevMove] = state
38                    q.append((prevCat, prevMouse, prevMove, state))
39                outDegree[prevCat][prevMouse][prevMove] -= 1
40            
41        return states[2][1][0].value

Java Solution

1
2java
3import java.util.*;
4
5enum State {
6    DRAW, MOUSE_WIN, CAT_WIN
7}
8
9class Solution {
10    public int catMouseGame(int[][] graph) {
11        int n = graph.length;
12        State[][][] states = new State[n][n][2];
13        int[][][] outDegree = new int[n][n][2];
14        Queue<int[]> q = new LinkedList<>();
15        
16        for (int cat = 0; cat < n; ++cat)
17            for (int mouse = 0; mouse < n; ++mouse) {
18                outDegree[cat][mouse][0] = graph[mouse].length;
19                outDegree[cat][mouse][1] = graph[cat].length - (Arrays.asList(graph[cat]).contains(0) ? 1 : 0);
20            }
21
22        for (int cat = 1; cat < n; ++cat)
23            for (int m = 0; m < 2; ++m) {
24                states[cat][0][m] = State.MOUSE_WIN;
25                states[cat][cat][m] = State.CAT_WIN;
26                q.add(new int[] {cat, 0, m, State.MOUSE_WIN.ordinal()});
27                q.add(new int[] {cat, cat, m, State.CAT_WIN.ordinal()});
28            }
29
30        while (!q.isEmpty()) {
31            int[] a = q.poll();
32            int cat = a[0], mouse = a[1], move = a[2], state = a[3];
33            if (cat == 2 && mouse == 1 && move == 0)
34                return state;
35            for (int prev : graph[move == 1 ? cat : mouse]) {
36                int prevCat = move == 1 ? prev : cat;
37                if (prevCat == 0) continue;
38                int prevMouse = move == 1 ? mouse : prev;
39                if (states[prevCat][prevMouse][1 - move] != null)
40                    continue;
41                if (move == 0 && (State.values())[state] == State.MOUSE_WIN || move == 1 && (State.values())[state] == State.CAT_WIN || --outDegree[prevCat][prevMouse][1 - move] == 0) {
42                    states[prevCat][prevMouse][1 - move] = State.values()[state];
43                    q.add(new int[] {prevCat, prevMouse, 1 - move, state});
44                }
45            }
46        }
47
48        return states[2][1][0].ordinal();
49    }
50}

JavaScript Solution

1
2javascript
3let DRAW = 0, MOUSE_WIN = 1, CAT_WIN = 2;
4
5let Solution = function() {
6    this.catMouseGame = function(graph) {
7        let n = graph.length;
8        let states = [...Array(n)].map(x => Array(n).fill(0).map(y => Array(2).fill(DRAW)));
9        let outDegree = [...Array(n)].map(x => Array(n));
10        
11        for (let cat = 0; cat < n; ++cat) {
12            for (let mouse = 0; mouse < n; ++mouse) {
13              outDegree[cat][mouse] = [graph[mouse].length, graph[cat].length - graph[cat].includes(0)];
14            }
15        }
16        
17        let q = [];
18        for (let cat = 1; cat < n; ++cat) {
19            for (let move = 0; move < 2; ++move) {
20                states[cat][0][move] = MOUSE_WIN;
21                states[cat][cat][move] = CAT_WIN;
22                q.push([cat, 0, move, MOUSE_WIN]);
23                q.push([cat, cat, move, CAT_WIN]);
24            }
25        }
26        
27        while (q.length > 0) {
28            let [cat, mouse, move, state] = q.shift();
29            if (cat == 2 && mouse == 1 && move == 0) {
30                return state;
31            }
32            let prevMove = move ^ 1;
33            for (let prev of graph[prevMove == 1 ? cat : mouse]) {
34                let prevCat = prevMove ? prev : cat;
35                if (prevCat == 0) continue;
36                let prevMouse = prevMove ? mouse : prev;
37                if (states[prevCat][prevMouse][prevMove] != DRAW) continue;
38                if ((prevMove == 0 && state == MOUSE_WIN) || (prevMove == 1 && state == CAT_WIN) ||
39                    --outDegree[prevCat][prevMouse][prevMove] == 0) {
40                    states[prevCat][prevMouse][prevMove] = state;
41                    q.push([prevCat, prevMouse, prevMove, state]);
42                }
43            }
44        }
45
46        return states[2][1][0];
47    }
48};

This problem solution involves deep understanding of game theory, BFS, DFS and dynamic programming, making it a hard-level problem.However, regardless of its difficulty, it is very well-suited to graph-based thinking and can give you a whole new perspective on dynamic programming problems. While implementing this solution in different languages, it is crucial to focus on BFS traversal, state preservation and how game dynamics can change the state. Also, remember that we are dealing here with a deterministic game, meaning the result of the game only depends on the action sequence of Mouse and Cat which in return depends on the current game state.

Before ending, Let's briefly summarize the problem and its solution:

Problem: Determining the winner in a game where Mouse and Cat take turns based on a deterministic strategy, starting from distinct positions in a graph. The game ends under three conditions. If (1) the Mouse reaches its Hole, (2) the Cat catches the Mouse, or (3) the configuration repeats and it's the same player's turn.

Solution: Starting from all possible end states of the game, use BFS to traverse through the graph and for each turn, examine all possible moves for the player. Update the states and outcomes using dynamic programming concepts.

Once you understand the underlying concepts, you can successfully implement the solution in any programming language.

Understanding a problem at this depth opens up your mind to different approaches and makes you better at problem-solving, two traits that any competent programmer must possess. So, if you are looking to improve your programming skills, finding and solving problems like this one is a great way to do it.