Can disgust be a key component of horror?

What exact color does ozone gas have?

What is going on with 'gets(stdin)' on the site coderbyte?

Why can Carol Danvers change her suit colours in the first place?

How to cover method return statement in Apex Class?

Does the UK parliament need to pass secondary legislation to accept the Article 50 extension

Lowest total scrabble score

How to say when an application is taking the half of your screen on a computer

Are Captain Marvel's powers affected by Thanos' actions in Infinity War

Pre-mixing cryogenic fuels and using only one fuel tank

Strong empirical falsification of quantum mechanics based on vacuum energy density

Mixing PEX brands

Is this toilet slogan correct usage of the English language?

Non-trope happy ending?

Redundant comparison & "if" before assignment

How do I delete all blank lines in a buffer?

Why does AES have exactly 10 rounds for a 128-bit key, 12 for 192 bits and 14 for a 256-bit key size?

Fear of getting stuck on one programming language / technology that is not used in my country

Using substitution ciphers to generate new alphabets in a novel

How to explain what's wrong with this application of the chain rule?

What are some good ways to treat frozen vegetables such that they behave like fresh vegetables when stir frying them?

Why is it that I can sometimes guess the next note?

Do the primes contain an infinite almost arithmetic progression?

On a tidally locked planet, would time be quantized?

Unique Path Traversal

Finding path in MazeFinding Shortest PathGoogle Foobar Challenge: Save Beta Rabbit in Python2D A* path finderBFS shortest path for Google Foobar “Prepare the Bunnies' Escape”Any-angle path planningHorse trying to find pathBacktracking maze traversal2D Maze solver using recursion in PythonLattice path from Project Euler with Python solution

0

$begingroup$

I got this problem during a mock interview, and I would like to get code review for the backtracking solution.

Robot Paths

from Leetcode https://leetcode.com/problems/unique-paths/description/

Prompt: Given a matrix of zeroes, determine how many unique paths exist from the top left corner to the bottom right corner

Input: An Array of Array of Integers (matrix)

Output: Integer

# Example: matrix = [[0,0,0,0],
# [0,0,0,0],
# [0,0,0,0]]
#
# robotPaths(matrix) = 38
#
#
# matrix = [[0,0,0],
# [0,0,0]]
#
# robotPaths(matrix) = 4



# Note: From any point, you can travel in the four cardinal directions. I decided to do backtracking approach to solve this problem.
# (north, south, east, west). A path is valid as long as it travels
# from the top left corner to the bottom right corner, does not go
# off of the matrix, and does not travel back on itself


def robot_paths(matrix):
 num_of_rows = len(matrix)
 num_of_cols = len(matrix[0])

 def traverse(row, col):
 nonlocal num_of_rows 
 nonlocal num_of_cols
 # is row and col inside the boundaries 
 if row < 0 or row >= num_of_rows or col < 0 or col >= num_of_cols:
 return 0 

 # has row, col already been visited 
 if matrix[row][col] == 1: 
 return 0 

 # is row, col the destination? 
 if row == num_of_rows - 1 and col == num_of_cols - 1:
 return 1 

 # mark coordinate as visited 
 matrix[row][col] = 1 

 # initialize sum of total unique paths to end from that coordinate
 s = traverse(row, col + 1) + traverse(row + 1, col) + traverse(row - 1, col) + traverse(row, col - 1)

 # backtrack; mark coordinate as unvisited so it can be 
 # used in another path 
 matrix[row][col] = 0 

 return s 

 return traverse(0, 0)

python pathfinding backtracking

share|improve this question

edited 19 mins ago

bruglesco

1,6572824

asked 1 hour ago

NinjaGNinjaG

825632

$endgroup$

add a comment | 

0

$begingroup$

I got this problem during a mock interview, and I would like to get code review for the backtracking solution.

Robot Paths

from Leetcode https://leetcode.com/problems/unique-paths/description/

Prompt: Given a matrix of zeroes, determine how many unique paths exist from the top left corner to the bottom right corner

Input: An Array of Array of Integers (matrix)

Output: Integer

# Example: matrix = [[0,0,0,0],
# [0,0,0,0],
# [0,0,0,0]]
#
# robotPaths(matrix) = 38
#
#
# matrix = [[0,0,0],
# [0,0,0]]
#
# robotPaths(matrix) = 4



# Note: From any point, you can travel in the four cardinal directions. I decided to do backtracking approach to solve this problem.
# (north, south, east, west). A path is valid as long as it travels
# from the top left corner to the bottom right corner, does not go
# off of the matrix, and does not travel back on itself


