James Madison University, Spring 2018 Semester
Lab24: Robots counting rooms
Background
For this lab we will program a robot that has been dropped into a grid of square rooms. The walls of each room have been painted this way: the North wall is Neon, the East wall is Eggplant, the South wall is Sandy, and the West wall is Walnut. Walls between rooms have doors in them, but walls on the edge do not. The robot knows how to:
- Check (N or E or S or W) to see if there is a door on that wall.
- Move (N or E or S or W) to go one room over in that direction.
- Do basic math and remember things; whatever you can program.
If you ask the robot to go through a wall that does not have a door, it isn't smart enough to know that it can't. So it will crash into the wall and damage itself.
Note this lab is fairly open-ended. The point is to assess both (1) your problem-solving skills and (2) how much Java you have learned. It's possible for you to spend hours on these activities, but you are not expected to do so.
Getting Started
Download the following files into your CS149/Lab24 folder:
Figure out how to compile and run the Example program. You may use the Example code as a starting point, but do not modify the other two files.
Submission: At the end of class today, or by 11:00 PM if you would like more time, submit one (the most advanced version that works) of the ActivityN.java files via Canvas.
Collaboration: You are encouraged to work with another student to complete this lab. Each of you should submit your own copy of the program. It's okay if your files are similar or identical, as long as both of your names are present at the top.
Activity 1: Simple Square
Download: Activity1.java
Suppose the robot is dropped into a square grid of rooms and starts in the north-west corner of the grid. Come up with an algorithm that the robot can use to figure out how many rooms are in the grid.
- An algorithm is a deterministic set of steps that does not require any outside information.
- Remember, your robot doesn't know how many squares there are in advance; if you refer to the size of the grid in your instructions to the robot, it won't work.
Is there any size grid for which your algorithm does not work? How about on a 1-by-1, or a 1000-by-1000?
In a 3-by-3 grid, how many times will the robot have to move through a door to run your algorithm? How about a 4-by-4? An n-by-n?
Assume that we want to save on robot fuel. Can you make an algorithm that uses fewer moves for the same size grid?
Once you have an algorithm you think is general (works for all grid sizes) and efficient (uses few moves), describe it at the top of Activity1.java by replacing the paragraph with the instructions. Don't forget to write your name(s) and today's date where indicated. Then implement as much of the algorithm as you can in the main method.
Activity 2: Simple Rectangular
Download: Activity2.java
Suppose the robot is dropped into a rectangular (not necessarily square) grid of rooms and starts in the north-west corner of the grid. Come up with an algorithm that the robot can use to figure out how many rooms are in the grid.
Ask yourself the same questions as in Part 1 to make sure you have a general and efficient algorithm. Then complete the Activity2.java file.
If your Part 1 algorithm also solves this problem as well as the Part 1 problem, you are welcome to use it again for Part 2.
Activity 3: Rectangular
Download: Activity3.java
Suppose the robot is dropped into a rectangular (not necessarily square) grid of rooms and might start in any arbitrary room in the grid. Come up with an algorithm that the robot can use to figure out how many rooms are in the grid.
Continue the same process as before to refine your algorithm. Then complete the Activity3.java file. Since the number of moves will probably depend on the starting location of the robot, just tell us the largest number you could see (assuming the robot starts in the worst possible room).
If your Part 2 algorithm also solves this problem as well as the Part 2 problem, you are welcome to use it again for Part 3.
Activity 4: Stranger Grids
Download: Activity4.java
See how general you can make your algorithm. Can you get it to work on diamond-shaped grids of rooms? Grids with more complicated outlines? Grids where some rooms are missing in the middle? Grids where some walls that should have doors don't have doors? Arbitrary mazes of rooms?
Implement the most general algorithm you can in Activity4.java. We are not looking for any particular functionality in Part 4. If you can't get any more complicated grids than in Part 3, submit Part 3 (or 2 or 1) instead, and we'll assume that's as much as you could do in the time we gave you.
Acknowledgements
This lab is based on materials developed by Luther Tychonievich, Mark Sherriff, and Ryan Layer. Adapted by Chris Mayfield and licensed under CC BY-NC-SA 3.0.