For this first lab, you will work individually.
First change into your directory for this class. Then clone the GitHub repository for lab0, replacing USER with your username:
cd cs63 git clone email@example.com:cs63-f19/lab0-USER.git
The objectives of this lab are to:
For this lab you will:
If you skipped cs21, or it has been awhile since you have programmed in Python, then I recommend that you begin with this Python tutorial.
Your lab0 repo should contain six files. Read through and familiarize yourself with each file. You do not need to implement any functionality in the first four files, however feel free to add your own test cases to them. Details on what you need to implement in the last two files are provided in the next sections.
Open the file searchAgent.py and complete the implementation of the class definition. You'll need to write the constructor, a search method, and a helper method for building up the path to the solution. The comments within each method provide guidance about how to proceed. You're welcome to create additional helper methods as needed.
In particular, the method executeSearch() should implement the following algorithm:
while queue not empty remove node from queue if state in node equals the goal state build the path display the path, and total number of steps taken return end if apply the operators to get all valid successors for each successor if key of successor is not in unique states dictionary add key of successor to dictionary create a node for the successor add node to queue end if end for end while report failure report number of states exploredIf the search terminates because the goal was found, then the problem is solved; if the while loop terminates because of an empty queue, then problem is unsolvable.
You can execute the pitcher.py file to test your search agent:
python3 pitcher.pyAt the bottom of pitcher.py file, two test cases have been provided. The first test case is solvable, and is the one we did in class. It can be accomplished in seven steps. The second test case is unsolvable. Ensure that your search agent produces the appropriate output for these two test cases.
Add at least three more test cases and verify the results. Once your are confident that your search agent is working correctly, you can move on to the next section.
Open the file missionary.py, and complete the implementation of the class definition. Notice that the MissionaryState class inherits from the abstract class ProblemState and is therefore required to provide concrete definitions for a number of methods, in a similar way to the PitcherState class. In fact, feel free to model your solution to MissionaryState on the PitcherState class. However, there is one key difference between the operators for the Missionary and Cannibals problem and the Water Pitcher problem. The operators for the Water Pitcher problem always lead to valid next states. You'll need to determine a way to recognize invalid Missionary and Cannibal states and avoid returning them as successors.
NOTE: Be careful that you do not hard code any particular number of missionaries or cannibals into your code. You can assume that for every version of the problem the boat can hold at most two people, but the numbers of missionaries and cannibals can vary.
Comment your code clearly. Explain the purpose of every class variable that you create.
At the bottom of the file missionary.py, add two test cases. The first should be the problem we discussed in class where three missionaries and three cannibals start on the left bank. This should be solvable in eleven steps. The second should be the unsolvable problem with four of each type starting on the left bank.
You can execute the missionary.py file to test whether your search agent can also find solutions to this logic puzzle:
Add some additional test cases of your own invention. Try some larger numbers. For instance, can 50 missionaries and 49 cannibals make it across the river safely?
To submit your code, use git to add, commit, and push the files that you modified.