SUNY Geneseo, Department of Computer Science

Homework 1

CSci 141 , Fall 2003

Prof. Doug Baldwin

Due Friday, Oct. 10

Purpose

This exercise's main purpose is to let you practice using recursion in relatively sophisticated ways, in a complete program. Secondarily, this exercise also introduces you to reading text from files in Java.

Background

Files

The big new thing in this exercise will probably be files and file input. A separate Guide to Text Input in Java explains how to read text from a file. You can find this guide on-line at http://cs.geneseo.edu/~baldwin/reference/java-textio.html.

In order to read from a file, you need to know the file's name. File names are basically strings that specify where the file you want is in the computer's file system. A "file system" is simply the collection of all servers, folders, and files that a computer has access to. Generally these things have a nested, or hierarchical, structure: there are only a few servers, each of which has several main folders, each of those folders contains other folders, and so forth, continuing through folders inside folders until you finally get to a folder that contains the file you want. Almost every modern computer system thus views a file name as a string consisting of a series of folder names leading from some standard place in the file system hierarchy (often the top) to a specific file.

For example, a typical file name in our Macintosh lab might be "/Volumes/MacOS X/Users/labuser/afile.txt", which means the file named "afile.txt", which is stored in the folder named "labuser", which in turn is in the folder named "Users", which in turn is in the folder named "MacOS X", which is one of the volumes (local disks or servers) connected to this computer.

Robots

This exercise asks you to use the Robot class you have used in other exercises. Documentation for this class is on the Web, at http://cs.geneseo.edu/~baldwin/sc/doc/. You can find code for the Robot and RobotRoom classes on the Web at http://cs.geneseo.edu/~baldwin/sc/Robot.java, and http://cs.geneseo.edu/~baldwin/sc/RobotRoom.java, or in our folder on the "Course Materials" file server.

Recursion

For information on recursion, see Chapter 6 of The Science of Computing. You also have to prove something about a recursive algorithm in this exercise, for which Section 7.1.2 of The Science of Computing is a reference. In particular, see the discussion of strong induction.

Exercise

At one time or another in your life, you have probably played 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 "the place where we swim," so they go to the swimming pool to look for a third clue, and so forth. Your basic job is to write a program that uses a robot to carry out a similar treasure hunt.

Our robots, unfortunately, 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) old 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 white tile means that the next clue is the tile directly in front of the robot
A blue tile means that the next clue is the tile to the robot's left
A green tile means that the next clue is the tile to the robot's right
A red tile means that the treasure hunt splits into two parts -- the next clue for the first part is the tile to the robot's left, and the next clue for the second part is the tile to the robot's right
A yellow (kind of gold-like) tile is a treasure -- it marks the end of a part of a treasure hunt.

Your program should define a subclass of Robot that has a hunt message that makes a robot carry out a treasure hunt. The hunt message has no parameters. You may assume as a precondition 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.) Upon completion of a treasure hunt, a robot should have visited all the treasures in that treasure hunt (there may be more than one treasure, since red tiles allow treasure hunts to fork into multiple parts), and should have returned to the tile it started on.

You may adopt further postconditions, in addition to the ones given above, if you wish.

In addition to the hunt method, you should write a main program that exercises your treasure-hunting subclass.

When you have designed an algorithm for doing treasure hunts (or even while you are designing it), prove that your algorithm is correct. ("Correct" in this case means that the robot will visit every tile in the treasure hunt and return to its starting tile, plus establish any other postconditions you add.)

In order to set up treasure hunts for robots to carry out, your program should be able to read a string describing a robot room from a file, and then use that string to initialize a room (recall the one-parameter constructor for RobotRoom).

I have written a number of files that contain suitable descriptions of robot rooms laid out for treasure hunts. These files are in a folder named "Treasure Hunts" in our folder on the "Course Materials" server. Each file consists of one line of text, which is the string describing the room. 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.

Some of the files that I have provided include

Stop.txt: A file that describes a treasure hunt that immediately ends at a treasure. Good for testing your handling of treasures in isolation from everything else.
Forward.txt: A file that describes a treasure hunt in which the robot only has to move forward once in order to find the only treasure. Good for testing your robot's ability to handle "move forward" clues.
Left.txt: A file that describes a treasure hunt in which the robot only has to turn left in order to find the only treasure. Good for testing your robot's ability to handle "turn left" clues.
Right.txt: A file that describes a treasure hunt in which the robot only has to turn right in order to find the only treasure. Good for testing your robot's handling of "turn right" clues.
Split.txt: A file that describes a treasure hunt that immediately splits into two parts, each of which then ends at a treasure. Good for testing your robot's ability to handle treasure hunts that split.
SimpleHunt.txt: A file that contains a non-trivial, but still fairly simple, treasure hunt.

These files are all in a folder named "TreasureHunts" inside our folder on "Course Materials". On a Macintosh, if you connect to "Course Materials" you can access these files without any further work by using names of the form "/Volumes/Course Materials/CS 141/Baldwin/TreasureHunts/" and then the final name given above. For example, "/Volumes/Course Materials/CS 141/Baldwin/TreasureHunts/Stop.txt". Note that spaces and capitalization in file names matter to the Macintosh operating system.

Follow-Up

Turn in a printout of any code you write, including your robot subclass and the main program that exercises it. Also turn in your correctness proof for your treasure hunting algorithm. The proof can be comments in the program, or on a separate piece of paper.