Number of ways to bottom-right of matrix with obstacles with any size skips right or down

Question

Question - You have to find the number of ways you can reach from the intial position (1,1) to the final position (N,M) [where N is the number of rows and M is the number of columns], given that:

1. You can move any number of steps downwards.
2. You can move any number of steps towards the right.

Note: Here the array indices are 1-indexed

Some conditions:

• You can never move out of the grid.
• You cannot ignore the conditions.
• The first cell (1,1) and the last cell (N,M) do not contain obstacles.
• A free cell is denoted by . and an obstacle is denoted by *.

---

Sample test case:

>>> 3 3
    . . .
    . * .
    . . .

>>> 8

There will be 8 ways:

• (1,1),(1,2),(1,3),(2,3),(3,3)
• (1,1),(1,2),(1,3),(3,3)
• (1,1),(1,3),(2,3),(3,3)
• (1,1),(1,3),(3,3)
• (1,1),(2,1),(3,1),(3,2),(3,3)
• (1,1),(3,1),(3,2),(3,3)
• (1,1),(2,1),(3,1),(3,3)
• (1,1),(3,1),(3,3)

---

My code:

def ways(l):
    
   # Don't know how to proceed



Testcases=int(input())
lst=[]
for i in range(Testcases):
    N,M=input().split()
    N,M=int(N),int(M)
    for j in range(N):
        s=input().split(" ",M)
        lst.append(s)
    
    ways(lst)

I have no idea how to proceed.

Answer 1

When you approach this kind of problems, you should start with looking for some patterns that could come out in a subproblem. For example, one subproblem you have is to find the number of ways you can move along aligned points. First, build a table with the number of points on the left and the number of ways to reach the last one on the right.

2  1
3  2
4  4
5  8
6  16
...

It should be pretty clear that the pattern is number_of_ways = 2^(number_of_points - 2). I am not a mathematician, so do not ask me why, but you can easily prove it computing all the combinations, perhaps with dynamic programming. Here is the code, or you can trust me (which I strongly suggest you not to do it)

n = 12
dp = [None] * (n + 1)

def num_of_subset(n):
    if dp[n] != None:
        return dp[n]
    elif n == 1:
        return 1
    else:
        ways = 0
        for i in range(n):
            ways += num_of_subset(n - (i + 1))
        
        dp[n] = ways
        return ways
        
print(num_of_subset(n))

First part is gone, now we know something that makes everything much easier: every time you add a new "point", the number of possible ways duplicates.

---

Second part: there are many things to take into account:

1. you need to track how many consecutives and aligned points you have. To do this each entry of the DP table is a tuple, first and second element are the counter from top and from left.
2. to get the total number of ways from starting point to the end, each tuple contains in the last index the total number of ways to reach that specific cell.
3. an obstacle is distant -1 from both top and left, a single isolated point is distant 0 both from top and left. a second aligned point does not add any other ways to reach the end because you are forced to pass on it. Instead, let's say you are looking at the upper cell, from the 3rd aligned point you double the ways of the top cell.
4. The first cell starts automatically with a 1 in the third index of the tuple (the computed ways until now). This is because if you have a single a matrix 1x1, there is one way to reach the end, and that consists on essentially doing nothing.

It is kind of hard to explain, so here is the code:

rows = 3
cols = 3

matrix = """
    ...
    .*.
    ...
"""

matrix = [list(r) for r in matrix.split()]
print(matrix)

#(from_top_distance, from_left_distance, totways_until_here)
dp = [[(-1, -1, 0)] * cols for _ in range(rows)]

for ri, r in enumerate(matrix):
    for ci, c in enumerate(r):
        if c == '*':
            continue
        
        if ri == 0 and ci == 0:
            dp[ri][ci] = (0, 0, 1)
            continue
        
        if (ri == 0 or dp[ri - 1][ci][0] == -1) and (ci == 0 or dp[ri][ci - 1][1] == -1):
            dp[ri][ci] = (-1, -1, 0)
            continue
        
        from_top = 0 if ri == 0 else dp[ri - 1][ci][0] + 1
        from_left = 0 if ci == 0 else dp[ri][ci - 1][1] + 1
        
        top_value = 0 if ri == 0 \
            else dp[ri - 1][ci][2] if from_top < 2 \
            else dp[ri - 1][ci][2] * 2
            
        left_value = 0 if ci == 0 \
            else dp[ri][ci - 1][2] if from_left < 2 \
            else dp[ri][ci - 1][2] * 2
        
        dp[ri][ci] = (from_top, from_left, top_value + left_value)

