1
\$\begingroup\$

I build a function(A kind of puzzle) that counts from a matrix the number of valid count (Explanation below). The matrix is ​​made up of 0,1.

Input-

  1. a matrix- list of lists
  2. row number
  3. column number

Output- valid count.

Valid Count - This is the number of cells that are in the same row and column that we got in the Input. where there is the digit 1 so the digit zero is not between them (between matrix[row][col] to those other cells).

for example-

 matrix = [[1,0,1,1],[0,1,1,1],[1,0,1,0]] valid_count(matrix, 0, 0) → 1 valid_count(matrix, 1, 0) → 0 valid_count(matrix, 1, 2) → 5 valid_count(matrix, 1, 1) → 3

I wrote a function that works properly, the problem is that it is a bit long and not elegant in my opinion. I would love advice for improving runtime, shortening the code and writing it in a more elegant way.

my code:

def valid_count(matrix, row, col): if matrix[row][col] == 0: return 0 else: return 1 + valid_count_row_helper(matrix, row, col) + valid_count_col_helper(matrix, row, col) def valid_count_row_helper(matrix, row, col): # This function checks if there are valid cells along the requested row (we received in the input) count = 0 for i in range(row + 1, len(matrix)): # checking from matrix[row][col] to matrix[len(matrix)][col] -going up if matrix[i][col] != 0: count += 1 else: break for j in range(1,row+1): if matrix[row - j][col] != 0: # checking from matrix[row][col] to matrix[0][col] -going down count += 1 else: break return count def valid_count_col_helper(matrix, row, col): # This function checks if there are valid cells along the requested column (we received in the input) count = 0 for i in range(col + 1, len(matrix[0])): # checking from matrix[row][col] to matrix[row][len(matrix[0])] -going up if matrix[row][i] != 0: count += 1 else: break for j in range(1,col+1): if matrix[row][col - j] != 0: # checking from matrix[row][col] to matrix[row][0] -going down count += 1 else: break return count
\$\endgroup\$

2 Answers 2

Reset to default
1
\$\begingroup\$

You already know the primary problem with your code: repetition. You have written reasonable code that is not difficult to understand. The problem is that you have four nearly identical chunks of code. Below is a listing of the key differences. If one focuses narrowly on the existing syntax, it's not easy to envision a way to write more general code that would handle the four situations.

for i in range(row + 1, len(matrix)): if matrix[i][col] != 0: for j in range(1,row+1): if matrix[row - j][col] != 0: for i in range(col + 1, len(matrix[0])): if matrix[row][i] != 0: for j in range(1,col+1): if matrix[row][col - j] != 0:

Step back and try to describe the needed behavior more abstractly. When faced with a situation like that, it often helps to step away from the details of syntax and instead try to understand the essence of the problem. We have a starting location: (row, col). From that location, we want to find the contiguous sequences of ones by looking in each direction: right, left, down, up.

Representing directions: use a data structure. In grid problems like this, direction of travel can often be represented by row and column location-change.

DIRECTIONS = ( (0, 1), # Right (0, -1), # Left (1, 0), # Down (-1, 0), # Up )

Exploring in all directions to compute the total. We just need to sum up the counts obtained from each direction and then make an adjustment to counteract the quadruple-counting of the starting location.

def valid_count(matrix, row, col): tot = sum( count_ones(matrix, row, col, dr, dc) for dr, dc in DIRECTIONS ) return max(0, tot - 3)

Counting ones. Once we have the idea to represent direction via row/col change values, implementing the code to do the counting is fairly straightforward: it's just a while loop that stops on the first non-one, which can occur when we hit a zero or when we run off the edge of the matrix. Because it's tedious to write code for the matrix boundary checks, it often helps in problems like this to write a small utility (similar in spirit to dict.get) to retrieve matrix values without having to worry about IndexError. That utility can also handle our other need: we do not want to support negative indexes.

def count_ones(matrix, row, col, dr, dc): n = 0 while get(matrix, row, col): n += 1 row += dr col += dc return n def get(matrix, row, col): try: return 0 if min(row, col) < 0 else matrix[row][col] except IndexError: return 0
\$\endgroup\$
1
  • \$\begingroup\$ Thank you very much, your response is very clear and detailed, you helped me a lot! \$\endgroup\$ Commented May 10, 2022 at 9:03
1
\$\begingroup\$

Your operation is pretty strange and has lots of edge cases so there's a limited amount that you can do to shorten your code. But you should probably use Numpy to handle matrix operations.

valid_count_row_helper and valid_count_col_helper are virtually the same function so they should just be one validate_vector.

Write unit tests.

There's more that can be done depending on your real call pattern, which you have not shown.

Suggested

import numpy as np def validate_matrix(matrix: np.array, row: int, col: int) -> int: if matrix[row][col] == 0: return 0 total = ( 1 + validate_vector(matrix[row, col+1:]) + validate_vector(matrix[row+1:, col]) ) if col > 0: total += validate_vector(matrix[row, col-1::-1]) if row > 0: total += validate_vector(matrix[row-1::-1, col]) return total def validate_vector(vector: np.array) -> int: if len(vector) == 0: return 0 index = np.argmin(vector) # Find the index of the first 0 if vector[index] == 0: return index # Number of 1s to the first 0 return len(vector) # Number of 1s to vector end def test() -> None: matrix = np.array(( (1, 0, 1, 1), (0, 1, 1, 1), (1, 0, 1, 0), ), dtype=np.int8) assert validate_matrix(matrix, 0, 0) == 1 assert validate_matrix(matrix, 1, 0) == 0 assert validate_matrix(matrix, 1, 2) == 5 assert validate_matrix(matrix, 1, 1) == 3 if __name__ == '__main__': test()
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.