School of Engineering and Applied Science
Department of Computer Science
CSci 53 -- Introduction to Software Development
http://www.seas.gwu.edu/~csci53
Prof. Michael B. Feldman
mfeldman@gwu.edu

Introducing Algorithms: Adventures of the Java Spider

Michael B. Feldman
Department of Computer Science
The George Washington University
revised August 2004


CONTENTS
PROGRAMS BY SECTION

1. Introducing the Spider



2. Straight-Line Algorithms
    SpiderCommands with Parameters
Startup
ShowSingleStep		 WalkLine
DrawBoxWithColor		 WalkBox
3. Algorithms with Single Loops
    Random Directions and Colors
DrawBoxWithLoop
DrawBoxWithRandomness

4. Algorithms with Nested Loops
    Spiral Patterns
    The while Loop
DrawBoxWithNestedLoops
DrawSpiral
DrawSpiralNoBlanks

5. Algorithms with Conditional Execution
WalkTooFar WalkToWall TourRoom
6. The Drunken Spider
DrunkenSpider

Review



The purpose of this report is to introduce you to algorithms through programming a simple picture-drawing creature called the spider. We introduce an imaginary spider that steps around an imaginary room drawn on the screen. The spider recognizes a number of commands, which we can issue by writing, compiling, and executing spider programs.

We use the spider to introduce a number of algorithmic concepts, including control structures and parameters. The goal here is to just give you a quick introduction, to get you started writing some "fun" programs.

The examples presented here are simple and clear and give you obvious feedback on the screen, we think you will find them useful in understanding algorithms and a number of Java program constructs. We urge you to compile and run these examples on a computer, observe their behavior, and experiment with them by making changes as you see fit.

1. Introducing the Spider

This section introduces an imaginary spider that steps around an imaginary room drawn on the screen, and leaves tracks in any of several colors. The spider recognizes a number of commands, which we can issue by writing, compiling, and executing spider programs.

The spider is simulated by an Java module called a class within which is the set of commands that the spider recognizes and obeys. The class is a very important construct in Java; it provides a way of encapsulating, or grouping, a set of related commands or methods. All Java programs consist of one or more classes; some programs, like the ones here, include a class with just one method called the main method. Some classes are provided with the Java language; these are called standard classes. Others are written by book authors, professors, students, professional developers, and other users of Java. The spider class was written by the author of this report.

The source statements for a Java class are given in a program file, in this case the file Spider.java. Everything you need to know to use a class is generally provided in a separate document of some kind; the documentation omits the operational details of the methods and just describes how to use each one. Often we refer to this class documentation as the specification of the class.

The Spider specification is shown as  Figure 1. This class specification is similar to others we will use during the semester. Read through the specification and note that it contains two types of information: unchanging data values called constants, and methods. Each method is given by its Java form and accompanied by a brief English description of it behavior. In this report, we go through the various constants and methods, and show and explain 14 programs that use some of the methods in the spider class. You don't need to understand yet just how the class works. As your knowledge of software development increases, and certainly by the end of this course, you will be able to understand the spider's internal mechanisms and can study them in detail.

Figure 1. Class Spider
Spider's color constants
final int RED
final int BLUE
final int GREEN
final int BLACK
final int NONE
final int NUMBER_OF_COLORS
Spider's direction constants
final int NORTH
final int EAST
final int SOUTH
final int WEST
Spider's View of her Room - rows and cols 1-20
final int ROWS_IN_ROOM = 20
final int COLS_IN_ROOM = 20
Methods Behavior
void start () Draws the room on the screen, with spider in center, facing NORTH and writing in GREEN
void turnRight () Spider turns right 90 degrees
void step () Spider takes one step forward
void quit () Stops the program
void changeColor (int NewColor) Spider starts writing in the new color
void face (int WhichWay) Spider faces the given direction
int currentColor () Returns the color the spider is currently using
int currentDirection () Returns the direction the spider is currently facing
boolean atWall () Returns true if the spider's next step will hit a wall, otherwise false
int randomStep () Spider takes a random number of steps forward, 20 or less
int randomColor () Spider starts writing in a randomly-chosen color
int randomDirection () Spider turns to face in a randomly-chosen direction
void singleStep (boolean Setting) Sets the single-step switch to true or false; it starts out false. If single-stepping is turned on, the spider moves just one step each time the user presses the RETURN key.
boolean singleStepping () Returns true if the single-stepping switch is true, otherwise false

