□ ■ ■ ■ □ □ □ □ ■ ■ ■ ▿ ◃ ◃ * ■ ■ ■ □ □ □ □ □ □ ■ □ ■ □ ▵ ◃ ◃ ■ ▿ ■ ▵ * * * ■ □ ■ □ ■ ■ □ ■ □ ■ □ ■ ■ ▵ ■ ▿ ■ ▵ ■ ■ * ■ □ ■ □ □ □ □ □ □ ■ □ ▹ ▹ ▵ ◃ ◃ ■ ▵ * * * □ □ ■ □ □ ■ ■ ■ ■ ■ □ ▵ ■ ■ ■ ■ ■ ▵ * ■ ■ ■ ■ ■ □ □ ■ □ □ □ ■ □ ▵ ■ ▿ ◃ ◃ ■ ▵ * ■ * * * ■ □ □ □ □ ■ □ □ □ ▵ ◃ ◃ ■ ▵ ◃ ◃ * * * ■ * * *
For this first lab, you will work individually. You should start by creating a directory for this class:
cd
mkdir cs63
cd cs63
Then clone the GitHub repository for your reading journal, replacing USERNAME with your username:
git clone git@github.swarthmore.edu:cs63-s19/journal-USERNAME.git
Then clone the GitHub repository for this lab, again use your username:
git clone git@github.swarthmore.edu:cs63-s19/lab0-USERNAME.git
If you have not done this in another class, don't remember how it
works, or somehow get stuck, check out Prof. Andy Danner's
Using git.
NOTE: Two of the files in the lab0 directory are executable: Queues.py and MazeSearch.py. You can run them as you would have in CS21, for example:
python3 Queues.pyAlternatively, because the first line of these files tells bash where to find your python3 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 now.
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:
Information about all of these and much more can be found in the python standard library reference.
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.
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.
The SearchAgent class implements a search through a Maze object and stores the results of that search. The search starts from the Maze object's start state and seeks the goal state. The start is always the top-left cell of the grid and the goal is the bottom-right cell, but both can be accessed as named fields of the Maze object.
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.
The class's search() method should implement the following general algorithm:
add start to frontier
add start to parents
while frontier not empty
get state from frontier
if state is a wall
add state to walls
else
add state to free
if state is goal
return
for each neighbor
if neighbor not in parents
add neighbor to frontier
add neighbor to parents
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.
The directory mazes/ which you copied along with the starting point code contains several examples on which you can test your MazeSearch.py program. Try out all three types of search on these mazes. The following links have some sample output, but you should run a lot more tests than these:
You must create at least one additional maze called BFS_outperforms_DFS.txt in which BFS will find a shorter path to the goal than DFS. Feel free to create as many other mazes as you'd like to help you test your search code.