## Lab 0: State Space Search on Logic PuzzlesDue Thursday, Sept. 12 by 11:59 pm

### Starting point code

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 git@github.swarthmore.edu:cs63-f19/lab0-USER.git
```

### Introduction

The objectives of this lab are to:

• (re)acquaint you with object-oriented programming in Python
• (re)acquaint you with breadth-first search

For this lab you will:

• implement an efficient version of breadth-first search using a dictionary
• apply your search to the Water Pitcher Problem
• formulate the Missionaries and Cannibals Problem for search
• apply your search to the Missionaries and Cannibals Problem

### Python review

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.

### Review the starting point code

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.

1. queue.py implements a Queue data structure. Make sure that you understand how it works. At the bottom of the file is some test code. Execute this file (python3 queue.py) to see the test results. You will need to use a queue when implementing breadth-first search.
2. nodes.py implements a basic Node class for storing search information. You will create nodes and add them to the Queue during your search.
3. problemState.py defines an abstract class (or in other words an interface). Your search implementation will assume that all problems to be solved will inherit from this abstract class.
4. pitcher.py implements a class called PitcherState that inherits from ProblemState. Once you complete your implementation of search, you can test it on this problem.
5. searchAgent.py contains an incomplete implementation of a search agent that uses BFS to solve logic problems. You must complete this.
6. missionaries.py contains an incomplete implementation of a class called MissionaryState. You must complete this.

### Implementing searchAgent.py

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
end if
end for
end while
report failure
report number of states explored
```
If 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.

### Testing searchAgent.py

You can execute the pitcher.py file to test your search agent:

```    python3 pitcher.py
```
At 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.

### Implementing missionary.py

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.

### Testing missionary.py

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:

```    python3 missionary.py
```

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?