2. Straight-Line Algorithms

In this section we use the spider to introduce you to straight-line algorithms. A straight-line algorithm is one that is just a straight sequence of instructions, with no decisions or "forks in the road" and no backtracking to an earlier point in the algorithm. The algorithm just moves in one direction.

Let's look at a very simple spider program, Program 2.2. The spider's commands appear between the innermost brackets { and }; these commands will differ from program to program. The other lines of the program are the same in all the programs here. As you can see, this program just calls the spider's start and stop methods. The sample run shows that calling Spider.start() draws a "room" on the screen, placing the spider icon (an asterisk) in the center. The small box in the upper left corner indicates the spider's color by a letter R, B, G, or K (for RED, BLUE, GREEN, or BLACK, respectively) with a dot indicating NONE. The spider's current direction is indicated by an arrow-like character ^, >, v, or <, incating NORTH, EAST, SOUTH, and WEST, respectively. The spider starts out facing north (up the screen) and leaving green tracks. Calling Spider.quit() just ends the program. Each spider program must begin with Spider.start() and end with Spider.quit().

Note: Java rules require each method call to have a set of parentheses. Some methods require a list of parameter values to appear between the parentheses; Spider.start() and Spider.quit() require empty parentheses.

Program 1. The Simplest Spider Program

//--------------------------------------------------------------
//| Very simple Spider program; just starts and stops
//| Author: M. B. Feldman, The George Washington University
//| Last Modified: August 2004
//--------------------------------------------------------------
import mbf.Spider;
public class Startup
{
  public static void main (String[] args)
  {
    Spider.start();
    Spider.quit();
  }
}

Sample Run of Program 1

                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| ^ |              |. . . . . . . . . . . . . . . . . . . .|
| G |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . * . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------


In Program 2 the spider takes five steps forward. You can see this from the sequence of five commands,  Spider.Step(). The sample run shows the spider in a location five rows north (upward) from the starting point.

Program 2. The Spider Walks a Line

//--------------------------------------------------------------
//| Spider walks five steps in a northward direction 
//| Author: M. B. Feldman, The George Washington University
//| Last Modified: August 2004
//--------------------------------------------------------------
import mbf.Spider;
public class WalkLine
{
  public static void main (String[] args)
  {
    Spider.start();
    Spider.step();
    Spider.step();
    Spider.step();
    Spider.step();
    Spider.step();
    Spider.quit();
  }
}

Sample Run of Program 2

                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| ^ |              |. . . . . . . . . . . . . . . . . . . .|
| G |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . * . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------

In Program 3 the spider walks around a square box, taking three steps forward, then turning right, then taking more steps, turning right again, and so on. The spider ends up in its starting position.

Program 3. The Spider Walks around a Box

//--------------------------------------------------------------
//| Spider walks a 4 x 4 box
//| Author: M. B. Feldman, The George Washington University
//| Last Modified: August 2004
//--------------------------------------------------------------
import mbf.Spider;
public class WalkBox 
{
  public static void main (String[] args)
  {
    Spider.start();

    Spider.step();
    Spider.step();
    Spider.step();
    Spider.turnRight();

    Spider.step();
    Spider.step();
    Spider.step();
    Spider.turnRight();

    Spider.step();
    Spider.step();
    Spider.step();
    Spider.turnRight();

    Spider.step();
    Spider.step();
    Spider.step();
    Spider.turnRight();

    Spider.quit();
  }
}

Sample Run of Program 3

                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| ^ |              |. . . . . . . . . . . . . . . . . . . .|
| G |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . G G G G . . . . . . .|
                   |. . . . . . . . . G . . G . . . . . . .|
                   |. . . . . . . . . G . . G . . . . . . .|
                   |. . . . . . . . . * G G G . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------
 

Spider Commands with Parameters

So far, we've used four spider commands: start, quit, step, and turnRight. In Program 4 we introduce two more commands: face and changeColor. Figure 2 gives some lines selected from the Spider specification:

Figure 2. A few lines from the Spider specification

Spider's color constants
final int RED
final int BLUE
final int GREEN
final int BLACK
final int NONE
final int NUMBER_OF_COLORS
Spider's direction constants
final int NORTH
final int EAST
final int SOUTH
final int WEST
Methods Behavior
void changeColor (int NewColor) Spider starts writing in the new color
void face (int WhichWay) Spider turns to face the given direction
void singleStep (boolean Setting) Sets the single-step switch to true or false; it starts out false.
These lines introduce the spider's colors and compass directions, and three methods. Let's consider the last method first. Program 4 is just like Program 3, except for the additional line at the beginning, which reads

