Probability Of Alive On Island | N00tc0d3r

Probability Of Alive On Island | N00tc0d3r
There is an island which is represented by square matrix NxN, represented as (0,0) to (N-1,N-1).
A person on the island is standing at given coordinates (x,y). He can move in any direction one step, right, left, up, down on the island. If he steps outside the island, he dies.

Now He is allowed to move n steps on the island (along the matrix). What is the probability that he is alive after he walks n steps on the island?
Write an efficient full code and tests for function double probabilityOfAlive(int x,int y, int n).
Prob(x, y, step) = 0.25*Prob(x-1, y, step-1) + 0.25*Prob(x, y-1, step-1)
                            + 0.25*Prob(x+1, y, step-1) + 0.25*Prob(x, y+1, step-1)

Solution - Recursion

This problem is similar to the Edit Distance problem we discussed before.

Let's start from a island of size 1x1. Since one step towards any direction will get out of the island, the probability to alive is 0.

Given a island of 3x3 and let's stand at (1,1) which is the center of the island. There are four possibilities and assume the probability of each is the same, 0.25. Walking one step towards any direction will end at a spot on the island. So the probability of alive is (1+1+1+1)/4 = 1.

Now let's stand at (0,1). Walking up one step will get out of the island! So the probability of alive is (0+1+1+1)/4 = 0.75.

Generalizing the formula, we have:

Prob(x, y, step) = 0.25*Prob(x-1, y, step-1) + 0.25*Prob(x, y-1, step-1)
                            + 0.25*Prob(x+1, y, step-1) + 0.25*Prob(x, y+1, step-1)

   public static double probabilityOfAlive(int x,int y, int step, int n) {  
     if (x<0 || y<0 || x>=n || y>=n) return 0;  
     if (step == 0) return 1;  
     return 0.25*probabilityOfAlive(x-1, y, step-1, n)  
         + 0.25*probabilityOfAlive(x, y-1, step-1, n)  
         + 0.25*probabilityOfAlive(x+1, y, step-1, n)  
         + 0.25*probabilityOfAlive(x, y+1, step-1, n);  
   }  




Solution - DP

   public static double probabilityOfAlive(int x,int y, int step, int n) {  
     if (x<0 || y<0 || x>=n || y>=n || (n==1 && step==1)) return 0;  
     if (step == 0) return 1;  
     double[][][] probTable = new double[n][n][2];  
     int sp = 0;  
     // init for step=1  
     for (int i=0; i<n; ++i) {  
       for (int j=0; j<n; ++j) {  
         probTable[i][j][sp] = 0;  
         if (i>0) probTable[i][j][sp] += 0.25;  
         if (j>0) probTable[i][j][sp] += 0.25;  
         if (i+1<n) probTable[i][j][sp] += 0.25;  
         if (j+1<n) probTable[i][j][sp] += 0.25;  
       }  
     }  
     // calculate with DP  
     while (sp < (step-1)) {  
       int pre = sp++;  
       for (int i=0; i<n; ++i) {  
         for (int j=0; j<n; ++j) {  
           probTable[i][j][sp&1] = 0;  
           if (i>0) probTable[i][j][sp&1] += 0.25*probTable[i-1][j][pre&1];  
           if (j>0) probTable[i][j][sp&1] += 0.25*probTable[i][j-1][pre&1];  
           if (i+1<n) probTable[i][j][sp&1] += 0.25*probTable[i+1][j][pre&1];  
           if (j+1<n) probTable[i][j][sp&1] += 0.25*probTable[i][j+1][pre&1];  
           if (sp==step-1 && i==x && j==y) return probTable[x][y][sp&1];  
         }  
       }  
     }  
     return probTable[x][y][sp&1];  
   }  

Recall that in Edit Distance problem, we only use a table of two rows to store the values.
Here we can reduce some spaces too.
Since the table is symmetric, we only need 1/4 of table and a lookup method that can map (i, j) to correct spot in the shrinked table.
http://www.careercup.com/question?id=15556758
http://stackoverflow.com/questions/16522296/probability-of-death-of-a-man-moving-n-steps-in-a-matrix
https://www.techiedelight.com/probability-alive-after-taking-n-steps-island/

float aliveProbability(int x, int y, int n, map<string, float> &dp)

{

    // base case

    if (n == 0)

        return 1.0;

    // calculate unique map key from current coordinates(x, y) of person

    // and number of steps(n) left

    string key = to_string(x) + "|" + to_string(y) + "|" + to_string(n);

    

    // if sub-problem is seen for the first time

    if (dp.find(key) == dp.end())

    {

        float p = 0.0;

        // move one step up

        if (x > 0)

            p += 0.25 * aliveProbability(x - 1, y, n - 1, dp);

        // move one step down

        if (x < N - 1)

            p += 0.25 * aliveProbability(x + 1, y, n - 1, dp);

        // move one step left

        if (y > 0)

            p += 0.25 * aliveProbability(x, y - 1, n - 1, dp);

        // move one step right

        if (y < N - 1)

            p += 0.25 * aliveProbability(x, y + 1, n - 1, dp);

        dp[key] = p;

    }

    return dp[key];

}

Prob(x, y, step) = 0.25*Prob(x-1, y, step-1) + 0.25*Prob(x, y-1, step-1)