DP: Leetcode 913. Cat and Mouse

Cat and Mouse - LeetCode

Original solutions are from

LeetCode 913. Cat and Mouse - AcWing

https://leetcode.com/problems/cat-and-mouse/discuss/298937/DP-memory-status-search-search-strait-forward-and-easy-to-understand

The java is fast. It only takes 24 ms.
Naively translate to python(976 ms)

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        def search(t, x, y):
            if t == len(graph) * 2: return 0
            if x == y:
                dp[t][x][y] = 2
                return 2
            if x == 0:
                dp[t][x][y] = 1
                return 1
            if dp[t][x][y] != -1:return dp[t][x][y]
            if (t%2==0):# mouse's turn
                flag = True
                for i in range(len(graph[x])):
                    nxt = search(t+1, graph[x][i], y)
                    if nxt == 1:
                        dp[t][x][y] = 1
                        return 1
                    elif nxt!=2:
                        flag = False
                if flag:
                    dp[t][x][y] = 2
                    return 2
                dp[t][x][y] = 0
                return 0
            else:# cat's turn
                flag = True
                for i in range(len(graph[y])):
                    if graph[y][i]!=0:
                        nxt = search(t + 1, x, graph[y][i])
                        if nxt ==2:
                            dp[t][x][y] = 2
                            return 2
                        elif nxt != 1:flag=False
                if flag:
                    dp[t][x][y] = 1
                    return 1
                else:
                    dp[t][x][y] = 0
                    return 0
        n = len(graph)
        dp = [ [ [-1 for k in range(n)] for j in range(n)] for i in range(2*n)]
        return search(0, 1, 2)

Make it a little bit concise (1000 ms)

from functools import lru_cache
class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        @lru_cache(None)
        def search(t, x, y):
            if t == len(graph) * 2: return 0
            if x == y: return 2
            if x == 0:return 1
            if (t%2==0):# mouse's turn
                if any(search(t+1, graph[x][i], y)==1 for i in range(len(graph[x]))):
                    return 1
                if all(search(t+1, graph[x][i], y)==2 for i in range(len(graph[x]))):
                    return 2
                return 0
            else:# cat's turn
                if any(search(t+1, x, graph[y][i])==2 for i in range(len(graph[y])) if graph[y][i]!=0):
                    return 2
                if all(search(t + 1, x, graph[y][i])==1 for i in range(len(graph[y])) if graph[y][i]!=0): 
                    return 1
                return 0
        return search(0, 1, 2)

change 2n to 0.8n can also pass all the test cases (run time is 472ms ).

from functools import lru_cache
class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        @lru_cache(None)
        def search(t, x, y):
            if t == int(len(graph) * 0.8): return 0
            if x == y: return 2
            if x == 0:return 1
            if (t%2==0):# mouse's turn
                if any(search(t+1, graph[x][i], y)==1 for i in range(len(graph[x]))):
                    return 1
                if all(search(t+1, graph[x][i], y)==2 for i in range(len(graph[x]))):
                    return 2
                return 0
            else:# cat's turn
                if any(search(t+1, x, graph[y][i])==2 for i in range(len(graph[y])) if graph[y][i]!=0):
                    return 2
                if all(search(t + 1, x, graph[y][i])==1 for i in range(len(graph[y])) if graph[y][i]!=0): 
                    return 1
                return 0
        return search(0, 1, 2)

Make the code more concise. (388 ms)

from functools import lru_cache
class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        @lru_cache(None)
        def search(t, x, y):
            if t == int(len(graph) * 0.8): return 0
            if x == y: return 2
            if x == 0:return 1
            if (t%2==0):# mouse's turn. Mouse will win if the mouse can find any winable node for the next step. If all the next step is winable for cats, then mouse lose.
                if any(search(t+1, x_nxt, y)==1 for x_nxt in graph[x]):return 1
                if all(search(t+1, x_nxt, y)==2 for x_nxt in graph[x]):return 2
                return 0
            else:# cat's turn
                if any(search(t+1, x, y_nxt)==2 for y_nxt in graph[y] if y_nxt!=0):return 2
                if all(search(t+1, x, y_nxt)==1 for y_nxt in graph[y] if y_nxt!=0):return 1
                return 0
        return search(0, 1, 2)

Thanks for reading.