Overview This question is broken down into 2 stages. 1. Complete the provided generate_paths (matrix) function that iterates all legal paths using a depth-first search (DFS). The function is pretty much complete, and there are a couple of sections where students will need to "add" or "adjust" code. 2. Write a function brute_force (matrix) that takes in the same grid as Q1, and returns the maximum possible score achievable with the optimal path as an integer. Part 1 The provided generate_paths (matrix) function only prints all the paths found and returns None. Your task is to change the function code in two locations by: 1. Replacing the print (path) with code that will add or assign the path to a variable so you can keep track of it. 2. Return all your paths so you can use them in the next function (brute_force) You are free to alter the function, including adding/initializing your own variables. Additionally, there will be a generate_next path function which Notes 1. Replacing the print(path) with code that will add or assign the path to a variable so you can keep track of it. 2. Return all your paths so you can use them in the next function (brute_force) You are free to alter the function, including adding/initializing your own variables. Additionally, there will be a generate_next_path function which students will need to implement in order for the generate_paths function to work. The locations to change your code will be marked with a # ### comment block. Please note that the path variable in this function changes values over each iteration. You should try and use the list.copy() method to copy the best path, rather than assigning it to a variable. Click on the "Run" icon below to see the output! # assigning vs copying Ist = [1, 2, 3] assigned_lst = lst copied 1st = lst.copy() # add an element Ist.append(99) Please note that the path variable in this function changes values over each iteration. You should try and use the list.copy () method to copy the best path, rather than assigning it to a variable. Click on the "Run" icon below to see the output! # assigning vs copying ist = [1, 2, 3] assigned_lst = lst copied_lst = lst.copy () # add an element ist.append(99) print(assigned, lst) print(copied ist) As you can see, the assigned_lst has 99 appended to it, whereas copied_lst does not. Part 2 Your task is to write a function brute_force which uses the generate_paths function you have implemented to return the best score possible from the best path you have found. If you have completed Question 3, then you will find the code for this function similar. The Cave The cave will be represented by an N N grid where N > 0. 1. The grid will always be passed through a parameter called matrix as a nested list of integer scores. That is, the "outer" list will be your rows whilst your "inner" lists will be your columns. 2. Eve will always be placed at the entrance located in the top-left cell at coordinate (0,0) and should aim to reach the goal which is always located in the bottom-right cell at coordinate (N-1, N - 1) through a sequence of actions. 3. Whilst the cave entrance is always neutral (o score), the goal may have a treasure or trap on it. 4. Eve will always travel from the cave entrance to the goal for each question. Consider the following 5 x 5 grid below: Path 1 -150 so good -1000 18 +1000 A 150 - 150 = 0 +150 Path 2 Figure 1: 5x5 Grid The grid will have an entrance at (0,0) and goal at (4,4), with the 2D (matrix) input represented as: [[0, -1000, 0, 0, 0], [0, 0, 150, 0, -1000], To, -1000, 1000, -1090, 0], [-1000, 1000, -1000, -150, 0], [1000, 150, 0, 0, -15011 Moves As Eve is a turtle, she is only able to move closer towards the goal and never further away from it. Therefore, the list of possible moves for Eve is always limited to: Right (East) Down (South) Diagonally-Right-Down (South-East) . Overview This question is broken down into 2 stages. 1. Complete the provided generate_paths (matrix) function that iterates all legal paths using a depth-first search (DFS). The function is pretty much complete, and there are a couple of sections where students will need to "add" or "adjust" code. 2. Write a function brute_force (matrix) that takes in the same grid as Q1, and returns the maximum possible score achievable with the optimal path as an integer. Part 1 The provided generate_paths (matrix) function only prints all the paths found and returns None. Your task is to change the function code in two locations by: 1. Replacing the print (path) with code that will add or assign the path to a variable so you can keep track of it. 2. Return all your paths so you can use them in the next function (brute_force) You are free to alter the function, including adding/initializing your own variables. Additionally, there will be a generate_next path function which Notes 1. Replacing the print(path) with code that will add or assign the path to a variable so you can keep track of it. 2. Return all your paths so you can use them in the next function (brute_force) You are free to alter the function, including adding/initializing your own variables. Additionally, there will be a generate_next_path function which students will need to implement in order for the generate_paths function to work. The locations to change your code will be marked with a # ### comment block. Please note that the path variable in this function changes values over each iteration. You should try and use the list.copy() method to copy the best path, rather than assigning it to a variable. Click on the "Run" icon below to see the output! # assigning vs copying Ist = [1, 2, 3] assigned_lst = lst copied 1st = lst.copy() # add an element Ist.append(99) Please note that the path variable in this function changes values over each iteration. You should try and use the list.copy () method to copy the best path, rather than assigning it to a variable. Click on the "Run" icon below to see the output! # assigning vs copying ist = [1, 2, 3] assigned_lst = lst copied_lst = lst.copy () # add an element ist.append(99) print(assigned, lst) print(copied ist) As you can see, the assigned_lst has 99 appended to it, whereas copied_lst does not. Part 2 Your task is to write a function brute_force which uses the generate_paths function you have implemented to return the best score possible from the best path you have found. If you have completed Question 3, then you will find the code for this function similar. The Cave The cave will be represented by an N N grid where N > 0. 1. The grid will always be passed through a parameter called matrix as a nested list of integer scores. That is, the "outer" list will be your rows whilst your "inner" lists will be your columns. 2. Eve will always be placed at the entrance located in the top-left cell at coordinate (0,0) and should aim to reach the goal which is always located in the bottom-right cell at coordinate (N-1, N - 1) through a sequence of actions. 3. Whilst the cave entrance is always neutral (o score), the goal may have a treasure or trap on it. 4. Eve will always travel from the cave entrance to the goal for each question. Consider the following 5 x 5 grid below: Path 1 -150 so good -1000 18 +1000 A 150 - 150 = 0 +150 Path 2 Figure 1: 5x5 Grid The grid will have an entrance at (0,0) and goal at (4,4), with the 2D (matrix) input represented as: [[0, -1000, 0, 0, 0], [0, 0, 150, 0, -1000], To, -1000, 1000, -1090, 0], [-1000, 1000, -1000, -150, 0], [1000, 150, 0, 0, -15011 Moves As Eve is a turtle, she is only able to move closer towards the goal and never further away from it. Therefore, the list of possible moves for Eve is always limited to: Right (East) Down (South) Diagonally-Right-Down (South-East)