danielfranca danielfranca - 7 days ago 8
Python Question

Count the number of paths from start to end with obstacles

I'm trying to implement an algorithm that should count the number of paths from the bottom left to the top right of a matrix NxM.
I ran it on some website which I upload the code and it runs a bunch of test cases, I can't see which test cases it's running against to so all I know is that it's failing in some of the test cases.

The complete description of the problem:


You are given a grid of cells with size N rows by M columns. A robot
is situated at the bottom-left cell (row N-1, column 0). It can move
from cell to cell but only to the right and to the top. Some cells are
empty and the robot can pass through them but others are not and the
robot cannot enter such cells. The robot cannot go outside the grid
boundaries.

The robot has a goal to reach top-right cell (row 0, column M-1). Both
the start and end cells are always empty. You need to compute the
number of different paths that the robot can take from start to end.
Only count paths that visit empty cells and move only to the right and
up.


For that what I'm doing is:


  1. Creating an empty grid NxM, which will be used to store the number
    of paths from starting point S to grid[i][j] for each grid[i][j]

  2. F(S) = 1 # There's only one way to reach the starting point

  3. For each cell i,j I check if it's blocked, if so F(i,j) = 0

  4. For the remaining cells I sum the 2 possible ways: F(i-1,j) + F(i, j+1)



The Python code:

def count_the_paths(grid):
N = len(grid)
M = len(grid[0])

ways = [[None for _ in range(M)] for _ in range(N)] # Generate empty matrix to store the number of ways
ways[N-1][0] = 1 # There's only 1 way to reach the starting point

for row in range(N-1, -1, -1):
for col in range(0, M):
if grid[row][col] == 1: # Blocked cell
ways[row][col] = 0
elif row != N-1 or col != 0: # If it's not the starting point
ways[row][col] = 0
if row < N-1:
ways[row][col] += ways[row+1][col]
if col > 0:
ways[row][col] += ways[row][col-1]

return ways[0][M-1]


For example, if the grid is:

grid = [
[0, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 1, 1, 0, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
]


The
ways
matrix is:

ways = [
[1, 0, 0, 1, 4],
[1, 1, 0, 1, 3],
[1, 0, 0, 1, 2],
[1, 0, 1, 1, 1],
[1, 1, 1, 0, 0]
]


So the number of paths is 4, which is correct as far as I understood.

Does anyone has any idea about what I'm missing or doing wrong?

UPDATE:
As @Tempux noted I've to store the MODULO 1000003 of the number of paths.

So I changed my code:

def count_the_paths(grid):
N = len(grid)
M = len(grid[0])

ways = [[None for _ in range(M)] for _ in range(N)] # Generate empty matrix to store the number of ways
ways[N-1][0] = 1 # There's only 1 way to reach the starting point

for row in range(N-1, -1, -1):
for col in range(0, M):
if grid[row][col] == 1: # Blocked cell
ways[row][col] = 0
elif row != N-1 or col != 0: # If it's not the starting point
ways[row][col] = 0
if row < N-1:
ways[row][col] += ways[row+1][col] % 1000003
if col > 0:
ways[row][col] += ways[row][col-1] % 1000003

return ways[0][M-1]


But the error saying I produced incorrect answer is still there.

UPDATE 2:

As suggested by User_Targaryen I changed the line

if grid[row][col] == 1: # Blocked cell


to:

if grid[row][col] == "1": # Blocked cell


But it's still failing

UPDATE 3:

Then my last attempt, (tried with both char and integer) with the correction of the modular addition as suggested by Tempux:

def count_the_paths(grid):
N = len(grid)
M = len(grid[0])

ways = [[None for _ in range(M)] for _ in range(N)] # Generate empty matrix to store the number of ways


ways[N-1][0] = 1 # There's only 1 way to reach the starting point



for row in range(N-1, -1, -1):
for col in range(0, M):
if grid[row][col] == 1: # Blocked cell - also tried with char instead


ways[row][col] = 0
elif row != N-1 or col != 0: # If it's not the starting point


ways[row][col] = 0
if row < N-1:
ways[row][col] += ways[row+1][col]
ways[row][col] %= 1000003
if col > 0:
ways[row][col] += ways[row][col-1]
ways[row][col] %= 1000003

return ways[0][M-1]


Still failing

FINAL UPDATE [SOLVED]
User_Targaryen was right, there was an issue with their test cases (and they were chars, not integers)
I got this response back:


Hi Daniel,

Thanks a lot for writing to us about this. There was an issue with
some of the test cases of the problem. It is now fixed. In addition to
that, in your solution you should change the way you check if a cell
is occupied or not. Note that the input grid consists of strings of 0
and 1. They are not numbers.

We've increased your allowed number of attempts, so that you can
submit more.

Thanks again


Thanks for everyone who helped me.

Answer

Looking at the problem statement and due to lack of information about the errors in the solution, I think that the input will be somewhat like:

grid = ['01100','00010','01010','01000','00010']

Because it says: The input grid will contain N strings with M characters each - either 0 or 1

Changing the following line in your code yielded 10 more points:

if grid[row][col] == '1': # Blocked cell

Edit: You can find a very similar question here. Submit your solution to check if your basic logic is correct.

Here is my accepted solution to the CodeChef problem:

def numWays(m,n,p):
  grid = [[0 for _ in range(n)] for _ in range(m)]
  ways = [[0 for _ in range(n)] for _ in range(m)]
  mod = 1000000007
  i = 0
  while i<p:
    i=i+1
    x,y = map(int, raw_input().split())
    grid[x-1][y-1]=1

  if grid[0][0]==1 or grid[m-1][n-1]==1:
    return 0

  ways[0][0]=1

  i=0
  ways[0][0] = 1
  while i<m:
    j = 0
    while j<n:
      if grid[i][j]==0:
        if i-1>=0 and j-1>=0:
          ways[i][j] = (ways[i][j-1] + ways[i-1][j]) % mod
        elif i-1>=0:
          ways[i][j] = ways[i-1][j]
        elif j-1>=0:
          ways[i][j] = ways[i][j-1]
      j=j+1
    i = i+1

  return ways[m-1][n-1]

def main():
  m,n,p = map(int, raw_input().split())
  print numWays(m,n,p)

main()  
Comments