print(dp)
print(dp[rows - 1][cols - 1][2])

The beauty of this code (if it is correct) is that the computational complexity is O(M*N).

Answer 2

(Code here.)

A naive reccurence would seem to be the sum of all ways to get to each possible predecessor. (Clearly, a blocked cell has zero ways to arrive at, and we don't count preceding cells' ways.) Let f(i, j) represent all the ways to get to cell M[i][j]. Then:

f(0, 0) ->
  1

f(i, 0) ->
  sum(f(k, 0)) for 0 ≤ k < i
  
f(0, j) ->
  sum(f(0, k)) for 0 ≤ k < j
  
f(i, j) ->
  sum(f(k, j)) for 0 ≤ k < i +
  sum(f(i, k)) for 0 ≤ k < j

Because of the variation caused by the blocked cells, in order to avoid the extra factor in complexity from the sum, we can use tuples (num_ways_here, cumulative_from_north, cumulative_from_east) to keep linear complexity:

A B C
D x E
F G H
I J K

(num_ways_here, cumulative_from_north, cumulative_from_east)

A (1, 1, 1)
  D (1, 2, 1)
  F (2, 4, 2)
  I (4, 8, 4)
    G (2, 2, 4)
      J (6, 8, 10)
  B (1, 1, 2)
  C (2, 2, 4)
    E (2, 4, 2)
    H (8, 12, 12)
        K (22, 34, 32)

