Lara Croft’s pet turtle Eve has decided to venture into a cave to collect ancient treasure that lies therein. PDF

Preview

Summary

Assignment 1 requires student to apply for loop and while loop to determine the best approach for a matrix-based question....

Description

DATA0006 Data Analytics with Python Spring Term, 2021 Assignment 1: Turtle Dungeon Crawler

Preamble As per the practice project, things to look out for in solving the questions are: • Make sure to , but never be afraid to create extra functions of your own, e.g. to break up the code into conceptual sub-parts, or avoid redundancy in your code • Commenting of code is one thing that you will be marked on; get some practice writing comments in your code, focusing on: –

when they are first defined (but not things like index variables in for loops)

–

(i.e. not every line, but chunks of code that perform a particular operation, such as #find the maximum value in the list or #count the number of vowels

–

, including what its arguments are, and what it returns.

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 AI 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 before reaching the goal (bottom-right).

collected

Unfortunately, the cave is plagued with death traps and electrical traps, which will hurt Eve. We want to help Eve discover an the amount of ancient treasure.

from the entrance of the cave to the goal tile amd help maximize

Items 1. Diamonds are worth a +1000 score 2. Gold Bars are worth a +150 score 3. Yellow Electrical Traps are worth a -150 score 4. Death Traps are worth a -1000 score 5. The Cave Entrance and neutral cells (Orange) are worth a 0 score.

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 is, the ”outer” list will be your rows whilst your ”inner” lists will be your columns.

. That

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 (0 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×5 grid below:

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], [0, -1000, 1000, -1000, 0], [-1000, 1000, -1000, -150, 0], [1000, 150, 0, 0, -150]]

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.

Figure 2: Possible moves at coordinate (1, 1)

Overview of Project questions Overview The overall problem to solve is to identify a safe path through an arbitrary cave that will enable Eve to collect all of the ancient treasure. We will break this down into several tasks: 1. The ”Dream Score” (find the maximum possible score obtainable) 2. Checking whether a given path is a valid solution to the problem 3. The Greedy Path (best move at the current coordinate) 4. Depth First Search using Brute Force Approaches (best path by looking at all possible paths)

Marks Your questions will be graded based on: • The (2) and ”mark” against assess test cases.

(2) passed. Note, that you will be unable to

• The approach to the problem (i.e was your code too simple, overly-complicated, or excellent) • PEP8 (make sure your output follows PEP8 standard and good variable names) • Commenting (make sure you add comments and a docstring, you can visit Worksheet 10 for more tips) The questions sum to a total of 30 marks worth 50% of this subject: • Question 1: 6 marks

• Question 2: 8 marks • Question 3: 8 marks • Question 4: 8 marks

Final Tips • All the questions are independent of each other, so you do not need to complete them in order to do the next question! • This project is on the difficult side, so please allow ample time for completion! • Use pen/paper to plan out your code and grids (especially for question 3). • You can make your own grids and check if your function is returning the correct output. To do so, add a print statement at the very end of your program with your own grid input and click ”Run”. • Programming is Fun!

Questions Question 1: The ”Dream Score” Write a function dream score(matrix) that takes in a list of lists, and returns the maximum possible score as an integer. You may assume the following: • The turtle can ”teleport” to any cell. • Each cell can only be visited ”once”. • You do not need to visit each cell (such as traps). • There may be an item or trap on the goal. Please note that the above assumptions 1 - 3 are solely relevant to this particular task only. Assumption 4 will be present throughout all the questions. Eve will always travel from the cave entrance to the goal, so items or traps on the goal (assumption 4) must still be taken into account. The parameters to this function are as follows: • matrix is a list of lists, where the ”outer lists” denote rows and ”inner lists” denote columns. Each cell is given an denoting the ” ” in the cell. Input Assumptions: • You can assume that the input arguments are syntactically correct given the definitions, and will always be non-empty (i.e a minimum grid size of 1×1). Here are example calls to your function: d r ea m s c or e ( [ [ 0 , −1000 , 0 , 0 , 0 ] , [ 0 , 0 , 1 5 0 , 0 , −1000] , [ 0 , −1000 , 1 0 0 0 , − 1000 , 0 ] , [ −10 00 , 1 0 0 0 , −1000 , −150 , 0 ] , [1000 , 150 , 0 , 0 , −150]]) >>> 3150 d r ea m s c or e ( [ [ 0 , 1 5 0 , 1 5 0 , 1 5 0 ] , [ 1 5 0 , 1 5 0 , 1 5 0 , 1 5 0 ] , [150 , 150 , 150 , 150] , [150 , 150 , 150 , 1 5 0 ] ] ) >>> 2250 d r ea m s c or e ( [ [ 0 , 0 , 0 ] , [ 0 , −1000 , 0 ] , [ −15 0 , 0 , 0 ] ] ) >>> 0

