Python


  • 3

    At the start, the knight is at (r, c) with probability 1 (and anywhere else with probability 0). Then update those probabilities over K moves.

    def knightProbability(self, N, K, r, c):
        p = {(r, c): 1}
        for _ in range(K):
            p = {(r, c): sum(p.get((r+i, c+j), 0) + p.get((r+j, c+i), 0) for i in (1, -1) for j in (2, -2)) / 8
                 for r in range(N) for c in range(N)}
        return sum(p.values())
    

    Shorter and maybe nicer version, influenced a bit by @flamesofmoon's solution:

    def knightProbability(self, N, K, r, c):
        p = {(r, c): 1}
        for _ in range(K):
            p = {(r, c): sum(p.get((r+i, c+j), 0) for x in (1, 2) for i in (x, -x) for j in (3-x, x-3)) / 8
                 for r in range(N) for c in range(N)}
        return sum(p.values())

  • 0
    G

    @StefanPochmann can you explain your solution in detail? I can understand only a part of it ... and especially the last part 'for r in range(N) for c in range(N)' confuses me...


  • 1

    @GoldenalCheese

    {do sth for r in range(N) for c in range(N)}
    

    is morally the same as

    for r in range(N):
        for c in range(N):
            do sth
    

    This is a type of list comprehension.

    The idea of the code is to compute the real-time probability distribution over the board. In other words, at time t (the t-th step), it computes the probability that the knight is at grid r,c for all r and c.

    That is also why the survival rate is the sum of everything inp.values().

    Check out another idea in my post.


  • -1
    B

  • 0

    @flamesofmoon said in Python:

    list comprehension

    Almost. It's a dict comprehension.


  • 0

    @StefanPochmann Exactly!

    To be honest, this object deserves a broader name as it is useful in so many aspects and dict comprehension isn't a very popular phrase.


  • 0
    B

    @balamark Why don't you need to divide by double 8.0 to avoid integer division?


  • 0
    D

    @StefanPochmann Isn't it fairly inefficient to look through the entire board on every move even though (presumably) the knight cannot reach the majority of the squares?


  • 0

    @balamark Because I'm using Python 3 here. (Sorry, I don't feel like pointing out all the time which version I'm using... at least not if it's obvious.)


  • 0

    @david120 Well, K has a much higher limit than N. And the knight can spread fairly quickly. Even for N=25 and r=c=0, it takes only 16 rounds to reach the majority of the squares. And there can be up to 100 rounds. So likely I'm only wasting time in the beginning, not that relevant overall.

    On the other hand... I just realized that the knight switches square color with every move. For the above example, after 16 rounds it can be on any of the 313 black squares out of the board's 625 squares. After 17 rounds, it can be on any of the 312 white squares. After 18, any of the 313 black squares again. We could take advantage of that. But it would make the code longer :-). And my solution gets accepted in about 470 ms, probably well under the limit, so I'm not that motivated.


  • 0
    G

    @flamesofmoon said in Python:

    The idea of the code is to compute the real-time probability distribution over the board. In other words, at time t (the t-th step), it computes the probability that the knight is at grid r,c for all r and c.

    Well, I know about the comprehension :-) But thank you for your explanation, I got the idea that the part of code is to calculate the probability on every position.


  • 0
    D

    @StefanPochmann I suppose your solution is more of a BFS. I was thinking more in terms of a DFS, where I exhaust the probabilities of each move and its children before moving on to the next one. My code is not as short as yours, but it runs maybe a tiny bit faster (~410 ms). I'm still on the right side of the mean in terms of Python solutions, so I'm wondering what optimizations I could make.

    def knightProbability(self, N, K, r, c):
        dp = {}
        def check(K, r, c):
            if not (0 <= r < N and 0 <= c < N):
                return 0.0
            if not K:
                return 1.0
            if (K, r, c) not in dp:
                dp[K, r, c] = .125 * sum(
                    check(K-1, r+i, c+j) + check(K-1, r+j, c+i)
                    for i in (-2,2) for j in (-1,1))
            return dp[K, r, c]
            
        return check(K, r, c)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.