Python Forum

Ok, so here´s the drill: I´m doing a problem that receives a matrix of size NxN (the problem called it a "mine", hence the variable name used) containing 0´s and 1´s, and then finds the path that goes throw the least number of 1´s and then prints out the number of 1´s that the path had to go throw. So this code i made works by receiving the input variable N, and then a matrix of size NxN containing 0´s and 1´s. After that, i generate a tuple that contains all the possible paths (the letters "R" and "D" represent the way the path is going, either right or down, these are the only moves allowed in the problem´s statement). After that, i go through each possible path, and then i have a variable that counts how many 1´s did it have to go throw. The variable "min" then receives the value of the counter for each path if that counter is smaller than the previous minimum path counter. In this way, when i print the variable "min", i should get the minimum number of 1´s you have to go throw in order to complete the path of the matrix (go from [0][0] to [N-1][N-1]), but in the simples test case of a 2x2 matrix [[0, 0], [1, 0]] which is supposed to be 0, obviously, i´m getting 1. Can someone help figure this out please? (The code is down below)

from itertools import permutations

N = int(input())
Mine = [input().split() for x in range(N)]
Mine = [[int(i) for i in x] for x in Mine]

sample_path = "D"*(N-1)+"R"*(N-1)
paths = set(permutations(sample_path, 2*(N-1)))
Min = N**2

for i in list(paths):
  counter = 0
  pos = [0, 0]
  for j in i:
    if j == 'D':
      if Mine[pos[0]+1][pos[1]] == 1:
        counter += 1
        pos[0] += 1
    elif j == 'R':
      if Mine[pos[0]][pos[1]+1] == 1:
        counter += 1
        pos[1] += 1
  if counter < Min: Min = counter
    
print(Min)

The pos[0] += 1 at line 18 or pos[1] += 1 at line 22 must be executed unconditionally out of the enclosing if statement. You also need to add 1 at the beginning if Mine[0][0] == 1.

You don't need set() at line 8 and list() at line 11. It is more memory efficient if you don't use them.

That said, I think it can be solved more efficiently with dynamic programming instead of generating all the permutations.

I made an alternative version in which i make an array of all the values of each path´s counters, and then print min(array) at the end. Do you think that´s better or worse in terms of performance?

It is worse because you store all the paths, which you don't need to do. That's why I told you to remove set() and list(). The call to itertools.permutations() generates all the paths, but it doesn't store them.