Home » Interview coding problems/challenges

Island Probability

Here, we are going to learn to find the solution of Island Probability, calculate the probability of being alive after moving n steps.
Submitted by Divyansh Jaipuriyar, on August 16, 2020

Problem statement

You are standing in some location (x, y) on an island, given in form of a matrix of size N*M, you are allowed to move in all four directions left, right, up and down. You can move only one step at a time, if you step out of the matrix region then you die. Calculate the probability of being alive after moving n steps.

Problem description:

The problem wants you to use knowledge of probability, you are standing at some location in the matrix and you are allowed to move in all four directions from the current location as left, right, down and up, but you need to keep in mind that you can only take K steps and if you fall out you die that is probability becomes 0 and if you utilized all K moves and you are under index range then the probability is 1. So you need to develop some logic that you can maximize the probability of surviving in that island.

Input

The first line of the input is the T number of test cases, each test case consists of N, size of the given matrix(N*N), and the starting point (x,y) in the following line and the number of moves k that he has.

Output

You are required to print the probability of person being alive after n moves.

Examples

Input:
T=1
N=3
x=1,y=1
k=4

Output:
0.375

Input:
T=1
N=4
x=2,y=2
k=3

Output:
0.71875

Solution Approach

Recursion Approach:

We will use a recursive function to solve this problem, we will create a solve function which will take a number of steps that we have, the coordinates as its input and return the probability of being alive if the number of steps remaining is 0 and we are under that matrix boundary then we simply 1 otherwise we will recursively call solve function in all four directions until we are left with 0 moves remaining.

The probability of traveling in all four directions is (0.25) as all have equal probability.

let f(x, y, n) be some function then it can be defined as:

let f(x, y, n) be some function then it can be defined as:
f(x,y,n)=f(x+1,y,n-1)*.25+f(x-1,y,n-1)*.25+f(x,y-1,n-1)*.25+f(x,y+1,n-1)*.25

Time complexity for above approach in worst case is exponential.

Space complexity for above approach in worst case is constant.

Dynamic Programming Approach:

In this approach we will use memoization technique to optimize our solution from exponential time to some efficient time, we will create a map for storing values for different states, each time we make a recursive call we will first check it in dp table, if already calculated then simply return it otherwise we calculate it again.

Time complexity for the above approach in the worst case is: O(n*n*n)

Space complexity for the above approach in the worst case is: O(n*n*n)

1) C++ Implementation (Recursion)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//solve function which will return
//probability of being alive.
double solve(ll x, ll y, ll k, ll n)
{
    //if remaining moves is 0 and
    //we are under safe boundary region
    //then probability is 1.
    if (k == 0)
        return 1.0;

    //initialize probability variable prob
    //with 0.
    double prob = 0;

    //check if we can move in up direction
    //that is (x-1) index.
    if (x > 0)
        prob += solve(x - 1, y, k - 1, n) * (.25);

    //check if we can move in down direction
    //that is (x+1) index.
    if (x < n - 1)
        prob += solve(x + 1, y, k - 1, n) * (.25);

    //check if we can move in left direction
    //that is (y-1) index.
    if (y > 0)
        prob += solve(x, y - 1, k - 1, n) * (.25);

    //check if we can move in right direction
    //that is (y+1) index.
    if (y < n - 1)
        prob += solve(x, y + 1, k - 1, n) * (.25);

    //finally return overall probability.
    return prob;
}

int main()
{
    cout << "Enter number of test cases: ";
    ll t;
    cin >> t;

    while (t--) {
        cout << "Enter size of N: ";
        ll n, k;
        cin >> n;

        cout << "Enter initial location: ";
        ll x, y;
        cin >> x >> y;

        cout << "Enter moves:\n";
        cin >> k;

        cout << "Probability of being alive: ";
        cout << solve(x, y, k, n) << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size of N: 2
Enter initial location: 0 0
Enter moves:
1
Probability of being alive: 0.5
Enter size of N: 3
Enter initial location: 1 1
Enter moves:
2
Probability of being alive: 0.75
Enter size of N: 3
Enter initial location: 0 0
Enter moves:
3
Probability of being alive: 0.25

2) C++ Implementation (Dynamic Programming):

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//unordered map for storing
//dp state (memorization).
unordered_map<string, double> dp;

//solve function which will return
//probability of being alive.
double solve(ll x, ll y, ll k, ll n)
{
    //if remaining moves is 0 and
    //we are under safe boundary region
    //then probability is 1.
    if (k == 0)
        return 1.0;

    //string variable for finding whether
    //given states already calculated or not.
    string str = "";
    str = to_string(x) + to_string(y) + to_string(k);

    //check if already calculated or not.
    if (dp.find(str) != dp.end())
        return dp[str];

    //initialize probability variable prob
    //with 0.
    double prob = 0;

    //check if we can move in up direction
    //that is (x-1) index.
    if (x > 0)
        prob += solve(x - 1, y, k - 1, n) * (.25);

    //check if we can move in down direction
    //that is (x+1) index.
    if (x < n - 1)
        prob += solve(x + 1, y, k - 1, n) * (.25);

    //check if we can move in left direction
    //that is (y-1) index.
    if (y > 0)
        prob += solve(x, y - 1, k - 1, n) * (.25);

    //check if we can move in right direction
    //that is (y+1) index.
    if (y < n - 1)
        prob += solve(x, y + 1, k - 1, n) * (.25);

    //finally store and return overall probability.
    return dp[str] = prob;
}

int main()
{
    cout << "Enter number of test cases: ";
    ll t;
    cin >> t;

    while (t--) {
        cout << "Enter size of N: ";
        ll n, k;
        cin >> n;

        cout << "Enter initial location: ";
        ll x, y;
        cin >> x >> y;

        cout << "Enter moves:\n";
        cin >> k;

        cout << "Probability of being alive: ";
        cout << solve(x, y, k, n) << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 2
Enter size of N: 3  
Enter initial location: 1 1
Enter moves:
4
Probability of being alive: 0.375
Enter size of N: 4  
Enter initial location: 2 2
Enter moves:
3
Probability of being alive: 0.71875