Spider.singleStep(true);

This causes the spider to go into "single-stepping mode". That is, before taking each step the spider waits for you to press the RETURN key on your keyboard. This helps you slow down the action of your program, so you can follow it step by step. An indication is given on the screen when the spider is single-stepping, as you can see in the sample output.
 

Program 4. The Spider walks around a box, but in Single-Step mode

//--------------------------------------------------------------
//| Spider walks a 4 x 4 box, demonstrating single-step mode
//| Author: M. B. Feldman, The George Washington University
//| Last Modified: August 2004
//--------------------------------------------------------------
import mbf.Spider;
public class ShowSingleStep
{
  public static void main (String[] args)
  {
    Spider.start();
    Spider.singleStep(true);  // turn single-stepping on here

    Spider.step();
    Spider.step();
    Spider.step();
    Spider.turnRight();

    Spider.step();
    Spider.step();
    Spider.step();
    Spider.turnRight();

    Spider.step();
    Spider.step();
    Spider.step();
    Spider.turnRight();

    Spider.step();
    Spider.step();
    Spider.step();
    Spider.turnRight();

    Spider.quit();
  }
}

Sample Run of Program 4

                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| ^ |              |. . . . . . . . . . . . . . . . . . . .|
| G |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . G G G G . . . . . . .|
 SINGLE STEP ON    |. . . . . . . . . G . . G . . . . . . .|
  Press RETURN     |. . . . . . . . . G . . G . . . . . . .|
                   |. . . . . . . . . * G G G . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------
 

Writing

Spider.singleStep(false);

turns the single-stepping off and causes the program to resume its regular speed.

Now let's look at the two other new methods. The first method, changeColor, must be called with a parameter selected from one of the color values, for example, 

Spider.changeColor(Spider.RED);
which will cause the spider to leave an R, representing a red mark, on the screen each time it takes a step. The second method, Face, must be called by including, between the parentheses, a parameter selected from one of the directions, for example, 
Spider.face(Spider.WEST);
which will cause the spider to turn (without moving) to face in a westerly direction (leftward on the screen).

Now let's use these two methods. In Program 5 the spider starts out facing west, then walks around the same kind of square as in Program 3, but this time it draws each side in a different "color."

Note: We've put "color" in quotation marks because the spider class does not require a color monitor to operate properly. As we mentioned earlier, the spider uses the letters R, G, B, and K to simulate the actual colors red, green, blue, and black. Also, a dot simulates the no-color ("invisible") case; it does not show up on the screen because a new dot is displayed over the one in the room grid.

Program 5. The Spider Draws a Box in Different Colors

//--------------------------------------------------------------
//| Spider draws a 4 x 4 box with colors
//| Author: M. B. Feldman, The George Washington University
//| Last Modified: August 2004
//--------------------------------------------------------------
import mbf.Spider;
public class DrawBoxWithColor
{
  public static void main (String[] args)
  {
    Spider.start();
    Spider.face(Spider.WEST);

    Spider.changeColor(Spider.BLACK);
    Spider.step();
    Spider.step();
    Spider.step();
    Spider.turnRight();

    Spider.changeColor(Spider.RED);
    Spider.step();
    Spider.step();
    Spider.step();
    Spider.turnRight();

    Spider.changeColor(Spider.GREEN);
    Spider.step();
    Spider.step();
    Spider.step();
    Spider.turnRight();

    Spider.changeColor(Spider.BLUE);
    Spider.step();
    Spider.step();
    Spider.step();
    Spider.turnRight();

    Spider.quit();
  }
}

Sample Run of Program 5

                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| < |              |. . . . . . . . . . . . . . . . . . . .|
| B |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . G G G B . . . . . . . . . .|
                   |. . . . . . R . . B . . . . . . . . . .|
                   |. . . . . . R . . B . . . . . . . . . .|
                   |. . . . . . R K K * . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------

Exercises for Section 2

1. Write a spider program that requests the spider to draw two of your initials on the screen. For example, 
XXXXX      X
X          X
XXX        X
X      X   X
XXXXX  XXXXX