Question 2: Valid Path Write a function valid path(n, path) that takes in the size of the grid and a travel path, and returns True if the path is valid and False if the path is invalid. A path is only valid when Eve ends at the goal coordinate (N−1,N−1) and the path conists of only legal moves between coordinates. Remember that coordinates must be inside the grid and legal moves are 1 unit: Right (East), Down (South), Diagonal-Right-Down (South-East). The parameters to this function are as follows: • N is the dimension of the grid. For example, if N = 2, then the size of the grid is 2×2 with a goal at coordinate (1,1). • path is a list of coordinates represented in tuples, starting with (0, 0). Input Assumptions: • You can assume that the input arguments are syntactically correct given the definitions, and will always be non-empty. • The path will always begin at the entrance coordinate (0,0), but it may not necessarily end at the goal node. Here are example calls to your function: valid path (2 , [ ( 0 , 0) , (1 , 1 ) ] ) >>> Tr u e valid path (4 , [ ( 0 ,0) ,( 0 ,1) ,( 0 ,2) ,( 1 ,2) , (2 ,3) ,(3 ,3)]) >>> Tr u e valid path (4 , [ ( 0 ,0) ,( 1 ,0) ,( 0 ,0) , (0 ,1) ,(0 ,2) ,(1 ,2) ,(2 ,3) ,(3 ,3)]) >>> F a l s e valid path (4 , [ ( 0 ,0) , ( 0 ,1) , ( 0 ,2) ] ) >>> F a l s e

Question 3: Greedy Approaches Greedy Algorithms Your next problem is to identify a valid path based on a greedy algorithm called ”Best First Search”. So what is a greedy algorithm? • A greedy algorithm makes the best choice possible from its current state (coordinate), without consideration of consequences that occur later on.

In the above animation (if it doesn’t work, please check it [HERE]), the greedy algorithm, whose task is to find the path of the largest sum, looks at its current options and chooses what appears to be the best choice (7→12→6=25). However, you can see that the end result is actually not the ”best” path (7→3→99=109). ”Best First Search” in a Toy World Question 3 will be about generating the best possible path by picking the best ”move” at its current state (also known as choosing the ”locally optimal” path). This strategy you will implement is called ”Best First Search”. At each coordinate, Eve will have at most 3 moves to choose from. Eve should then always pick the move that yields the best score. Consider the grid below:

The following possible moves will be: 1. Go Right (East) to (2,1) for a Diamond worth +1000 score. 2. Go Down (South) to (1,2) to a Neutral Cell. 3. Go Diagonal-Right-Down (South-East) to (2,2) for a Death Trap worth -1000 score. Eve will then choose Option Number 1 as it is the current ”best” choice (locally optimal choice).

Tie Breakers Consider a scenario where all the possible moves Eve can make are onto Neutral Cells, which means that whichever move Eve decides to take results in the same outcome. For these scenarios, Eve will always have a preference: 1. Right (East) is always preferred if legal 2. Down (South) is next preferred if legal 3. Diagonal-Right-Down (South-East) is the lowest preference if legal For example, if Eve was at the Cave Entrance, the following possible moves might be: 1. Go Right (East) to (1,0) to a Neutral Cell. 2. Go Down (South) to (0,1) to a Neutral Cell. 3. Go Diagonal-Right-Down (South-East) to a Neutral Cell. Since these are all tie-breakers, Eve will prefer to go Right (East).

