Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
This exercise consolidates understanding of recursion through the design and implementation of a relatively large and sophisticated recursive algorithm.
Firm understanding of chapter 6 of Algorithms and Data Structures: The Science of Computing.
Understanding of inductive correctness proofs for algorithms, as described in section 7.1 of Algorithms and Data Structures: The Science of Computing. Strong induction is particularly relevant.
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 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. Keep in mind, however, that this 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 sends the BufferedReader a readLine message,
which reads one line of text from the file and returns that text as a string.
The third line
prints this string. Finally, the fourth line sends the BufferedReader a close message,
which 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 descriptions of robot
rooms laid out for treasure hunts is available to help test hunt algorithms.
Each description is in a file that 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 are…
See the “Final Details” section of this document for information on where to find these files.
Define a subclass of Robot that handles 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 times the robot reached treasure in the treasure hunt, and the robot has
returned to the tile it started
on. You may adopt additional postconditions if you wish.
After designing the hunt algorithm, prove
that the algorithm establishes the postconditions given earlier, and any other
postconditions you added.
In addition to the hunt method, the treasure-hunting subclass
of Robot needs a constructor that takes the robot’s
initial tile column, tile row, orientation, and room as parameters. This constructor
is needed in order to
create treasure
hunting robots in rooms that contain treasure hunt clues, with the robot standing
on the first tile of the treasure hunt and facing into it. This constructor
is completely analogous to the four-parameter constructor for Robot,
and doesn’t need to do anything except call that constructor.
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.
Turn in your solution to this exercise as directed by your instructor.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 8, 2005 by Doug Baldwin