// This program defines and exercises a robot that goes on "treasure hunts."
// Specifically, the robot follows clues in the form of tile colors that tell
// it where to go, as follows:
// White tiles: move one tile forward
// Blue tiles: Turn left and move one tile forward
// Green Tiles: Turn right and move one tile forward
// Red tiles: Pursue further treasure hunts to the left and right
// Yellow tiles: Stop, you're at the end of a path.
// History:
//
// September 2003 -- Written by Doug Baldwin, based on a long history
// of similar exercises in other languages.
import java.io.*;
import java.awt.Color;
import geneseo.cs.sc.Robot;
import geneseo.cs.sc.RobotRoom;
class TreasureRobot extends Robot {
// Initialize a treasure-hunting robot with its position, heading, and room.
// This simply passes its parameters on to the analogous constructor for Robots.
public TreasureRobot( int column, int row, int heading, RobotRoom room ) {
super( column, row, heading, room );
}
// Carry out a treasure hunt. This is based on the general recursive insight
// that to do a treasure hunt, you follow the first clue and then do a
// treasure hunt that starts with the next clue you find. See the comments at
// the top of this file for descriptions of the clues and their meanings.
// Note that red tiles mark the end of (part of) a treasure hunt, and so
// are base cases for the recursion. Green tiles generate two recursive hunts,
// one to the left and one to the right.
// Preconditions: The robot is standing on the first clue, and facing into
// the treasure hunt.
// Postconditions: The robot is standing back on the first clue, facing out
// of the treasure hunt. The robot has visited all the yellow tiles in the
// treasure hunt.
//
// Correctness proof, by strong induction on the number of tiles in the treasure
// hunt:
//
// Base case: The treasure hunt contains only one tile. Since the only tiles that
// don't imply that a treasure hunt contains more tiles adjacent to the first
// are yellow, this tile must be yellow. The algorithm's "if ( tileColor == Color.yellow )"
// test therefore succeeds, and the algorithm turns the robot around. The robot is
// still on the first (and only) clue, but facing out of the treasure hunt. The robot
// has visited all yellow tiles in the treasure hunt (namely the one tile it started on).
//
// Induction hypothesis: Assume that for any treasure hunt of fewer than k tiles
// (k > 1), "hunt" leaves the robot standing back on the first clue, facing out
// of the treasure hunt, and having visited all the yellow tiles in the treasure hunt.
//
// Show that for any treasure hunt of k tiles, "hunt" leaves the robot standing back
// on the first clue, facing out of the treasure hunt, and having visited all the yellow
// tiles in the treasure hunt. There are four ways the k-tile treasure hunt can begin:
// with a white tile, with a blue tile, with a green tile, or with a red tile.
// White tile: The "if ( tileColor == Color.white )" test succeeds, so the robot
// moves forward, landing on the second tile of the treasure hunt (henceforth called
// "the second tile"). There are k-1 tiles left in the treasure hunt that begins on
// the second tile, and the robot is facing into that treasure hunt. Thus the recursive
// message causes the robot to visit all yellow tiles in that treasure hunt (and so
// in the k-tile one), come back to the second tile, and face out, towards the first
// tile. The final move therefore returns the robot to the first tile, and leaves it
// facing out of the original treasure hunt.
// Blue tile: The "if ( tileColor == Color.blue )" test succeeds, so the robot
// turns left and moves forward, landing on the second tile of the treasure hunt
// (henceforth called "the second tile"). There are k-1 tiles left in the treasure
// hunt that begins on the second tile, and the robot is facing into that treasure hunt.
// Thus the recursive message causes the robot to visit all yellow tiles in that treasure
// hunt (and so in the k-tile one), come back to the second tile, and face back towards
// the first tile. The subsequent move therefore returns the robot to the first tile, and
// the turnRight leaves it facing out of the original treasure hunt.
// Green tile: The "if ( tileColor == Color.green )" test succeeds, so the robot
// turns right and moves forward, landing on the second tile of the treasure hunt
// (henceforth called "the second tile"). There are k-1 tiles left in the treasure
// hunt that begins on the second tile, and the robot is facing into that treasure hunt.
// Thus the recursive message causes the robot to visit all yellow tiles in that treasure
// hunt (and so in the k-tile one), come back to the second tile, and face back towards
// the first tile. The subsequent move therefore returns the robot to the first tile, and
// the turnLeft leaves it facing out of the original treasure hunt.
// Red tile: The "if ( tileColor == Color.red )" test succeeds, so the robot
// turns left and moves forward, landing on the first tile of the treasure hunt
// to the left of the red tile (henceforth called "the left tile"). There are fewer than
// k tiles in the treasure hunt that begins on the left tile, and the robot is facing into
// that treasure hunt. Thus the recursive message causes the robot to visit all yellow
// tiles in the left-hand treasure hunt, come back to the left tile, and face back towards
// the first tile. The next two move messages move the robot to the first tile
// of the treasure hunt to the right of the red tile (henceforth called "the right tile").
// There are fewer than k tiles in the treasure hunt that begins on the right tile, and
// the robot is facing into that treasure hunt. Thus the second recursive message causes
// the robot to visit all yellow tiles in the right-hand treasure hunt. Between these
// yellow tiles and those in the left-hand treasure hunt, the robot has visited all yellow
// tiles in the original treasure hunt. The recursive message also brings the robot
// back to the right tile, and leaves it facing back towards the first tile. The final
// move and turnLeft leave it on that first tile, facing out of the original treasure hunt.
public void hunt() {
Color tileColor = this.colorOfTile();
if ( tileColor == Color.white ) { // Next treasure hunt is in front of the robot
this.move();
this.hunt();
this.move();
}
else if ( tileColor == Color.blue ) { // Next treasure hunt is to the left
this.turnLeft();
this.move();
this.hunt();
this.move();
this.turnRight();
}
else if ( tileColor == Color.green ) { // Next treasure hunt is to the right
this.turnRight();
this.move();
this.hunt();
this.move();
this.turnLeft();
}
else if ( tileColor == Color.red ) { // Treasure hunts to both left and right
this.turnLeft();
this.move();
this.hunt();
this.move();
this.move();
this.hunt();
this.move();
this.turnLeft();
}
else if ( tileColor == Color.yellow ) { // End of path, just turn around
this.turnLeft();
this.turnLeft();
}
}
// The main method reads a description of a treasure hunt from a file, and creates
// a room from that description. Then it creates a robot and sets it hunting in
// that room.
public static void main( String args[] ) {
// Create the room:
final String roomDirectory = "../";
final String roomFile = "SimpleHunt.txt";
String roomDescription = "17 17";
try {
BufferedReader in = new BufferedReader( new FileReader( roomDirectory + roomFile ) );
roomDescription = in.readLine();
in.close();
}
catch ( Exception err ) {
System.err.println( "Error reading room description:" );
System.err.println( "\t" + err );
}
RobotRoom treasureRoom = new RobotRoom( roomDescription );
// Put a robot in the room, and have it do the treasure hunt:
TreasureRobot hunter = new TreasureRobot( 8, 15, Robot.NORTH, treasureRoom );
hunter.hunt();
}
}