□ ■ ■ ■ □ □ □ □ ■ ■ ■ ▿ ◃ ◃ * ■ ■ ■ □ □ □ □ □ □ ■ □ ■ □ ▵ ◃ ◃ ■ ▿ ■ ▵ * * * ■ □ ■ □ ■ ■ □ ■ □ ■ □ ■ ■ ▵ ■ ▿ ■ ▵ ■ ■ * ■ □ ■ □ □ □ □ □ □ ■ □ ▹ ▹ ▵ ◃ ◃ ■ ▵ * * * □ □ ■ □ □ ■ ■ ■ ■ ■ □ ▵ ■ ■ ■ ■ ■ ▵ * ■ ■ ■ ■ ■ □ □ ■ □ □ □ ■ □ ▵ ■ ▿ ◃ ◃ ■ ▵ * ■ * * * ■ □ □ □ □ ■ □ □ □ ▵ ◃ ◃ ■ ▵ ◃ ◃ * * * ■ * * *
cd mkdir cs63 cd cs63 mkdir labs cd labs git clone git@...Two of the files you just cloned are executable: Queues.py and MazeSearch.py. You can run them as you would have in CS21, for example:
python Queues.pyAlternatively, because the first line of these files tells bash where to find your python executable, you can simply run them with the path to the file, for example:
./Queues.pyHowever, these are the files you will be modifying, and they will just print error messages if you run them right away.
The objectives of this lab are to:
For this lab you will implement three variants of a queue data structure:
You will test these queues and then use them to implement three methods of uninformed search through an ASCII grid maze:
Some of these functions will be the same for all three types of queues and should therefore be implemented in the parent class. Others will differ across queue types and should be implemented by the child classes. The three types of queue differ in which item is returned by get():
For functions that you implement in _Queue, you should remove the overriding definition in the child classes. For functions implemented in the child classes, change the parent-class error message to be more informative.
When you submit Queues.py, your test_queues() function should print out explanations of each test so that a user could run the program, know what it is testing, and be convinced that it works correctly.
Two Python classes for representing a grid maze have been provided for you in the file MazeClass.py. Take a look at the MazeCell and Maze classes but do not modify them. One thing to note is the use of a set instead of a list to represent the walls. Sets are like dictionaries, but without values (only keys); they use a hash table to give O(1) lookup. See section 5.7 of the Python library docs for more information about sets.
You have been provided several .txt files containing example mazes. The maze at the top of this page is in 7x7_two_paths.txt. Before you can solve a maze, you need to read in the maze file, which means implementing the read_input() function. This function should check for valid command line input in sys.argv and print an error message if the input is invalid. Valid input is a path to a maze file and a search mode: BFS, DFS, or RND, for example:
./MazeSearch.py mazes/5x5_possible.txt BFS
Given valid input, you should parse the maze file and initialize a Maze object. A maze file has the following format:
The __init__() function for the Maze class expects a number of rows, a number of columns, and a list of (row, col) pairs where walls are located. For the maze file 5x5_possible.txt, this would be:
read_input() should return the initialized Maze object as well as the mode string specifying the type of search. You can test your read_input() function by calling the display() method on the Maze object you return. See python docs 7.2 for information on how to read files in python.
add start to frontier
add start to parents
while frontier not empty and goal not found
get state from frontier
add state to walls or free
if state is free
add neighbors of state to parents
add neighbors of state to frontier
end if
end while
If the while loop terminates because the goal was found, then the maze is solved; if the loop terminates because of an empty frontier, the maze is impossible.
The search() function has no return value because all relevant information is stored in the SearchAgent class.
For example, whether the maze can be solved is checkable by whether the goal is in parents.
If the maze is solvable, a solution can be found by tracing parents backwards from the goal.
You will implement this in the path_to() function.
Our search algorithm uses four data structures:
You should decide what data structure to use for each of these and set them up in the __init__() function for the SearchAgent class.
If you come up with a particularly good test maze, please share it on the piazza forum. A small amount of extra credit will be awarded for particularly effective (catches lots of bugs) or exciting (really cool mazes) test cases.
In introductory CS classes, we often want you to reinvent programming language features to see how they work. In AI, you should try to shake off that mindset, and instead take advantage of built-in functions and data structures whenever they make your life easier. If there is a specific case where I don't want you to use a certain library, I will tell you; if you're uncertain, just ask. To that end, here are some libraries that I found helpful when implementing this lab:
Information about all of these and much more can be found in the python standard library reference.
If your only previous experience with python comes from CS 21, you may not have encountered many of the coolest features of the language. Some features you might want to look into (though not necessarily required this week) are map, filter, and lambda expressions. One advanced feature that should be useful right away is the list comprehension. There is an example of a list comprehension in line 52 of the MazeClass.py starter code. There is a better introductory example and much more information about list comprehensions here: https://docs.python.org/2/tutorial/datastructures.html#list-comprehensions.
cd ~/cs63/labs/lab00-username git add Queues.py MazeSearch.py git commit git push