3. Algorithms with Single Loops

Program 5, in the previous section, contains four sequences of almost identical statements. Leaving aside color changes for a moment, the sequence 
Spider.step();
Spider.step();
Spider.step();
Spider.turnRight();
appears four times in this straight-line program.

Algorithms quite frequently involve repetitive sequences of steps. Indeed, we could write the basic box-drawing algorithm as a repetition:

 Algorithm for drawing a box:

 1. Repeat steps 1.1 and 1.2 four times.

1.1 Take three steps forward.

 1.2 Turn right.

In programming, a repetition is generally called a loop. We can translate this algorithm into a program that uses a Java control structure called the for construct. Program 6 contains just such a structure. The statement 
    for (int Side = 1; Side <= 4; Side++)
    {
      Spider.step();
      Spider.step();
      Spider.step();
      Spider.turnRight();
    }


instruct the spider to repeat, four times, the sequence of statements that appears between the braces {}. The sequence of statements is called the loop body. The for construct has three parts, separated by semicolons.

Program 6. The Spider Draws a Box Using a Loop Control Structure

//--------------------------------------------------------------
//| Spider draws a 4 x 4 box, using a loop
//| Author: M. B. Feldman, The George Washington University
//| Last Modified: August 2004
//--------------------------------------------------------------
import mbf.Spider;
public class DrawBoxWithLoop
{
  public static void main (String[] args)
  {
    Spider.start();
    Spider.face(Spider.WEST);

    Spider.changeColor(Spider.RED);

    for (int Side = 1; Side <= 4; Side++)
    {
      Spider.step();
      Spider.step();
      Spider.step();
      Spider.turnRight();
    }

    Spider.quit();
  }
}

Sample Run of Program 6

                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| ^ |              |. . . . . . . . . . . . . . . . . . . .|
| R |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . R R R R . . . . . . .|
                   |. . . . . . . . . R . . R . . . . . . .|
                   |. . . . . . . . . R . . R . . . . . . .|
                   |. . . . . . . . . * R R R . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------

Random Directions and Colors

The box drawn by the spider in Program 6 is exactly the same every time the program is run: always in the same location, always red. Let's make the program more interesting by causing the spider to start walking in a randomly selected direction, and to change the color of each side by a random color selection. Figure 3 shows two spider methods using which we can get random colors and directions from these two spider methods:
Methods Behavior
int randomColor() Spider starts writing in a randomly-chosen color
int randomDirection() Spider turns to face in a randomly-chosen direction

These have obvious meanings. Program 7 makes use of these operations to draw a box that will look different each time the program is one. The sample run shows just one execution; try running the program a number of times to observe its behavior.

Program 7. Drawing a Box Using Random Colors and Starting Direction

//--------------------------------------------------------------
//| Spider draws a box, using random initial direction and colors
//| Author: M. B. Feldman, The George Washington University
//| Last Modified: August 2004
//--------------------------------------------------------------
import mbf.Spider;
public class DrawBoxWithRandomness
{
  public static void main (String[] args)
  {
    Spider.start();
    Spider.face(Spider.randomDirection());

    for (int Side = 1; Side <= 4; Side++)
    {
      Spider.changeColor(Spider.randomColor());
      Spider.step();
      Spider.step();
      Spider.step();
      Spider.turnRight();
    }

    Spider.quit();
  }
}

Sample Run of Program 7

                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| ^ |              |. . . . . . . . . . . . . . . . . . . .|
| R |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . * G G K . . . . . . .|
                   |. . . . . . . . . R . . K . . . . . . .|
                   |. . . . . . . . . R . . K . . . . . . .|
                   |. . . . . . . . . R R R R . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------

Exercises for Section 3

1. Write and test a program that instructs the spider to draw a pattern in the shape of a highway "yield" sign, that is,
  
    RRRRRRR
     R   R
      R R
       R
Hints: Start the spider facing west, draw the top line, and so on. Also note that you can get the spider to draw a "blank" by changing its color to None.

4. Algorithms with Nested Loops

Programs 6 and 7 both contain the sequence of statements 
Spider.step();
Spider.step();
Spider.step();
which is, itself, a repetition. Let's take this into account by rewriting the box-drawing algorithm, adding the color change as we go:

Algorithm for drawing a box:

 1. Repeat steps 1.1 through 1.3 four times.

 1.1 Choose a color.

 1.2 Repeat step 1.2.1 three times.

 1.2.1 Take one step forward.
