Lab 2 - Hashing States

Many environments have the property that there are several paths that lead to the same state.

1. Which of the search algorithms that we covered in class benefit from detecting repeated states? For each algorithm give a short explanation how detecting repeated states makes it better.
2. Which data structure is typically used for detecting repeated states and why?
3. Download the material below, implement a hash function for State objects that passes all the tests.
4. Comment on the results you get. Are they good or bad? How would they influence the efficiency and effectiveness of detecting repeated states if your hash function was used?
5. If the results are bad try to improve your hash function. If you only get very few collisions, increase the number of states that are generated in Main.java to 10000 or 100000 and see what happens.

• java project for the lab

The project contains a State class that could be thought of implementing a state of some robot. The state consists of a position, an orientation and a boolean holding the information of whether or not the robot is turned on. The project also contains code to test how good the hashCode() method of the State class is. To run the tests simply run the Main class or use “ant run” on the terminal.

• You need to implement the methods int hashCode() and boolean equals(Object o) in classes State and Position appropriately.
• For two states s1 and s2 that you'd consider the same, s1.equals(s2) must return true and false otherwise.
• For any two objects o1 and o2, if o1.equals(o2) then o1.hashCode() == o2.hashCode() must be true!
• Objects that are not equal are allowed have the same hash code. However, if that happens too often then hash maps become very inefficient.

As with all the labs, you can work in groups of up to 4 students.

Hand in a zip file containing:

• the answers to the questions above (in a text/pdf/word file)
• your source code (ideally just the whole project directory)

To create the zip file you can just edit the “student” property in the build.xml and call the “zip” target using ant (execute “ant zip” in the directory containing the build.xml).