// 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(); } }