1.3 Turn right.
This algorithm is saying that each of the four times we reach step 1.2, we execute step 1.2.1 three times. The real power in algorithms is that we can combine straight-line sequences with repetitions (and conditional executions, as we shall see shortly) in almost unlimited ways.

How can we represent this new algorithm in a program? We can combine control structures, to reflect the algorithm steps. In this case we can include an entire for construct inside another one. To put it another way, a statement in a loop body can be another entire loop construct. This is called nesting control structures. Program 7 shows this: The inner loop construct 

      for (int Count = 1; Count <= 5; Count++)
      {
        Spider.step();
      }
is nested inside the outer one; for variety we changed the number of steps to 5. We use indentation in the program to highlight the nesting, as we use indentation in algorithms and other outlining methods. The indentation is not required by the compiler, but it certainly makes a difference in the clarity of the program! The behavior of this program is very similar to that of Program 7, so we have omitted the sample run. Try running it yourself several times to observe the randomness again.

Program 8. The Spider Draws a Box Using Nested Loop Control Structures

//--------------------------------------------------------------
//| Spider draws a  6 x 6 box, using nested loops
//| Author: M. B. Feldman, The George Washington University
//| Last Modified: August 2004
//--------------------------------------------------------------
import mbf.Spider;
public class DrawBoxWithNestedLoops
{
  public static void main (String[] args)
  {
    Spider.start();
    Spider.face(Spider.randomDirection());

    for (int Side = 1; Side <= 4; Side++)
    {
      Spider.changeColor(Spider.randomColor());

      for (int Count = 1; Count <= 5; Count++)
      {
        Spider.step();
      }

      Spider.turnRight();
    }

    Spider.quit();
  }

Spiral Patterns

So far, our loop constructs have used numberic literals (like 3, 4, and 5) to represent the bounds (starting and ending values) of the counters. This is not required; loop bounds can vary as the program runs. To see this, consider the loop structure of Program 9: 
    for (int Line = 1; Line <= 10; Line++)
    {
      Spider.changeColor(Spider.randomColor());

      // Inner loop takes its upper bound from outer count
      for (int Count = 1; Count <= Line; Count++)
      {
        Spider.step();
      }

      Spider.turnRight();
    }
As the comment indicates, the inner loop takes its upper bound from the current value of the outer loop's counter. When the first line is being drawn (Line is 1), the inner loop counter ranges from 1 to 1, so the spider takes one step. When the second line is drawn (Line is 2), the spider takes two steps, and so on until the spider takes ten steps to draw the tenth line. This results in the spiral pattern shown in the sample run; make sure you understand how this happens. Make sure to run this program several times to appreciate the randomness. The pattern really is different each time!

Program 9. The Spider Draws a Spiral Pattern

//--------------------------------------------------------------
//| Spider draws a spiral pattern
//| Author: M. B. Feldman, The George Washington University
//| Last Modified: August 2004
//--------------------------------------------------------------
import mbf.Spider;
public class DrawSpiral
{
  public static void main (String[] args)
  {
    Spider.start();
    Spider.face(Spider.randomDirection());

    for (int Line = 1; Line <= 10; Line++)
    {
      Spider.changeColor(Spider.randomColor());

      // Inner loop takes its upper bound from outer count
      for (int Count = 1; Count <= Line; Count++)
      {
        Spider.step();
      }

      Spider.turnRight();
    }

    Spider.quit();
  }
}

Sample Run of Program 9

                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| < |              |. . . . . . . . . . . . . . . . . . . .|
| R |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . R R R R R R R R R R . . . . .|
                   |. . . . . G . . . . . . . . R . . . . .|
                   |. . . . . G . K K K K K K . R . . . . .|
                   |. . . . . G . K . . . . K . R . . . . .|
                   |. . . . . G . K . G G . K . R . . . . .|
                   |. . . . . G . K . . G . K . R . . . . .|
                   |. . . . . G . K . . . . K . R . . . . .|
                   |. . . . . G . . . . . . K . R . . . . .|
                   |. . . . . G G G G G G G G . R . . . . .|
                   |. . . . . . . . . . . . . . R . . . . .|
                   |. . . . . . . . . . . . . . * . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------
In the test run above, one line appears to be missing from the spiral. Why is this? In choosing a random color to draw with, NONE is a possible choice; on the average, it will be selected as often as any of the other colors, namely once in five choices. Drawing with no color results in a line that is drawn with dots, so it seems to be missing altogether.

Of course, in any one run, there may be more than one in five missing lines. This is the nature of randomness: If you flip a coin 10 times, on the average you should get five heads and five tails, but sometimes you get more heads than that, and sometimes more tails. It's similar in picking a random color. For example, how many lines seem to be missing from the output below?