The transition for turns is that when a component is missing, it inherits num_ways_here instead of the sum with the component (in other words num_ways_here + 0.

22 ways to get to K:

(1)
.
. x
.
. . .

(2)
.
  x
.
. . .

(3)
.
. x

. . .

(4)
.
. x
.
.   .

(5)
.
  x

. . .

(6)
.
  x
.
.   .

(7)
.
. x

.   .

(8)
.
  x

.   .

(9)
.
. x
. .
  . .
  
(10)
.
  x
. .
  . .
  
(11)
.
. x
. . .
    .
    
(12)
.
  x
. . .
    .
  
(13)
.
. x
.   .
    .
    
(14)
.
  x
.   .
    .
  
(15)
. . .
  x .
    .
    .
    
(16)
.   .
  x .
    .
    .
    
(17)
. . .
  x
    .
    .
    
(18)
. . .
  x .

    .
    
(19)
.   .
  x
    .
    .
    
(20)
.   .
  x .

    .
    
(21)
. . .
  x

    .
    
(22)
.   .
  x

    .

Answer 3

Encoding the paths as a string of left (L=incrementing rows) and right (R=incrementing columns) steps you have a set of permutations of possible paths through the array. Then you would check, for each path, if you hit an obstacle. This could look like this (no error handling, just very limited tests performed, game board entry omitted i.e. your . and * are implemented as 0 and 1 for now, N=row-steps, M=col-steps, i.e. the array with the nodes has dimensions (N+1, M+1)):

import numpy as np
import itertools
import random

def chk_pth(path, gboard):
    row, col = 0, 0
    for sidx, stp in enumerate(path): # step through gameboard along path
        if stp == 'L':
            row += 1
        else:
            col += 1
        if gboard[row, col] == 1: # obstacle?
            return False
    return True
    
lst=[]
N, M = input().split()
N, M=int(N), int(M)
# gameboard input omitted
lst = np.zeros((N+1, M+1))
lst[random.randint(1, N), random.randint(1, M)] = 1 # hard-coded for now, todo: change to manual input
lst[N, M] = 0 # guaranteed unblocked exit
print(lst)

# N = rows, M = cols
pthstr = 'L' * N + 'R' * M # we encode the paths uniquely as lefts and right (left=row+1, right=col+1)
uq_paths = set(list(itertools.permutations(pthstr, N+M))) # only need unique paths, permutations gives multiple results
path_ok = []
for pidx, path in enumerate(uq_paths):
    path_ok.append(chk_pth(path, lst))

print([pth for pidx, pth in enumerate(uq_paths) if path_ok[pidx]]) # only show valid paths

which results in (note random gameboard, first the board shown, then the valid paths):

[[0. 0. 0. 0.]
 [0. 0. 1. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]
[('L', 'R', 'L', 'R', 'L', 'R'), ('L', 'R', 'L', 'R', 'R', 'L'), ('L', 'R', 'L', 'L', 'R', 'R'), ('L', 'L', 'R', 'R', 'R', 'L'), ('L', 'L', 'R', 'R', 'L', 'R'), ('R', 'L', 'L', 'L', 'R', 'R'), ('L', 'L', 'R', 'L', 'R', 'R'), ('R', 'L', 'L', 'R', 'L', 'R'), ('L', 'L', 'L', 'R', 'R', 'R'), ('R', 'L', 'L', 'R', 'R', 'L'), ('R', 'R', 'R', 'L', 'L', 'L')]

Answer 4

First I would break the problem down into smaller problems:

1. Find all possible permutations of right moves to get from (0,0) to (1,M)
2. Find all possible permutations of down moves to get from (0,0) to (N,1)
3. Find all possible permutations of interlacing 1. and 2. to get all possible move-combinations from (0,0) to (N,M)
4. Remove those move-combinations that intersect with an obstacle.
5. Profit.

(My code is 0-indexed)

1./2. Moves into one direction

This problem can be reformulated as "all list of natural numbers that sum to N/M". This has already been extensively answered here: https://stackoverflow.com/a/4633515/8106583

With slight adjustments to allow for repetitions we get:

def subset_sum(target, result, partial=[]):
    s = sum(partial)
    if s == target:  #check if the partial sum is equals to target
        result.append(partial)
        return
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(1,target+1):
        subset_sum(target, result, partial + [i])

So that we can use rightMovesAll = []; subset_sum(M-1, rightMovesAll to get all permutations of right moves (same for down) which results for M=5 in rightMovesAll=[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]

3. Inderlacing

Now for each combination of one rightMoves and one downMoves we need to interlace, meaning to get all possible orders of them.

movesAll = []
for rightMoves in rightMovesAll:
    for downMoves in downMovesAll:
        interlace(rightMoves, downMoves, movesAll)

To not loose the information on a moves direction we convert all moves to moveVektor. Meanting a rightMove of 3 becomes (0,3) and a downMove of 4 becomes (3,0) The interlacing function (inspired by this answer) is the following

def interlace(rightMoves, downMoves, movesAll, partial=[]):
    if len(rightMoves) == 0 and len(downMoves) == 0:
        movesAll.append(partial)
        return
    else:
        if len(rightMoves) > 0:
            interlace(rightMoves[:-1], downMoves, movesAll, partial + [(0, rightMoves[-1])])
        if len(downMoves) > 0:
            interlace(rightMoves, downMoves[:-1], movesAll, partial + [(downMoves[-1], 0)])

Now we have a list of all possible combinations of moveVektors to get from (0,0) to (N-1,M-1)

4. Removing paths with obstacles

Before we can remove paths, we need to convert the list of moveVektors to the actual sequence of positions (like you provided in your example)

import operator
positionsAll = []
for vectors in vectorsAll:
    positions = []
    position = (0,0)
    for vector in vectors:
        position = tuple(map(operator.add, position, vector))
        positions.append(position)
    positionsAll.append(positions)

Now we need a list of all obstacle-positions so that we can check for intersections:

obstacles = [(2,2)] #example of a obstacle at 2,2
for obstacle in obstacles:
    for positions in positionsAll:
        if(obstacle in positions):
            positionsAll.remove(positions)

This would leave us with the sequences of positions like you asked for.

Hope this works for You.

P.S. Be careful. The computational complexity grows exponentially! Also my code is 0-indexed