// This program defines and exercises an extension to the Science of Computing
// Robot class. The extension represents robots that can draw more sophisticated
// figures than standard robots can. All the drawing algorithms use recursion, and
// in fact the real point of this class is to demonstrate recursion.
// History:
// September 2003 -- Created by Doug Baldwin.
import geneseo.cs.sc.Robot;
import geneseo.cs.sc.RobotRoom;
class DrawingRobot extends Robot {
// Initialize a drawing robot at a particular place in a particular room.
public DrawingRobot( int column, int row, int heading, RobotRoom room ) {
super( column, row, heading, room );
}
// The pyramid method makes a robot draw a pyramid n levels high. The algorithm
// is based on the recursive insight that an n > 1 level pyramid consists of
// a tile at the lower left corner, a tile at the lower right corner, and an
// (n-1)-level pyramid in between. A pyramid of 1 level is just a single tile.
// Preconditions: The robot is standing where the lower left tile of the
// pyramid should be, facing up (relative to the pyramid).
// Postconditions: The robot is standing on the lower right tile of the
// pyramid, facing down.
// Correctness proof: The proof is by induction on n.
// Base Case: n = 1. The n > 1 test fails, so the algorithm
// executes the "else" arm of its conditional. This paints the
// tile the robot is standing on (by the precondition, the
// lower left, and only, tile of the pyramid) red, and turns
// the robot to face down. The robot is still standing on the
// only, and so also lower right, tile of the pyramid.
// Induction Hypothesis: For some k-1 >= 1, pyramid(k-1)
// draws a (k-1) level pyramid, and leaves the robot standing
// on its lower right tile, facing down.
// Show that pyramid(k) draws a k level pyramid, and leaves
// the robot standing on its lower right tile, facing down. Since
// k-1 >= 1, k > 1 and the "n > 1" test passes. The algorithm
// therefore paints the tile the robot starts on red, then moves
// the robot diagonally up and right, leaving it facing up. The
// recursive message causes the robot to draw a k-1 level pyramid,
// by the induction hypothesis. Since this pyramid begins 1 tile
// above and right of the one the robot colored at the beginning,
// that tile serves as the lower left corner of a kth level.
// Furthermore, since the robot finishes drawing the k-1 level
// pyramid standing on that pyramid's lower right tile and facing
// down, the moves and turns after the recursive message put the
// robot one tile diagonally below and right of the k-1 level
// pyramid. Painting that tile red makes it the lower right corner
// of a k level pyramid, whose lower left corner is the tile painted
// before the recursion.
public void pyramid( int n ) {
if ( n > 1 ) {
this.paint( java.awt.Color.red );
this.move();
this.turnRight();
this.move();
this.turnLeft();
this.pyramid( n - 1 );
this.move();
this.turnLeft();
this.move();
this.turnRight();
this.paint( java.awt.Color.red );
}
else {
this.paint( java.awt.Color.red );
this.turnLeft();
this.turnLeft();
}
}
// colorfulLine makes a robot draw a line 2n+1 tiles long, with the first
// n tiles blue, the middle tile yellow, and the last n tiles red. The
// algorithm is based on the recursive insight that for n > 0, such a
// line consists of a blue tile, an (n-1)-tile colorful line, and finally
// a red tile. A 0-tile line consists of just a yellow tile.
// Preconditions: The robot is standing on what will be the first tile
// of the line, facing in the direction the line should grow.
// Postconditions: The robot is standing on the last tile in the line,
// facing in its original direction.
// Correctness proof: The proof is by induction on n.
// Base Case: n = 0. The "n > 0" test fails, so the algorithm paints no
// blue tiles, one yellow tile, and no red tiles, i.e., a size-0 colorful line.
// The robot is standing on the yellow tile, i.e., the last tile of the line,
// and is still facing in its original direction.
// Induction Hypothesis: For some k-1 >= 0, colorfulLine( k-1 ) draws a line
// consisting of k-1 blue tiles, one yellow, and k-1 red, and leaves the robot
// standing on the last tile, facing in its original direction.
// Show that colorfulLine(k) draws a line of k blue tiles, 1 yellow, and k
// red, leaving the robot standing on the last tile and facing in its original
// direction. Since k-1 >= 0, k > 0 and so the "n > 0" test succeeds. The algorithm
// proceeds to paint one tile blue and move forward. It then sends itself a
// "colorfulLine(k-1)" message. By the induction hypothesis, this message draws
// k-1 blue tiles, 1 yellow, and k-1 red, starting where the robot was standing
// upon receiving the "colorfulLine(k-1)" message. Since this was on the tile
// after the one the robot initially painted blue, there are a total of k blue
// tiles, one yellow, and k-1 red. The robot is standing on the last red tile.
// The move and paint messages that the robot sends itself after the recursion
// therefore move the robot to the tile after the k-1 red ones, and paint that
// tile red, so that now the robot has drawn k blue tiles, 1 yellow, and k red.
// The robot remains standing on the last red tile, and never turns, so it is
// always facing in its original direction.
public void colorfulLine( int n ) {
if ( n > 0 ) {
this.paint( java.awt.Color.blue );
this.move();
this.colorfulLine( n - 1 );
this.move();
this.paint( java.awt.Color.red );
}
else {
this.paint( java.awt.Color.yellow );
}
}
// halfwayBack makes a robot move forward until it comes to a wall, painting
// tiles green as it moves. At the wall, the robot turns around and comes
// back halfway to its starting point, painting tiles yellow as it moves.
// More precisely, if the robot starts with n tiles between it and the wall
// (n = 0 if the robot is next to the wall), then the robot ends with floor( n/2)
// tiles between it and the wall, and facing away from the wall. The algorithm is
// based on the recursive insight that if there are 0 or 1 tiles between the
// robot and the wall, then all it has to do is move as far as it can and
// then turn around. Otherwise, it should move two tiles, then move to the
// wall and halfway back, and finally move one more tile away from the wall.
// Correctness proof: the proof is by induction on n, the number of tiles initially
// between the robot and the wall. I use the terminology "floor(x)" to mean x
// rounded down to an integer. With this terminology, the postcondition on the robot's
// position can be phrased as "there are floor(n/2) tiles between the robot and
// the wall."
// Base Case 1: n = 0. In this case, it is not OK for the robot to move, and so
// the algorithm just turns the robot around. The robot is now facing away from the
// wall. There are still 0 tiles between the robot and the wall, and 0 equals
// floor(0/2). No tiles have been painted, which is equivalent to saying that the
// 0 tiles between the wall and the robot's final position have been painted yellow,
// and the remaining 0 tiles between the yellow ones and the robot's initial position
// have been painted green.
// Base Case 2: n = 1. In this case it is initially OK to move, so the robot moves
// one tile forward and paints the tile it comes to green. It is now not OK to move,
// so the second "okToMove" test fails, so the robot turns around and the algorithm
// ends. At this point there are 0 = floor(1/2) tiles between the robot and the wall,
// 0 tiles have been painted yellow, and the one remaining tile between the wall and
// the root's initial position is green. The robot is facing away from the wall.
// Induction Hypothesis. Assume that for some k-2 >= 0, halfwayBack moves a robot
// with k-2 tiles between it and the wall forward to that wall and back to a position
// where there are floor( (k-2)/2 ) tiles between the robot and the wall; paints the
// tiles between the wall and the robot's final position yellow; paints all other
// tiles between the wall and the robot's initial position green; and leaves the robot
// facing in the opposite of its original direction.
// Show that halfwayBack also moves a robot with k tiles between it and the wall
// forward to that wall and back to a position where there are floor( k/2 ) tiles
// between the robot and the wall; paints the tiles between the wall and the robot's
// final position yellow; paints all other tiles between the wall and the robot's initial
// position green; and leaves the robot facing in the opposite of its original direction.
// Since k-2 >= 0, k >= 2, so both "okToMove" tests in the algorithm succeed. The robot
// therefore moves two tiles forward, painting both of the tiles it comes to green. There
// are now k-2 tiles between the robot and the wall. Thus the recursive "halfwayBack"
// message moves the robot to the wall and back to a position where there are floor( (k-2)/2 )
// tiles between the robot and the wall, paints those tiles yellow, and leaves the
// robot facing away from the wall. The robot paints the tile it is standing on yellow,
// then moves off that tile, and the algorithm ends. Thus all tiles between the robot's
// final position and the wall are yellow. The robot's final position has
// floor( (k-2)/2 ) + 1 tiles between it and the wall. The 1 can be moved into
// the "floor" (you can move integer addends into and out of "floor" operations), so the
// number of tiles between the wall and the robot's final position can also be
// expressed as
// floor( (k-2)/2 + 1 )
// = floor( k/2 - 2/2 + 1 )
// = floor( k/2 )
// All tiles from the robot's final position to (but not including) its starting
// position are still green, and the robot is still facing away from the wall.
public void halfwayBack() {
if ( this.okToMove() ) {
this.move();
this.paint( java.awt.Color.green );
if ( this.okToMove() ) {
this.move();
this.paint( java.awt.Color.green );
this.halfwayBack();
this.paint( java.awt.Color.yellow );
this.move();
}
else {
this.turnLeft();
this.turnLeft();
}
}
else {
this.turnLeft();
this.turnLeft();
}
}
// The main method creates a drawing robot and demonstrates some of the
// things it can do.
public static void main( String args[] ) {
RobotRoom testRoom = new RobotRoom( "14 15" );
// Test colorful lines in both the base case and a non-base case:
DrawingRobot line1 = new DrawingRobot( 1, 13, Robot.NORTH, testRoom );
DrawingRobot line2 = new DrawingRobot( 2, 13, Robot.NORTH, testRoom );
line1.colorfulLine( 0 );
line2.colorfulLine( 5 );
// Test pyramids in both their base case and a non-base case:
DrawingRobot pyramid1 = new DrawingRobot( 3, 13, Robot.NORTH, testRoom );
DrawingRobot pyramid2 = new DrawingRobot( 4, 13, Robot.NORTH, testRoom );
pyramid1.pyramid( 1 );
pyramid2.pyramid( 3 );
// Test halfwayBack in both of its base cases, and in both even and odd
// non-base cases:
DrawingRobot halfway1 = new DrawingRobot( 9, 1, Robot.NORTH, testRoom );
DrawingRobot halfway2 = new DrawingRobot( 10, 2, Robot.NORTH, testRoom );
DrawingRobot halfway3 = new DrawingRobot( 11, 12, Robot.NORTH, testRoom );
DrawingRobot halfway4 = new DrawingRobot( 12, 13, Robot.NORTH, testRoom );
halfway1.halfwayBack();
halfway2.halfwayBack();
halfway3.halfwayBack();
halfway4.halfwayBack();
}
}