                    ---------------------------------------
 ---               |. . . . . . . . . . . . . . . . . . . .|
| < |              |. . . . . . . . . . . . . . . . . . . .|
| R |              |. . . . . . . . . . . . . . . . . . . .|
 ---               |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . K K K K K K K K K R . . . . .|
                   |. . . . . G . . . . . . . . R . . . . .|
                   |. . . . . G . . . . . . . . R . . . . .|
                   |. . . . . G . B . . . . . . R . . . . .|
                   |. . . . . G . B . . G . . . R . . . . .|
                   |. . . . . G . B . . G . . . R . . . . .|
                   |. . . . . G . B G G G . . . R . . . . .|
                   |. . . . . G . . . . . . . . R . . . . .|
                   |. . . . . G . . . . . . . . R . . . . .|
                   |. . . . . . . . . . . . . . R . . . . .|
                   |. . . . . . . . . . . . . . * . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------

The while loop

Let's improve the spiral program to eliminate the missing lines. We can do this by noticing when the choice is NONE, and just selecting another color before proceeding. First, consider this spider method, which lets us determine the color the spider is using:
Methods Behavior
int currentColor()  Returns the spider's current color

Let's combine this with another kind of Java loop statement, the while statement.

while (Spider.currentColor() == Spider.NONE)
{
  Spider.changeColor(Spider.randomColor());
}

In the expression between the parentheses,

Spider.currentColor() == Spider.NONE

The symbol == should be read "is equal to". The while statement checks whether the current color is equal to NONE, and if so, carries out the statements between the braces (chooses another color) and then checks again. Since we could randomly choose NONE several times in a row, the while causes a new color choice until we choose one that is not NONE. At that point, execution continues after the entire while statement. Fitting this into the overall spiral program, we get Program 10. Examine this program, then run it several times to confirm that we get no blank lines.

Program 10. The Spider Draws a Spiral Pattern without Blank Lines

//--------------------------------------------------------------
//| Spider draws a spiral pattern
//| Author: M. B. Feldman, The George Washington University
//| Last Modified: August 2004
//--------------------------------------------------------------
import mbf.Spider;
public class DrawSpiralNoBlanks
{
  public static void main (String[] args)
  {
    Spider.start();
    Spider.face(Spider.randomDirection());

    for (int Line = 1; Line <= 10; Line++)
    {
      Spider.changeColor(Spider.randomColor());

      // Loop until the color is non-blank
      while (Spider.currentColor() == Spider.NONE)
      {
        Spider.changeColor(Spider.randomColor());
      }

      // Inner loop takes its upper bound from outer count
      for (int Count = 1; Count <= Line; Count++)
      {
        Spider.step();
      }

      Spider.turnRight();
    }

    Spider.quit();
  }
}

Exercises for Section 4

1. Write and test a program that instructs the spider to draw a pattern in the shape of a solid triangle, that is, 
 B
 BB
 BBB
 BBBB
 BBBBB
 BBBBBB
2. Write a spider program to draw a checkerboard pattern, that is,

