Solve Robot Paths using backtrackingFinding node pathsRobot toy simulator18 Motor, 6 Legged robot walking using Python / ROSFinding the maximal bottleneck in a 2D matrix from source to destinationRuby sudoku solver using backtracking (interview)2D console robot warsNumber of Paths (BackTracking) in JavaSolving maze problem with backtracking solution using stackN Queens in Python using backtrackingSolve multi-dimentional optimization problem using basinhopping

Star/Wye electrical connection math symbol

Why are on-board computers allowed to change controls without notifying the pilots?

What to do with wrong results in talks?

Personal Teleportation as a Weapon

I'm in charge of equipment buying but no one's ever happy with what I choose. How to fix this?

Is it okay / does it make sense for another player to join a running game of Munchkin?

Teaching indefinite integrals that require special-casing

Is a roofing delivery truck likely to crack my driveway slab?

Why did Kant, Hegel, and Adorno leave some words and phrases in the Greek alphabet?

The baby cries all morning

What's the purpose of "true" in bash "if sudo true; then"

If a character can use a +X magic weapon as a spellcasting focus, does it add the bonus to spell attacks or spell save DCs?

apt-get update is failing in debian

Bash method for viewing beginning and end of file

How does it work when somebody invests in my business?

Everything Bob says is false. How does he get people to trust him?

What is the intuitive meaning of having a linear relationship between the logs of two variables?

Coordinate position not precise

Will it be accepted, if there is no ''Main Character" stereotype?

The Riley Riddle Mine

What's a natural way to say that someone works somewhere (for a job)?

How do I rename a LINUX host without needing to reboot for the rename to take effect?

How do I keep an essay about "feeling flat" from feeling flat?

How can a jailer prevent the Forge Cleric's Artisan's Blessing from being used?



Solve Robot Paths using backtracking


Finding node pathsRobot toy simulator18 Motor, 6 Legged robot walking using Python / ROSFinding the maximal bottleneck in a 2D matrix from source to destinationRuby sudoku solver using backtracking (interview)2D console robot warsNumber of Paths (BackTracking) in JavaSolving maze problem with backtracking solution using stackN Queens in Python using backtrackingSolve multi-dimentional optimization problem using basinhopping













2












$begingroup$


I got this problem during a mock interview, and I would like to get code review for the backtracking solution. I include 7 test cases, and my solution passes 7 out of 7 test cases. See the online code compiler here




Robot Paths



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



Examples:



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 in bounds?
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
matrix[row][col] = 0

return s

return traverse(0, 0)



#############################################
######## DO NOT TOUCH TEST BELOW!!! #######
#############################################

def expect(count, name, test):
if (count == None or not isinstance(count, list) or len(count) != 2):
count = [0, 0]
else:
count[1] += 1

result = 'false'
errMsg = None
try:
if test():
result = ' true'
count[0] += 1
except Exception as err:
errMsg = str(err)

print(' ' + (str(count[1]) + ') ') + result + ' : ' + name)
if errMsg != None:
print(' ' + errMsg + 'n')

def lists_equal(lst1, lst2):
if len(lst1) != len(lst2):
return False
for i in range(0, len(lst1)):
if lst1[i] != lst2[i]:
return False
return True

print('Robot Paths Tests')
test_count = [0, 0]


