IN PYTHON

II. Bot Saves Princess (2 pts)

Understanding the Input The first challenge we will work through is the Bot Saves Princess challenge. From the AI track, under the Bot Building Challenges subdomain, click on the green button labeled Solve Challenge. From here you will see the problem description. Read through it to make sure you understand what the challenge is requiring. Note that HackerRank assumes that you will not be entering any input from files that you create or from the keyboard. The input is all set up in a format described on the page. Look at the description of the Input Format, and the sample input. Answer the following questions:

1) In the Sample input, what does the 3 represent?

2) In the Sample input, what does the p represent?

3) What does the m represent?

4) Given this problem description, what would be the output if the input was in the following form:

5 ----p ----- --m-- ----- -----

5) The input for this challenge will be stored as an integer and a 2-dimensional list containing the characters in the grid. If we define a 2D list called grid, what is the value of this list after the data from the Sample input in the problem statement is stored in it. grid =

6) What cell in the grid is the princess trapped in?

7) Where is the bot located in the grid?

Writing the Code

Scroll down to the box labeled Current Buffer. This is the space where you will insert your code. There is a pull-down menu on the top right side of the box that allows you to choose the programming language that you will use. Choose Python 3. When you do this, the code box is populated with some starter code for you to use. This code performs the input for you and creates a 2-dimensional list representing the grid in which the princess is trapped. Your job is to write the function displayPathtoPrincess. We will be using IDLE to write and test the code. After you are convinced that your function is correct, you will paste it into the HackerRank buffer and test it there. Create a new file in IDLE and write the function to display the path to the princess. Create a main function that defines the 3x3 grid as in question 5 above. Then have the main call the displayPathtoPrincess function. Test your function with the 5x5 grid from question 4 above as well.

Testing the Code in HackerRank

Now that you have the function working correctly in IDLE, copy it (not the main, just the function) from your IDLE file and paste it into the buffer in HackerRank. Note that the function definition is already there, so you should paste in the body of the function. Click on the button at the bottom labeled Run Code. It will take a few moments to get the test started. Then a 3x3 grid will appear in the space below the code buffer. Click on the play button to execute your code. If it works correctly, you will see the bot move in the direction of the princess and save her. Show your instructor that your bot does indeed save the princess, and get a signature.

Submit the Code

In order to receive credit in HackerRank for solving this challenge, you have to submit the code. After you are convinced that your code is correct and will work for all cases covered in the project description, you can click on the Submit Code button. When you do this, your code is tested with several other inputs and you receive feedback. Click on the Submit Code button. You will see a message that your code is being tested. This may take a little while. When it is done, you can click on the Submissions tab and the View Results button. This will show the results of the test games that were run. You should see: 3/0/0 indicating that you Won 3 of the tests, Tied 0 and Lost 0. Get your instructors signature when the results are displayed.

III. Bot Saves Princess Full Knowledge (1 pt)

The Challenge. The next challenge we will work on is a variation on the first one. This one is called Bot Saves Princess - 2. Go back to the home page of HackerRank and choose the Artificial Intelligence domain. The second challenge in the Bot Building Challenges is Bot Saves Princess 2. Click on the Solve Challenge button to begin. In this challenge, the princess is placed in a random cell in the grid, and your job is to write a function to display the next move towards the princess. Read through the problem description and the Input Format and Output Format described on the page. Recall that with many AI problems, there are two different ways that the bot can interact with the environment: Full-Knowledge and Local Knowledge. In this challenge, what would it mean for the bot to have Full-Knowledge? What would it mean for the bot to have Local Knowledge?

Full-Knowledge of the Environment We will solve this challenge using the Full-Knowledge assumption first. This means that the bot is given the full grid and can figure out exactly where the princess is. Write a function called findPrincess that is given the grid, and returns the row and column of the location of the princess. The function begins with: def findPrincess(grid): # Fill in the code to find the princess return row, col To ensure that we cover all possibilities, if the princess is not found in the grid, return -1 for the row and the column. Test your code in IDLE using the following grids:

grid1 = [['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['p', '-', '-', 'm', '-'], ['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-']]

grid2 = [['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['-', 'm', '-', '-', '-']]

Next Move. Now write the function that computes the next move in the grid given the number of rows, the row and column of the bot and the grid. The first thing you can do in your function is call the findPrincess function so that you know that location of the princess. Then write the code that prints the direction of the next move towards the princess. def nextMove(n, r, c, grid): # n - number of rows and cols in the grid # r - row position of the bot # c - col position of the bot # grid the 2D array representing the game environment # Compute the next move LEFT, RIGHT, UP, or DOWN return move Test your code in IDLE using the following grids:

Input: grid1 = [['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['p', '-', '-', 'm', '-'], ['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-']] Expected Output: >>> nextMove(5,2,3,grid1) 'LEFT'

Input: grid2 = [['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['p', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['-', 'm', '-', '-', '-']] Expected Output: >>> nextMove(5,4,1,grid2) 'UP'

Test the Code in HackerRank Now that you have the functions working correctly in IDLE, copy them from your IDLE file and paste them into the buffer in HackerRank. Be sure to replace the function definition that is already there. Click on the button at the bottom labeled Run Code. It will take a few moments to get the test started. Then a 5x5 grid will appear in the space below the code buffer. Click on the play button to execute your code. If it works correctly, you will see the bot move in the direction of the princess and save her. This test runs your code repeated until the princess is saved. Show your instructor that your bot does indeed save the princess, and get a signature.

Submit the Code

Submit your code in HackerRank by clicking on the Submit Code button. This will take a few minutes beause it is testing your code on several test cases. If you refresh your browser, it might display the completed games. While you are waiting for the tests to complete, you may go on to the next part of the lab. Be sure to have a TA sign off on your submission once it is complete.

IV. Bot Saves Princess 2 Local Knowledge (2 pts)

Now lets consider that the bot only has local knowledge of the environment. Lets also assume that the bot is now saving a prince (princesses get a bad rap for being helpless in this game!) Depth First Search If the bot in the game only has local knowledge, this means that it can only see the cells directly next to itself. Suppose you have the 4x4 grid shown below. If you were going to use a Depth First Search to find the prince from the position where the bot is, complete the Depth First Search tree. You can assume that the algorithm can recognize when a cell is out of bounds, and represent it as an X in the tree. Indicate the moves that the bot would take to find the prince using this search method