The Greedy Path Write a function greedy path(matrix) that takes in the same grid as Q1, and returns: 1. The locally optimal path using a ”Best First Search” strategy as a list of tuples (coordinates). 2. The total score as an integer. Your function should return the above the result as a tuple in form (path, score). The parameters to this function are as follows: • matrix is a list of lists, where the ”outer lists” denote rows and ”inner lists” denote columns. Each cell is given an integer value denoting the ”score” in the cell. Note, that you are encouraged to make any additional helper function(s) to make your code become readable and neat (as there are marks awarded to this criteria). We also strongly suggest you draw out the grid and ”mimic” a Best First Search before you write the code prior to implementing. Here’s an example call to your function: gr eedy pa th ( [ [ 0 , 0 , − 1 5 0 , 0 ] , [ 0 , 1 0 0 0 , 0 , 0 ] , [ −1000 ,0 , −1000 ,0] ,[0 ,0 ,150 ,0]]) >>> ( [ ( 0 , 0 ) , ( 1 , 1 ) , ( 2 , 1 ) , ( 3 , 1 ) , ( 3 , 2 ) , ( 3 , 3 ) ] , 1 0 0 0 ) g r e e d y p a t h ( [ [ 0 , −1000 , 1 5 0 , 1 5 0 , 1 5 0 ] , [ 1 0 0 0 , 0 , 0 , −150 , 1 5 0 ] , [ 0 , −1000 , 0 , 0 , 1 5 0 ] , [ 0 , −1000 , − 1000 , −1000 , 1 5 0 ] , [1000 , 1000 , 1000 , 1000 , 0 ] ] ) >>> ( [ ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 1 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 3 , 2 ) , ( 4 , 2 ) , ( 4 , 3 ) , ( 4 , 4 ) ] , 130 0) g r e e d y p a t h ( [ [ 0 , 1 0 0 0 , −1000 , 0 , 1 5 0 , 1 5 0 , 1 5 0 ] , [ 1 0 0 0 , 1 0 0 0 , −1000 , 0 , −150 , − 150 , −150] , [ 1 0 0 0 , −1000 , −1000 , 0 , 0 , 0 , 0 ] , [ 1 0 0 0 , −1000 , 0 , 0 , 0 , 0 , 0 ] , [ 1 0 0 0 , −1000 , 0 , 0 , 0 , 0 , 0 ] , [ 1 0 0 0 , −1000 , 0 , 0 , 0 , 0 , 0 ] , [1 0 00 , 1000 , 1000 , 1000 , 1000 , 1000 , −150]]) >>> ( [ ( 0 , 0 ) , ( 1 , 0 ) , ( 1 , 1 ) , ( 2 , 1 ) , ( 3 , 1 ) , ( 3 , 2 ) , ( 4 , 2 ) , ( 5 , 2 ) , ( 6 , 2 ) , ( 6 , 3 ) , ( 6 , 4 ) , ( 6 , 5 ) , ( 6 , 6 ) ] , 850)

Question 4: Brute Force Approaches Brute Force Approaches So what is brute force? • A brute force algorithm makes the best choice possible after exhausting all possible options. A real-life application of a Brute Force strategy is password cracking, where one can simply try all possible password combinations until a solution is found. You will be using a Brute Force strategy called ”Depth First Search” (DFS) for this question. ”Depth First Search” in a Toy World The way Depth First Search works is that it searches all the way down one path (i.e from the Cave Entrance to the goal) before going back and looking at the next possible path. Here’s an example of a Depth First Search (DFS) in action using a Brute Force approach (see BF.gif if the embedded animation doesn’t work):

In the above animation, you can see the DFS tries every possible value by going all the way down and trying the next path. Finally, DFS picks the path 0→3→11=14. The Question 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 Please see ”program.py” 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 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. # a s s i g n i n g vs copy in g l s t = [1 , 2 , 3] assigned lst = l s t c o p i e d l s t = l s t . c op y ( ) # a dd an e l e m e n t l s t . a p p end ( 9 9 ) print ( a ssigned lst ) print ( copied lst ) 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. Complete your Question 4 here. If you are unsure as to how this works, please go back to the Grok Slide ”Question 4 Introduction”. Here are example calls to your function: br ute for ce ( [ [ 0 , 0 , 0 , 0] , [0 , 0 , 0 , 0] , [0 , 0 , 0 , 0] , [ 0 , 0 , 0 , −1000]]) >>> −1000 b r u t e f or c e ( [ [ 0 , −150 , 1 0 0 0 , 0 , 0 , 0 ] , [ 1 5 0 , −1000 , 0 , 0 , 0 , 0 ] , [ 0 , −1000 , 0 , 0 , 0 , 0 ] , [ 0 , −1000 , 1 0 0 0 , 0 , 0 , 0 ] , [ 0 , −1000 , −1000 , − 1000 , 0 , 0 ] , [0 , 0 , 0 , 0 , 0 , 0 ]]) >>> 1850 br ute for ce ([[0 , −1000 ,0 ,0 ,0] ,[0 ,0 ,150 ,0 , −1000] , [ 0 , − 1 0 0 0 , 1 00 0 , − 1 0 0 0 , 0 ] , [ − 1 0 0 0 , 1 0 00 , − 1 0 0 0 , − 1 5 0 , 0 ] , [1000 ,150 ,0 ,0 , −150]]) >>> 1000...