def test():
matrix = [[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]
example = robot_paths(matrix)
return example == 38


expect(test_count, 'should work on first example input', test)


def test():
matrix = [[0, 0, 0],
[0, 0, 0]]
example = robot_paths(matrix)
return example == 4


expect(test_count, 'should work on second example input', test)


def test():
matrix = [[0]]
example = robot_paths(matrix)
return example == 1


expect(test_count, 'should work on single-element input', test)


def test():
matrix = [[0, 0, 0, 0, 0, 0]]
example = robot_paths(matrix)
return example == 1


expect(test_count, 'should work on single-row input', test)


def test():
matrix = [[0],
[0],
[0],
[0],
[0]]
example = robot_paths(matrix)
return example == 1


expect(test_count, 'should work on a 5 x 8 matrix input', test)


def test():
matrix = [[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]
print(" Please be patient, test 6 may take longer to run")
example = robot_paths(matrix)
return example == 7110272


print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + 'nn')









share|improve this question









$endgroup$
















    2












    $begingroup$


    I got this problem during a mock interview, and I would like to get code review for the backtracking solution. I include 7 test cases, and my solution passes 7 out of 7 test cases. See the online code compiler here




    Robot Paths



    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



    Examples:



    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 in bounds?
    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
    matrix[row][col] = 0

    return s

    return traverse(0, 0)



    #############################################
    ######## DO NOT TOUCH TEST BELOW!!! #######
    #############################################

    def expect(count, name, test):
    if (count == None or not isinstance(count, list) or len(count) != 2):
    count = [0, 0]
    else:
    count[1] += 1

    result = 'false'
    errMsg = None
    try:
    if test():
    result = ' true'
    count[0] += 1
    except Exception as err:
    errMsg = str(err)

    print(' ' + (str(count[1]) + ') ') + result + ' : ' + name)
    if errMsg != None:
    print(' ' + errMsg + 'n')

    def lists_equal(lst1, lst2):
    if len(lst1) != len(lst2):
    return False
    for i in range(0, len(lst1)):
    if lst1[i] != lst2[i]:
    return False
    return True

    print('Robot Paths Tests')
    test_count = [0, 0]


    def test():
    matrix = [[0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]]
    example = robot_paths(matrix)
    return example == 38


    expect(test_count, 'should work on first example input', test)


    def test():
    matrix = [[0, 0, 0],
    [0, 0, 0]]
    example = robot_paths(matrix)
    return example == 4


    expect(test_count, 'should work on second example input', test)


    def test():
    matrix = [[0]]
    example = robot_paths(matrix)
    return example == 1


    expect(test_count, 'should work on single-element input', test)


    def test():
    matrix = [[0, 0, 0, 0, 0, 0]]
    example = robot_paths(matrix)
    return example == 1


    expect(test_count, 'should work on single-row input', test)


    def test():
    matrix = [[0],
    [0],
    [0],
    [0],
    [0]]
    example = robot_paths(matrix)
    return example == 1


    expect(test_count, 'should work on a 5 x 8 matrix input', test)


    def test():
    matrix = [[0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0]]
    print(" Please be patient, test 6 may take longer to run")
    example = robot_paths(matrix)
    return example == 7110272


    print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + 'nn')









    share|improve this question









    $endgroup$














      2












      2








      2





      $begingroup$


      I got this problem during a mock interview, and I would like to get code review for the backtracking solution. I include 7 test cases, and my solution passes 7 out of 7 test cases. See the online code compiler here




      Robot Paths



      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



      Examples:



      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 in bounds?
      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
      matrix[row][col] = 0

      return s

      return traverse(0, 0)



      #############################################
      ######## DO NOT TOUCH TEST BELOW!!! #######
      #############################################

      def expect(count, name, test):
      if (count == None or not isinstance(count, list) or len(count) != 2):
      count = [0, 0]
      else:
      count[1] += 1

      result = 'false'
      errMsg = None
      try:
      if test():
      result = ' true'
      count[0] += 1
      except Exception as err:
      errMsg = str(err)

      print(' ' + (str(count[1]) + ') ') + result + ' : ' + name)
      if errMsg != None:
      print(' ' + errMsg + 'n')

      def lists_equal(lst1, lst2):
      if len(lst1) != len(lst2):
      return False
      for i in range(0, len(lst1)):
      if lst1[i] != lst2[i]:
      return False
      return True

      print('Robot Paths Tests')
      test_count = [0, 0]


      def test():
      matrix = [[0, 0, 0, 0],
      [0, 0, 0, 0],
      [0, 0, 0, 0]]
      example = robot_paths(matrix)
      return example == 38


      expect(test_count, 'should work on first example input', test)


      def test():
      matrix = [[0, 0, 0],
      [0, 0, 0]]
      example = robot_paths(matrix)
      return example == 4


      expect(test_count, 'should work on second example input', test)


      def test():
      matrix = [[0]]
      example = robot_paths(matrix)
      return example == 1


      expect(test_count, 'should work on single-element input', test)


      def test():
      matrix = [[0, 0, 0, 0, 0, 0]]
      example = robot_paths(matrix)
      return example == 1


      expect(test_count, 'should work on single-row input', test)


      def test():
      matrix = [[0],
      [0],
      [0],
      [0],
      [0]]
      example = robot_paths(matrix)
      return example == 1


      expect(test_count, 'should work on a 5 x 8 matrix input', test)


      def test():
      matrix = [[0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0]]
      print(" Please be patient, test 6 may take longer to run")
      example = robot_paths(matrix)
      return example == 7110272


      print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + 'nn')









      share|improve this question









      $endgroup$




      I got this problem during a mock interview, and I would like to get code review for the backtracking solution. I include 7 test cases, and my solution passes 7 out of 7 test cases. See the online code compiler here




      Robot Paths



      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



      Examples:



      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 in bounds?
      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
      matrix[row][col] = 0

      return s

      return traverse(0, 0)



      #############################################
      ######## DO NOT TOUCH TEST BELOW!!! #######
      #############################################

      def expect(count, name, test):
      if (count == None or not isinstance(count, list) or len(count) != 2):
      count = [0, 0]
      else:
      count[1] += 1

      result = 'false'
      errMsg = None
      try:
      if test():
      result = ' true'
      count[0] += 1
      except Exception as err:
      errMsg = str(err)

      print(' ' + (str(count[1]) + ') ') + result + ' : ' + name)
      if errMsg != None:
      print(' ' + errMsg + 'n')

      def lists_equal(lst1, lst2):
      if len(lst1) != len(lst2):
      return False
      for i in range(0, len(lst1)):
      if lst1[i] != lst2[i]:
      return False
      return True

      print('Robot Paths Tests')
      test_count = [0, 0]


      def test():
      matrix = [[0, 0, 0, 0],
      [0, 0, 0, 0],
      [0, 0, 0, 0]]
      example = robot_paths(matrix)
      return example == 38


      expect(test_count, 'should work on first example input', test)


      def test():
      matrix = [[0, 0, 0],
      [0, 0, 0]]
      example = robot_paths(matrix)
      return example == 4


      expect(test_count, 'should work on second example input', test)


      def test():
      matrix = [[0]]
      example = robot_paths(matrix)
      return example == 1


      expect(test_count, 'should work on single-element input', test)


      def test():
      matrix = [[0, 0, 0, 0, 0, 0]]
      example = robot_paths(matrix)
      return example == 1


      expect(test_count, 'should work on single-row input', test)


      def test():
      matrix = [[0],
      [0],
      [0],
      [0],
      [0]]
      example = robot_paths(matrix)
      return example == 1


      expect(test_count, 'should work on a 5 x 8 matrix input', test)


      def test():
      matrix = [[0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0]]
      print(" Please be patient, test 6 may take longer to run")
      example = robot_paths(matrix)
      return example == 7110272


      print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + 'nn')






      python interview-questions






      share|improve this question













      share|improve this question











      share|improve this question




      share|improve this question










      asked 11 mins ago









      NinjaGNinjaG

      855632




      855632




















          0






          active

          oldest

          votes











          Your Answer





          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ifUsing("editor", function ()
          StackExchange.using("externalEditor", function ()
          StackExchange.using("snippets", function ()
          StackExchange.snippets.init();
          );
          );
          , "code-snippets");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "196"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader:
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          ,
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













          draft saved

          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f216295%2fsolve-robot-paths-using-backtracking%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown

























          0






          active

          oldest

          votes








          0






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes















          draft saved

          draft discarded
















































          Thanks for contributing an answer to Code Review Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid


          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.

          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f216295%2fsolve-robot-paths-using-backtracking%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          名間水力發電廠 目录 沿革 設施 鄰近設施 註釋 外部連結 导航菜单23°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.7113923°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.71139計畫概要原始内容臺灣第一座BOT 模式開發的水力發電廠-名間水力電廠名間水力發電廠 水利署首件BOT案原始内容《小檔案》名間電廠 首座BOT水力發電廠原始内容名間電廠BOT - 經濟部水利署中區水資源局

          Prove that NP is closed under karp reduction?Space(n) not closed under Karp reductions - what about NTime(n)?Class P is closed under rotation?Prove or disprove that $NL$ is closed under polynomial many-one reductions$mathbfNC_2$ is closed under log-space reductionOn Karp reductionwhen can I know if a class (complexity) is closed under reduction (cook/karp)Check if class $PSPACE$ is closed under polyonomially space reductionIs NPSPACE also closed under polynomial-time reduction and under log-space reduction?Prove PSPACE is closed under complement?Prove PSPACE is closed under union?

          Is my guitar’s action too high? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Strings too stiff on a recently purchased acoustic guitar | Cort AD880CEIs the action of my guitar really high?Μy little finger is too weak to play guitarWith guitar, how long should I give my fingers to strengthen / callous?When playing a fret the guitar sounds mutedPlaying (Barre) chords up the guitar neckI think my guitar strings are wound too tight and I can't play barre chordsF barre chord on an SG guitarHow to find to the right strings of a barre chord by feel?High action on higher fret on my steel acoustic guitar