Firm understanding of chapter 6 of Algorithms and Data Structures: The Science of Computing.
This exercise revolves around an algorithm for the robots introduced in chapter 2 of Algorithms and Data Structures: The Science of Computing. The algorithm directs a robot along a turning, possibly branching, path in its room. The robot follows the path by interpreting the colors of tiles it encounters as signals that the path turns, splits, etc. The “Exercise” section of this document explains this problem and the interpretation of tile colors in detail. To make it easier to create rooms that test this algorithm, we provide a number of files containing pre-defined room descriptions. Reading room descriptions from these files requires using Java’s file input mechanisms.
The robot is available as a Java class named Robot (and a supporting
class named RobotRoom). Programs that use these classes need to
include two Java files: Robot.java and RobotRoom.java. The “Final
Details” section of this document explains how to find these files
and their documentation.
Any Java source file that refers to the Robot or RobotRoom classes
should “import” those classes, via the statement
import geneseo.cs.sc.*;at the beginning of the file.
A constructor is basically a method that initializes a new object (see Sections
3.4.2 and A.4.4 of Algorithms and Data Structures: The Science of Computing).
In Java, constructors have the same name as the class they initialize — for
example, the constructors for Robot objects are named Robot,
the constructors for instances of a hypothetical ExtendedRobot subclass
of Robot would be named ExtendedRobot, and so forth.
Note that subclasses don’t inherit constructors from their superclass
the way they inherit other methods — for example, even if a constructor
for Robot logically does everything necessary to initialize instances
of an ExtendedRobot subclass, there is no way to automatically
apply this constructor to ExtendedRobot objects.
Even though Java doesn’t do it automatically, one often wants to initialize
instances of a subclass by just calling a superclass’s constructor. This
will probably be the case for the subclass of Robot defined in
this exercise. To do this, define constructors for the subclass that do nothing
but call the corresponding superclass constructor. Within a constructor, the
word super can be used to call a superclass constructor. For example,
to allow instances of an ExtendedRobot subclass of Robot to
be initialized with their position, heading, and room (just like the four-parameter
constructor for Robot does), include the following constructor
in ExtendedRobot:
// Within the ExtendedRobot class...
public ExtendedRobot( int column, int row, int heading, RobotRoom room ) {
super( column, row, heading, room );
}A statement such as the following implicitly uses this constructor to initialize an extended robot:
ExtendedRobot r = new ExtendedRobot( 1, 3, Robot.NORTH, myRoom );A complete explanation of how to read text files in Java is beyond the scope of this document, although a short review of a simple approach is appropriate. For a more detailed discussion of text input in Java, a guide to Text Input and Output in Java is available on the Web at http://cs.geneseo.edu/~baldwin/reference/java-textio.html. Keep in mind that the summary below is a short review, which emphasizes simplicity over flexibility. There are other ways of doing almost every step shown:
Five things must be done in order to read text from a file:
BufferedReader that will deliver
data from the file to the program.As an example, here is a Java program that opens a file named “textfile.txt”, reads one line from it, prints that line, and then closes the file and stops:
import java.io.*;
class InputDemo {
public static void main( String[] args ) throws Exception {
BufferedReader in = new BufferedReader( new FileReader( "textfile.txt" ) );
String text = in.readLine();
System.out.println( text );
in.close();
}
}This program handles exceptions by propagating them to whatever called main (the
phrase throws
Exception in the declaration for main asserts that main may
propagate exceptions to its caller). The first line of main creates
the BufferedReader for file “textfile.txt”;
the second line reads a line of text from it; the third line prints that text;
the fourth line closes the file.
Children sometimes play a “treasure
hunt” game, in which players receive clues that guide them to other clues,
until eventually the last clue leads them to a “treasure.” For
example, at the beginning of the game the players might receive a slip of paper
that
says “go to the big oak tree,” at the oak tree they might find
another slip of paper that says “try swimming,” so they go to
the swimming pool to look for a third clue, and so forth. The basic job in
this exercise is to define a subclass of Robot that can carry out a similar
treasure hunt.
Robots can’t read slips of paper, so the “clues” for a robot treasure hunt are represented by the colors of tiles. Furthermore, robots aren’t smart enough to think of (or find) oak trees or swimming pools, so every clue in a robot treasure hunt just requires a robot to move one tile in some direction. After doing so, the robot examines the color of the tile it is then standing on to figure out where to go next, and so forth.
Here are the specific rules for interpreting tile colors as clues:
A collection of files that provide descriptions of robot
rooms laid out for treasure hunts is available to help test hunt algorithms.
Each file simply contains one line of text, which is a string describing
the
room. These strings can be used as parameters to the one-parameter constructor
for RobotRoom. Each room is 17 tiles by 17 tiles, and the clues
assume that the robot will start in column 8, row 15 (i.e., the center of the
bottom edge
of
the
room),
facing north.
The available files include…
See the “Final Details” section of this document for details on where to find these files.
Define a subclass of Robot that has a hunt message
that makes a robot carry out a treasure hunt. This message
has no parameters, but returns the number of times the robot reaches treasure
(yellow tiles) during the treasure hunt. There may be more
than one
treasure in a treasure hunt,
since
red tiles
allow
treasure
hunts to fork into multiple parts. It’s also possible for multiple paths
to end at the same treasure, so the number of times a robot reaches treasure
may be more than the number of distinct yellow tiles in the treasure hunt.
Assume as a precondition for hunt that the robot is standing
on the first clue of the
treasure
hunt,
facing “in” to
the treasure hunt (i.e., the direction in which it should continue moving when
on a white
tile, turn left relative to when on a blue tile, etc.) Further assume that
the clues in the treasure hunt will never steer the robot into a wall.
Postconditions for hunt are that the returned value is the number
of treasures in that treasure hunt, and the robot has returned
to the tile it started
on. You may adopt additional postconditions if you wish.
In addition to designing and coding the hunt algorithm, prove
that the algorithm establishes the postconditions given earlier, and any other
postconditions you added.
Finally, write a main program
that exercises the treasure-hunting subclass. This program should be able
to read room descriptions from files such as those described under “Sample
Treasure Hunts,” and create rooms in which to hunt for treasures
from the descriptions. Don’t assume that the provided files will test
hunt to complete perfection; create additional test files to exercise the algorithm
further.
The sample treasure hunts can be downloaded from the Web through the following links:
Both Robot.java and RobotRoom.java can be downloaded from the Web.
Documentation on both classes is also available on the Web. The main documentation page is an index to documentation for all the Java classes written for use with Algorithms and Data Structures: The Science of Computing. To see the documentation for a specific class, click on that class’s name in the left-hand panel of the page.
I will grade this assignment through face-to-face meetings with you. You should complete work on the project by Monday, March 29, and hold your grading appointment no later than Thursday, April 1.
Grading appointments should be half an hour long. Come
to your grading appointment prepared to show me your hunt method
and main program, running if possible (i.e., bring the code on a laptop computer,
or set it up in a lab and hold the appointment there, etc). Also bring your
proof that hunt is correct, either on a separate sheet of paper or as comments
in your program.
Copyright © 2004. Charles River Media. All rights reserved.
Revised Mar. 17, 2004