SUNY Geneseo, Department of Computer Science

Lab 4

CSci 141 , Fall 2003

Prof. Doug Baldwin

Due Wednesday, September 24

Purpose

This lab is intended to help you begin inventing and coding recursive algorithms on your own. It does this by asking you to write a series of recursive algorithms in Java.

Background

In this lab you will write a set of recursive algorithms, some for the software robots we have used in past labs, and some simple numeric algorithms.

You can find Documentation on the Robot on the Web, at http://www.cs.geneseo.edu/~baldwin/sc/doc/ You can find the code for the robot classes in our folder on the "Course Materials" file server.

Defining Your Own Robot Rooms

Many of the algorithms you will write for this lab involve robots somehow interacting with red tiles. In order to test these algorithms you will have to put the robots in rooms that contain red tiles. Since the default robot room doesn't contain any red tiles, you will have to define your own robot rooms.

Robot rooms are objects of class RobotRoom, and you can create them much like you create any other object. One of the constructors for RobotRoom takes a string parameter that describes the room you want. (The reason for this apparently bizarre and complicated parameter is that it makes it easy to read room descriptions from files or even interactively from users.) The string should begin with two numbers, which are the width and height of the room, in tiles. Then there should be any number of descriptions of colored tiles -- each description consists of the column in which the tile lies (a number), the row (another number), and a one-character code for its color. Legal characters are "R", "G", "B", or "Y", for red, green, blue, and yellow, respectively. Every item in this description should be separated from its neighbors by one or more spaces. Note that column and row numbers start at 0, and range up to one less than the width or height of the room (i.e., they work just like array indices in Java). Every room has a wall around it that occupies the top and bottom rows, and left and right columns. Don't forget to include this wall when you figure out your room's width and height.

For example, to create a room that is 3 tiles wide by 10 high, with a red tile 1 row below the top wall in the middle column, I would say

    RobotRoom room = new RobotRoom( "3 10 1 2 R" );

3 and 10 are the width and height of the room; the "1 2 R" part of the string calls for a red tile ("R") in the middle column (column 1, since column numbers start at 0) and with one row between it and the top wall (the wall is row 0, the empty row is row 1, and so the red tile is in row 2). The resulting room looks like this:

Once you have a room, you have to put a robot in it (rooms don't automatically come with robots). To do this, use the constructor for robots that lets you specify a robot's column, row, initial heading, and room. For example, to put a robot facing up (north) at the bottom of the room created above, I could say

    Robot robbie = new Robot( 1, 8, Robot.NORTH, room );

Note that row 8 is the lowest row a robot can occupy in this room, because the 10 rows are numbered 0 through 9, and row 9 contains the bottom wall. The result of the above statement looks like this:

The online Documentation for classes Robot and RobotRoom says more about these constructors.

Defining Constructors

The example above assumes that you want to put an ordinary robot into your own room. Unfortunately, in this lab you will need to put instances of your own subclass of Robot into rooms. This in turn means that your subclass will need a constructor analogous to the Robot constructor used above (i.e., a constructor that takes the robot's column, row, heading, and room as parameters). This constructor is much easier to write than you may expect, but you do need to write it.

The basic problem is that to create one of your own robots and position it in your own room, you will need to write code of the form

    RedRobot robbie = new RedRobot( 1, 8, Robot.NORTH, room );

(I have assumed that your subclass is called RedRobot, and that you want to position the new RedRobot exactly as in the example that created an ordinary robot.) This code needs the new RedRobot(...) part in order to create an instance of your subclass, but that syntax also says to call a constructor named RedRobot with four parameters, and no such constructor exists unless and until you define it.

Somewhat annoyingly, the RedRobot constructor that you need in the above example really just needs to call the four-parameter Robot constructor, and you would think Java compilers could figure out how to do this for you. But they can't. However, Java does let you write constructors that call their superclass's constructor. To do this, make the first line of the constructor a call to the special "constructor" super, with parameters appropriate for the superclass constructor you want to use. Thus, the constructor for RedRobot that the example needs could be written as just

    // In class RedRobot...
    public RedRobot( int width, int height, int heading, RobotRoom    room ) {
        super( width, height, heading, room );
    }

Subclasses of Robot that you write for this lab will almost certainly need such a constructor.

For more on the use of super as a constructor, see Appendix section 1.4.5 in The Science of Computing.

Exercise

Design and code in Java recursive methods that solve each of the problems described below. The first three problems involve robots, and you should code the solutions to those problems as methods of a subclass of Robot. The fourth problem can be coded as a static method in your main class.

Problem 1 -- Find a Red Tile

Design and code a recursive algorithm that causes a robot to move forward until it is standing on a red tile. If the robot is initially standing on a red tile, it should not move at all. You may assume as a precondition that there is at least one red tile between the robot and whatever wall it is facing ('though the red tile may be at the robot's initial position).

Note that to test this method, you will need to define rooms containing red tiles between the robot and the wall. To do this, you will need to know about Defining Rooms, as discussed in the "Background" section above, and you will also need to write a Constructor for your subclass that passes its parameters on to the constructor for Robot.

Problem 2 -- Red Diagonal

Design and code a recursive algorithm that makes a robot draw a diagonal red line n steps long, where n is a parameter to your algorithm. You may assume as a precondition that n >= 0, and that the robot is initially standing where the lower left tile of the line will be, facing north.

For example, here is a robot that has just drawn a 4-step diagonal. The robot started in the lower left corner of its room.

Problem 3 -- Counting Red Tiles

Design and code a recursive algorithm that moves a robot forward until it comes to a wall, and returns the number of red tiles that the robot encounters on the way, including any red tile that the robot starts on, and any that is next to the wall.

Remember that "return" in a context such as this is a technical programming term that means deliver a value back to the client that sent the message -- "return" does not mean "print."

Problem 4 -- Squaring

Design and code a recursive algorithm that computes n², where n is an integer parameter to your algorithm. Your recursion should be based on the fact that, when n > 0, n² = (n-1)² + 2n - 1. When n = 0, n² = 0 too. You may assume as a precondition that n >= 0.

The simplest way to write this algorithm in Java is as a static method of your main class. There is no point in defining a whole new class just to do this one computation.

Follow-Up