4

There is an island represented by a matrix. You are somewhere on the island at location (x,y). If you jump n times, what is the probability you will survive? Survival means after n jumps you must be on the island.

My solution: I applied flood fill algorithm in which I allowed to move in all directions (i.e. N, W, E, S) and checked if before n jumps I was off the island then increment the failure counter, otherwise increment the success counter.

After iterating all the possible paths, the answer is ((success)/(success + failure)). It takes exponential time.

My question from you is can we do this problem in polynomial time, by using dynamic programming or any other programming technique? If yes, can you give me the concept behind that technique?

EDIT: MY CODE

#include<iostream>

using namespace std;

double probability_of_survival(int n, int m, int x, int y, int jumps) {
    int success = 0;
    int failure = 0;
    probability_of_survival_utility_func(n, m, x, y, 0, jumps, &sucess, &failure);
    return (double)((success)/(failure+success));
}

void probability_of_survival_utility_func(int n, int m, int x, int y, int jump_made, int jumps, int *success, int *failure) {
    if(x > m || x < 0 || y > n || y < 0) { (*failure)++; return;}
    if(jump_made == jumps) { (*success)++; return;}
    probability_of_survival_utility_func(n, m, x+1, y, jump_made++, jumps, success, failure);
    probability_of_survival_utility_func(n, m, x, y+1, jump_made++, jumps, success, failure);
    probability_of_survival_utility_func(n, m, x-1, y, jump_made++, jumps, success, failure);
    probability_of_survival_utility_func(n, m, x, y-1, jump_made++, jumps, success, failure);
}
13
  • Can you define survival? What conditions should be met in order for you to survive?
    – amit
    Aug 28, 2012 at 12:29
  • 1
    So to paraphrase: You basically start somewhere on the island and you have to find the probability that a random walk of n steps won't ever leave the island? Also I think you mean brute force, not flood fill, because a flood fill would be O(n^2).
    – JPvdMerwe
    Aug 28, 2012 at 12:29
  • 2
    As stated your problem is trivial. If the man is standing on the island and if the island has size at least 2x1 then the man jumps to the neighbouring location, then back again, and repeats the process n times. If the island is only 1x1 the man is just plain out of luck. Aug 28, 2012 at 12:31
  • amit, Survival means after n jumps you must be on the island, not in the water, cry for help :P
    – devsda
    Aug 28, 2012 at 12:31
  • For better understanding of my approach, I posted my code.
    – devsda
    Aug 28, 2012 at 12:42

2 Answers 2

4

The problem is neatly described by a Markov matrix. Translate the problem into a graph the following way. Map the rows of the matrix onto the coordinates, that is, for every possible (x,y) -> i. Build a symmetric adjacency matrix A such that (i,j)=1 if and only if the sites (x1,y1)->i, (x2,y2)->j are connected. All death sites will map to a single site and have the property such that A[i,i]=1, A[i,j!=i]=0 i.e it is an adsorbing states. Row normalize the matrix. With a starting vector p=[0,0,0,...,1,...,0,0] where the one corresponds to the starting position take the product:

 (A**k) . p

And sum over the live sites, this will give you the survival probability. For analysis, the number of note here is n, the number of alive sites on the island. Complexity is neatly bound, the most expensive operation is matrix exponentiation A**k. Naively this can be done in O(n**3 * k), but I suspect that you can diagonalize the matrix first at a cost of O(n**3) and exponentiate the eigenvalues.

Visual Example:

An island, with a red start point and it's adjacency matrix:

enter image description here

the calculated survival probability as a function of steps:

enter image description here

Python Implementation:

from numpy import *

# Define an example island
L = zeros((6,6),dtype=int)
L[1,1:2] = 1
L[2,1:4] = 1
L[3,1:5] = 1
L[4,2:4] = 1

# Identify alive sites
alive = zip(*where(L))
N = len(alive)

# Map the entries onto an index for easy access
ID = dict(zip(alive, range(N)))

# Create adj. matrix, the final index is the dead site
def connect(x, horz, vert):
    s = (x[0]+horz, x[1]+vert)
    if s not in ID: A[ID[x], N] += 1
    else          : A[ID[x], ID[s]] += 1
    
A = zeros((N+1,N+1))
for x in alive:
    connect(x,  1, 0)
    connect(x, -1, 0)
    connect(x,  0, 1)
    connect(x,  0,-1)

# Define the dead site as adsorbing, and row normalize
A[N,N] = 1
A /= A.sum(axis=1)[:,newaxis]


# Define the initial state
inital = (3,2)
p0 = zeros(N+1)
p0[ID[inital]] = 1

# Compute survival prob. as a function of steps
steps = 20
A2 = A.copy()
S = zeros(steps)
for t in xrange(steps):
    S[t] = 1-dot(A2.T,p0)[-1]
    A2   = dot(A2, A)

# Plot results
import pylab as plt
plt.subplot(121)
LSHOW = L.copy()
LSHOW[inital] = 2
plt.imshow(LSHOW,interpolation='nearest')
plt.subplot(122)
plt.imshow(A,interpolation='nearest')
plt.figure()
plt.plot(range(steps), S,'ro--')
plt.show()
1
  • Yep, this is my canonical markov matrix example, so it makes sense to do it this way!
    – argentage
    Aug 31, 2012 at 18:20
3
f(x,y,0) = 0     if (x,y) is not in the island
           1     otherwise

f(x,y,i) = 0     if (x,y) is not in the island
           otherwise: 1/4 * f(x+1,y,i-1) + 
                      1/4 * f(x-1,y,i-1) + 
                      1/4 * f(x,y+1,i-1) + 
                      1/4 * f(x,y-1,i-1)

Using Dynamic programming you can create 2n+1 x 2n+1 x n+1 3-dimensional array,and filling it according to this formula, starting from i=0 and making you way up until i=n.

Your solution at the end is f(0,0,n) in the array. (Remmeber to set the original (x,y) as (0,0) in your coordinates, and make the needed adjustments).

Complexity is O(n^3) - the size of the matrix.

Note, this solution is pseudo-polynomial, so if any future answers shows this problem is NP-Hard (no idea if it is) - it does not contradict it.

P.S. For real implementations - if you need exact answer - be very careful when using double precision numbers - especially for large number of steps, since the carried numerical error might become significant.

9
  • 2
    You don't need to make adjustments to the coordinate system. Also you can get away with O(n^2) memory, by only storing 2 levels of the array. Since you only ever access i and i-1.
    – JPvdMerwe
    Aug 28, 2012 at 12:44
  • Can you tell what the compexity of my code is?? I think exponential
    – devsda
    Aug 28, 2012 at 12:45
  • @JPvdMerwe: I agree according to the 2nd - but note that it does not change the time complexity, the 1st just seems simpler IMO - but might be subjective.
    – amit
    Aug 28, 2012 at 12:45
  • @jhamb: I believe you are correct. You are trying all possible routes. There are exponential number of those, and thus the solution is indeed exponential.
    – amit
    Aug 28, 2012 at 12:47
  • @jhamb: Also: some optimizations could be taken place: You might be able to reduce the size of the matrix, I don't think you need (-100,-100,0) if the island is a square of size 10 around (0,0). This can significantly reduce the run time.
    – amit
    Aug 28, 2012 at 12:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.