Overview

This question is broken down into 2 stages. 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. 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:

Replacing the print(path) with code that will add or assign the path to a variable so you can keep track of it. 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.

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.

from hidden import (apply_move, is_duplicate_move, path_coordinate_is_valid)

# Part 1 def generate_next_path(last_position, previous_position, possible_moves): #### STUDENTS TO IMPLEMENT THIS FUNCTION ##### # 1. Calculate the last move # 2. Find the next available move in possible_moves list # 3. Replace the last move by the next available move found # 4. Return the resulting turtle position return None

def generate_paths(grid): N = len(grid)

# possible moves for the x, y coordinate (right, down, diagonal-right-down) possible_moves = [(1, 0), (0, 1), (1, 1)] # path is a sequence of visited cells path = [(0, 0)] #### STUDENTS TO FILL BELOW ######## # you can add your variables here if you are making any

####################################

while True: # explore current path whilst the coordinate is valid (inside the cave) while path_coordinate_is_valid(path[-1], N): # add the next move path.append(apply_move(path[-1], possible_moves[0])) # if our current location is the goal location if path[-1] == (N, N): # then remove the last move which goes past the grid walls path.pop()

#### STUDENTS TO FILL BELOW ######## # store your current path somewhere # The placeholder code below just prints out all the paths: print(path) ####################################

# remove future moves that have already been explored while len(path) > 1 and is_duplicate_move(path[-1], path[-2]): path.pop() # if we have finished the final path, then we are done! if len(path)

# Part 2 def brute_force(matrix): # TODO: Implement this function (delete this comment when you begin)

Introduction We often use computers to discover efficient solutions to problems. Artificial Intelligence (AI) provides a range of techniques for solving a wide variety of problems. In this Project 1 (P1). you will implement two specific techniques for solving what we call a "search problem". When developing and demonstrating Al techniques, we often use "toy worlds". Toy Worlds are simplified problems for which a concise, exact definition is possible. This contrasts significantly to "real world" problems, which are much more complex and messier. The "toy world" scenario that we will use for P1 is as follows. Turtle Dungeon Crawler Lara Croft's pet turtle Eve has decided to venture into a cave to collect ancient treasure that lies therein. This cave can be represented as a two-dimensional (2D) grid, completely enclosed by the cobblestone walls. Eve arrives at the entrance of the cave (top-left) and must maximize the amount of ancient treasure collected before reaching the goal (bottom-right). Unfortunately, the cave is plagued with death traps and electrical traps, which will hurt Eve. We want to help Eve discover an efficient route from the entrance of the cave to the goal tile amd help maximize the amount of ancient treasure. Items 1. Diamonds are worth a -1000 score 2. Gold Bars are worth a +150 score 3. Yellow Electrical Traps are worth a -158 score 4. Death Traps are worth a -1000 score 5. The Cave Entrance and neutral cells (Orange) are worth a score. The Cave The cave will be represented by an N x 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 ( score), the goal may have a treasure or trap on 4. Eve will always travel from the cave entrance to the goal for each question it. 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) The diagram below visually shows all the possible directions that Eve can make when moving. Introduction We often use computers to discover efficient solutions to problems. Artificial Intelligence (AI) provides a range of techniques for solving a wide variety of problems. In this Project 1 (P1). you will implement two specific techniques for solving what we call a "search problem". When developing and demonstrating Al techniques, we often use "toy worlds". Toy Worlds are simplified problems for which a concise, exact definition is possible. This contrasts significantly to "real world" problems, which are much more complex and messier. The "toy world" scenario that we will use for P1 is as follows. Turtle Dungeon Crawler Lara Croft's pet turtle Eve has decided to venture into a cave to collect ancient treasure that lies therein. This cave can be represented as a two-dimensional (2D) grid, completely enclosed by the cobblestone walls. Eve arrives at the entrance of the cave (top-left) and must maximize the amount of ancient treasure collected before reaching the goal (bottom-right). Unfortunately, the cave is plagued with death traps and electrical traps, which will hurt Eve. We want to help Eve discover an efficient route from the entrance of the cave to the goal tile amd help maximize the amount of ancient treasure. Items 1. Diamonds are worth a -1000 score 2. Gold Bars are worth a +150 score 3. Yellow Electrical Traps are worth a -158 score 4. Death Traps are worth a -1000 score 5. The Cave Entrance and neutral cells (Orange) are worth a score. The Cave The cave will be represented by an N x 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 ( score), the goal may have a treasure or trap on 4. Eve will always travel from the cave entrance to the goal for each question it. 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) The diagram below visually shows all the possible directions that Eve can make when moving