 G G G G
  G G G G
 G G G G
  G G G G


 

5. Algorithms with Conditional Execution

Another important algorithmic structure is conditional execution. To introduce the need for this, consider Program 11, which commands the spider to take 20 steps forward. The Spider class doesn't allow the spider to walk through a wall; if the spider is about to hit a wall, the spider program just beeps and the spider moves no farther.

Program 11. The Spider Tries to Walk into a Wall

//--------------------------------------------------------------
//| Spider tries to walk 12 steps in a northward direction
//| Author: M. B. Feldman, The George Washington University
//| Last Modified: August 2004
//--------------------------------------------------------------
import mbf.Spider;
public class WalkTooFar
{
  public static void main (String[] args)
  {
    Spider.start();

    for (int Count = 1; Count <= 12; Count++)
    {
      Spider.step();
    }

    Spider.quit();
  }
}

Is there a way to let the spider detect the wall and take an action, instead of just stopping with a beep? Yes! The spider program can check to see whether the spider will step into a wall, using conditional execution. The spider package provides a condition-testing, or Boolean method
 
Methods Behavior
boolean atWall () Returns true if the spider's next step will hit a wall, otherwise false

Now in Program 12, the lines 

if (Spider.atWall())
{
  Spider.turnRight();          // get out of the loop
}
test the condition Spider.atWall(). If the condition is true, the spider turns right and keeps walking, instead of hitting the wall. The if statement is called a conditional statement -- the lines between the braces are executed only if the condition (in this case Spider.atWall()) is true at the time program flows into the if.

Program 12. The Spider Goes to the Wall and Turns

//--------------------------------------------------------------
//| Spider tries to walk 20 steps in a northward direction
//| but turns when it reaches the wall.
//| Author: M. B. Feldman, The George Washington University
//| Last Modified: August 2004
//--------------------------------------------------------------
import mbf.Spider;
public class WalkToWall
{
  public static void main (String[] args)
  {
    Spider.start();

    for (int Count = 1; Count <= 20; Count++)
    {
      if(Spider.atWall())
      {
        Spider.turnRight();
      }
      Spider.step();
    }

    Spider.quit();
  }
}

Sample Run of Program 12

                    ---------------------------------------
 ---               |. . . . . . . . . G G G G G G G G G G *|
| > |              |. . . . . . . . . G . . . . . . . . . .|
| G |              |. . . . . . . . . G . . . . . . . . . .|
 ---               |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . G . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                   |. . . . . . . . . . . . . . . . . . . .|
                    ---------------------------------------

Let's use Spider.atWall() and while loops to command the spider to take a walk around the edges of its room. The first section of Program 12 is a while loop that causes the spider to move to the first wall and stop:

while(!Spider.atWall()) // loop until spider gets to wall
{
  Spider.step();
}

The ! symbol in Java means "not", so the condition should be read "Spider.AtWall is not true", or "Spider.AtWall is false", or in English, "the spider is not at the wall". You can read the entire loop statement as "loop while the spider is not at the wall", or to put it positively, "loop until the spider gets to the wall".

In Program 13, when the spider reaches the first wall, it enters the ensuing for loop, in which it turns right and then walks along each wall until it reaches the end of that wall.
 

Program 13. The Spider Tours Its Room

//--------------------------------------------------------------
//| Spider takes a tour of the perimeter of its room
//| Author: M. B. Feldman, The George Washington University
//| Last Modified: August 2004
//--------------------------------------------------------------
import mbf.Spider;
public class TourRoom
{
  public static void main (String[] args)
  {
    Spider.start();

    while(!Spider.atWall()) // loop until spider gets to wall
    {
      Spider.step();        
    }

    for (int Wall = 1; Wall <= 4; Wall++) // step along 4 walls
    {
      Spider.turnRight();
      while(!Spider.atWall()) // loop until spider gets to wall
      {
        Spider.step();        
      }
    }
    Spider.quit();
  }
}

Sample Run of Program 13

