Counting Squares

Assignment Info

Summary: Teaching the basics of algorithm design without using much programing.
Topics: Learning how to write algorithms.
Audience: Beginning programmers. We use this in CS1 and with middle-school programming camps.
Difficulty: Easy.
Strengths: Good visualizations, gets students involved and interested. Works very well as a guided activity or lab.
Weakensses: Could be overly simple depending on the group.
Dependencies: None.
Varients: Add in more complexity to the rooms to use it later in a course or even in an upper-level course.

Grid of doors

For this lab we will be programming a robot that has been dropped into a grid of square rooms. Each wall of each room has been painted a different color: the North wall is Neon, the East wall is Eggplant, the South wall is Sandy, and the West wall is Wallnut. Walls between rooms have doors in them, but walls on the edge do not. All of the doors are closed initially.

The robot knows how to

• Check N (or Check E, or S, or W) to see if there is a door on that wall of its current room;
• Go N (or E or S or W) to move one room over; and
• Do basic math and remember numbers.

If you ask it to Go through a wall that does not have a door, it isn’t smart enough to know it can’t so it will walk into the wall and damage itself.

We won’t be super formal in this lab. If we can tell what you are asking the robot to do, that’s good enough for us.

Activity 1: Simple Square

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 size squares) and efficient (uses few moves), submit it as Part 1. Include a simple statement about how many moves it takes, on an n-by-n grid the robot moves through 2n+5 doors or something like that.

Activity 2: Simple Rectangular

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.

Submit an algorithm for this case as Part 2, including a description of the number of moves needed for an n-by-m grid.

If your Part 1 algorithm also solves this problem as well as the Part 1 problem, you are welcome to submit it again for Part 2.

Activity 3: Rectangular

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.

Submit an algorithm for this case as Part 3, including a description of the number of number of moves your robot will make for an n-by-m grid. Since this will probably depend on the starting location of the robot, just tell us the biggest number you could see (assuming the robot started 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 submit it again for Part 3.

Activity 4: Stranger Grids

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?

Submit the most general algorithm you can come up with as Part 4. At the beginning of the submission, include a description of the kinds of grids you think it can handle.

We are not looking for any particular functionality in Part 4; if you can’t get any more complicated grids than Part 3 did, submit Part 3 and tell us it’s as much as you could do in the time we gave you.

Optional Lab Component

If you wish to test some of the algorithms with the class, we wrote code that simulates the robot’s motion through the grid.

Python:

This code requires that PyGame has been installed - PyGame Install

• gamebox.py - Library that sits on top of PyGame, making it a bit easier to used. Written by Tychonievich.
• zombiegrid.py - Driver code for rectangualr grids and an animated zombie characer
• Monster-zombie.png - Zombie graphics, needed by zombiegrid.py
• example.py - An example of how to use zombiegrid. We have the instructor open this file and entr the students' algorithm suggestions. The zombie then tries them out.

Java

• DoorRoom.java - Code that defines the grid of rooms. You never need to use this class explicitly; it is invoked by the Robot.
• Robot.java - The Robot class. Can be created with rectangular grids or with arbitrary grids with some missing rooms. See the JavaDoc comments or ExampleRoom.java for more.
• ExampleRoom.java - An example of how you use the Robot class to demonstrate an algorithm.
• MazeSolverSolution.java - An example of a solution using ArrayList<String> to count the cells in arbitrary mazes.