def robot_paths(matrix):
 num_of_rows = len(matrix)
 num_of_cols = len(matrix[0])

 def traverse(row, col):
 nonlocal num_of_rows 
 nonlocal num_of_cols
 # is row and col inside the boundaries 
 if row < 0 or row >= num_of_rows or col < 0 or col >= num_of_cols:
 return 0 

 # has row, col already been visited 
 if matrix[row][col] == 1: 
 return 0 

 # is row, col the destination? 
 if row == num_of_rows - 1 and col == num_of_cols - 1:
 return 1 

 # mark coordinate as visited 
 matrix[row][col] = 1 

 # initialize sum of total unique paths to end from that coordinate
 s = traverse(row, col + 1) + traverse(row + 1, col) + traverse(row - 1, col) + traverse(row, col - 1)

 # backtrack; mark coordinate as unvisited so it can be 
 # used in another path 
 matrix[row][col] = 0 

 return s 

 return traverse(0, 0)

python pathfinding backtracking

share|improve this question

edited 19 mins ago

bruglesco

1,6572824

asked 1 hour ago

NinjaGNinjaG

825632

$endgroup$

add a comment | 

$begingroup$

I got this problem during a mock interview, and I would like to get code review for the backtracking solution.

Robot Paths

from Leetcode https://leetcode.com/problems/unique-paths/description/

Prompt: Given a matrix of zeroes, determine how many unique paths exist from the top left corner to the bottom right corner

Input: An Array of Array of Integers (matrix)

Output: Integer

# Example: matrix = [[0,0,0,0],
# [0,0,0,0],
# [0,0,0,0]]
#
# robotPaths(matrix) = 38
#
#
# matrix = [[0,0,0],
# [0,0,0]]
#
# robotPaths(matrix) = 4



# Note: From any point, you can travel in the four cardinal directions. I decided to do backtracking approach to solve this problem.
# (north, south, east, west). A path is valid as long as it travels
# from the top left corner to the bottom right corner, does not go
# off of the matrix, and does not travel back on itself


def robot_paths(matrix):
 num_of_rows = len(matrix)
 num_of_cols = len(matrix[0])

 def traverse(row, col):
 nonlocal num_of_rows 
 nonlocal num_of_cols
 # is row and col inside the boundaries 
 if row < 0 or row >= num_of_rows or col < 0 or col >= num_of_cols:
 return 0 

 # has row, col already been visited 
 if matrix[row][col] == 1: 
 return 0 

 # is row, col the destination? 
 if row == num_of_rows - 1 and col == num_of_cols - 1:
 return 1 

 # mark coordinate as visited 
 matrix[row][col] = 1 

 # initialize sum of total unique paths to end from that coordinate
 s = traverse(row, col + 1) + traverse(row + 1, col) + traverse(row - 1, col) + traverse(row, col - 1)

 # backtrack; mark coordinate as unvisited so it can be 
 # used in another path 
 matrix[row][col] = 0 

 return s 

 return traverse(0, 0)

python pathfinding backtracking

share|improve this question

edited 19 mins ago

bruglesco

1,6572824

asked 1 hour ago

NinjaGNinjaG

825632

$endgroup$

# Example: matrix = [[0,0,0,0],
# [0,0,0,0],
# [0,0,0,0]]
#
# robotPaths(matrix) = 38
#
#
# matrix = [[0,0,0],
# [0,0,0]]
#
# robotPaths(matrix) = 4



# Note: From any point, you can travel in the four cardinal directions. I decided to do backtracking approach to solve this problem.
# (north, south, east, west). A path is valid as long as it travels
# from the top left corner to the bottom right corner, does not go
# off of the matrix, and does not travel back on itself


def robot_paths(matrix):
 num_of_rows = len(matrix)
 num_of_cols = len(matrix[0])

 def traverse(row, col):
 nonlocal num_of_rows 
 nonlocal num_of_cols
 # is row and col inside the boundaries 
 if row < 0 or row >= num_of_rows or col < 0 or col >= num_of_cols:
 return 0 

 # has row, col already been visited 
 if matrix[row][col] == 1: 
 return 0 

 # is row, col the destination? 
 if row == num_of_rows - 1 and col == num_of_cols - 1:
 return 1 

 # mark coordinate as visited 
 matrix[row][col] = 1 

 # initialize sum of total unique paths to end from that coordinate
 s = traverse(row, col + 1) + traverse(row + 1, col) + traverse(row - 1, col) + traverse(row, col - 1)

 # backtrack; mark coordinate as unvisited so it can be 
 # used in another path 
 matrix[row][col] = 0 

 return s 

 return traverse(0, 0)

share|improve this question

edited 19 mins ago

bruglesco

1,6572824

asked 1 hour ago

NinjaGNinjaG

825632

share|improve this question

edited 19 mins ago

bruglesco

1,6572824

asked 1 hour ago

NinjaGNinjaG

825632

edited 19 mins ago

bruglesco

1,6572824

edited 19 mins ago

bruglesco

1,6572824

asked 1 hour ago

NinjaGNinjaG

825632

asked 1 hour ago

NinjaGNinjaG

825632