                    ---------------------------------------
 ---               |* . . . . . . . . G G G G G G G G G G G|
| ^ |              |G . . . . . . . . G . . . . . . . . . G|
| G |              |G . . . . . . . . G . . . . . . . . . G|
 ---               |G . . . . . . . . G . . . . . . . . . G|
                   |G . . . . . . . . G . . . . . . . . . G|
                   |G . . . . . . . . G . . . . . . . . . G|
                   |G . . . . . . . . G . . . . . . . . . G|
                   |G . . . . . . . . G . . . . . . . . . G|
                   |G . . . . . . . . G . . . . . . . . . G|
                   |G . . . . . . . . G . . . . . . . . . G|
                   |G . . . . . . . . G . . . . . . . . . G|
                   |G . . . . . . . . . . . . . . . . . . G|
                   |G . . . . . . . . . . . . . . . . . . G|
                   |G . . . . . . . . . . . . . . . . . . G|
                   |G . . . . . . . . . . . . . . . . . . G|
                   |G . . . . . . . . . . . . . . . . . . G|
                   |G . . . . . . . . . . . . . . . . . . G|
                   |G . . . . . . . . . . . . . . . . . . G|
                   |G . . . . . . . . . . . . . . . . . . G|
                   |G G G G G G G G G G G G G G G G G G G G|
                    ---------------------------------------

Exercise for Section 5

1. Modify Program 13 so that the spider covers the four walls completely but does not visit any parts of the walls a second time. Hint: Count the number of steps the spider takes while touring the first wall and the number of steps in touring the third (parallel) wall.

6. The Drunken Spider

Finally, we develop a spider program that puts together everything we've learned here. Imagine that the spider discovers a large glass of beer in its room and drinks enough beer to become inebriated (a fancy word for "drunk"). The spider tries to tour its room but is too drunk to do this properly. Instead, the spider tries to take a random number of steps. If it does so without reaching a wall, it turns right, selects another random number, and resumes walking. If the spider reaches a wall, it turns around and walks in the opposite direction, completing its count in the new direction. The drunken spider appears in Program 14.

Program 14. The Drunken Spider

//--------------------------------------------------------------
//| Spider tries to tour her room but has drunk too much beer,
//| so takes a random number of steps and may hit the wall. If
//| the spider hits the wall, she turns around and keeps going.
//| Author: M. B. Feldman, The George Washington University
//| Last Modified: August 2004
//--------------------------------------------------------------
import mbf.Spider;
public class DrunkenSpider
{
  public static void main(String[] args)
  {

    Spider.start();

    for(;;)                // keep going forever
    {
      Spider.face(Spider.randomDirection());
      Spider.changeColor(Spider.randomColor());

      // Spider will count steps correctly
      // but might change direction
      int Steps = Spider.randomStep();
      for (int Count = 1; Count <= Steps; Count++)
      {
        if (Spider.atWall())
        {
          Spider.turnRight();
          Spider.turnRight();
        }

        Spider.step();
      }

      Spider.turnRight();

    }

    //Spider.quit();
  }
}

In addition to the conditional if statement, this program has another interesting characteristic. The outer loop in this program is a for(;;) statement, in which all three loop-control parts are missing. This odd-looking statement -- which, in particular, has no condition for termination -- is a conventional way to express an endless loop. The program will therefore continue indefinitely.

Most programs, including the other spider programs here, are designed to terminate after a finite number of steps; this program is an exception, similar to an "embedded" program like the one in an automatic teller machine, a car braking system, or other computer-controlled system. An embedded program generally terminates only when the equipment itself is shut off. In our case, we need not shut off the computer. Rather, in most computers, pressing the CONTROL and C keys simultaneously (usually referred to as ctrl-C) will cause the operating system to terminate your currently executing program. In the sample run of DrunkenSpider, we pressed ctrl-C to stop the program; most terminals will display this on the screen as ^C, and you can see this here at the end of the lower row of Ks.

Sample Run of Program 14

                    ---------------------------------------
 ---               |. R . . . R . . . . . . R . R . . . . .|
| ^ |              |. R . . . R . . . . . . R . R . . . . .|
| R |              |. R . . . R . . . . . . R . R . . . . .|
 ---               |. R . . . R . . . . . . R . R . . . . .|
                   |. R . . . R . . . . . . R . R . . . . .|
                   |. R . . . R . . . . . . R . K . . . . .|
                   |. R . . . R . . . . . . R . K . . . . .|
                   |. R . . . R . . . . . . R . K . . . . .|
                   |. R . . . R . . . . . . R . K . . . . .|
                   |. R . . . R K K K K K K K K K K K K G G|
                   |. R . . . R . . . G G R . . K . . . . .|
                   |. R . . . B B B B B B G G G K . . . . .|
                   |. R . . . . . . . . . . . . K . . . . .|
                   |. R K K K K K *^C K K K K K K . . . . .|
                   |. R . . . . . R . . . . . . B . . . . .|
                   |. R . . . . . R . . . . . . B . . . . .|
                   |. R . . . . . R . . . . . . B . . . . .|
                   |. R . . . . . R . . . . . . B . . . . .|
                   |. B B B B B B R . . . . . . B . . . . .|
                   |. . . . . . . . . . . . . . B . . . . .|
                    ---------------------------------------


Review

The goal of this chapter has been to get you started with developing algorithms and implementing them as programs using control structures. We introduced straight-line algorithms, as well as those with single and nested repetitive loops and with conditional execution. The spider has served as an easy-to-understand mechanism for introducing these structures; the patterns drawn by the spider gave you obvious feedback on the behavior of the spider programs.

Each structure and technique that we discuss here is covered in full detail later in this course.