Part 0: Copy a script

Save the file gnuplotMOD (retaining that name) into the same directory you're using for this lab. (Hint: lab04 is a nice name!) This is a little wrapper script for a utility called gnuplot. We need to set the file's permissions to "executable". After last week's lab, it's hopefully no surprise that the instruction for that is:
chmod 700 gnuplotMOD
Give the command ls -l to verify that file gnuplotMOD exists and is set to executable for you.

Part 1: Fear the turtle

I want you to create a very simple "turtle graphics" kind of program (some of your instructors grew up with one called Logo). Imagine you have a turtle that starts at point (0,0) facing due East. Then you have a sequence of instructions. In the instructions, every capital letter represents a "forward move" of one unit. The plus sign (+) represents an in-place clockwise turn of a fixed number of degrees. The minus sign (-) represents an in-place counter-clockwise turn of the same fixed number of degrees. Lowercase letters are ignored. A semicolon terminates the instructions. Imagine the turtle following these instructions while dragging a marker behind him. He traces out a path. You're going to draw that path, by printing out the turtle's coordinates after each movement and then using gnuplotMOD to display the resulting path.

The input format for the turtle's instructions has some parts that will allow us to extend this in later sections; we can ignore those parts at first. For example, consider the following two inputs:

X>X ; 45 ; -F++F++F++F ;
A > ABC ; 90 ; X++Y-J--D ;
X>X+YF , Y>FX-Y ; 90 ; X+YFFX-Y;

All the stuff before the first semicolon can be ignored by your program for this part - it could be arbitrarily long, and there may or may not be spaces around the >, but will always be ended by a single stand-alone semicolon. So, we'll have our program ignore X>X in the first example and A > ABC in the second.

The number following the first semicolon is an angle, in degrees. The text after the second semicolon is the turtle's instructions. Each + character indicates the turtle should turn right the number of degrees specified earlier. Each - character indicates it should turn left. Any capital letter means it should move forward one meter. (And remember, all lowercase letters are ignored for now.) The final semicolon means the instructions are done.

After any movement, the turtle's (x,y) coordinates should be printed out, x coordinate first, followed by a tab character ('\t' in C++), followed by the y coordinate.

So, for example, if your program's input is:

X>X ; 45 ; -F++F++F++F ;

The output should be (though there may be very small rounding errors):

0	0
0.707107	0.707107
1.41421	0
0.707107	-0.707107
0	0

Save your program in a file called turtle.cpp.

Remembering trig: Remember that if the turtle's current heading is \(\theta\), taken as the angle in radians between the positive x-axis and the current heading, and the distance of a single step is \(s\) (for us, this is 1), the changes in \(x\) and \(y\) coordinates are given by \[ \begin{array}{l} \Delta x = s \cos \theta\\ \Delta y = s \sin \theta\\ \end{array} \]

To convert an angle from degrees to radians remember the formula \(\theta_{rad}=\theta_{deg}*\pi/180\).

sin(), cos(), and M_PI are all available to you if you remember to include <cmath>.

The following picture may help you picture what's going on. Here, the input is A>A ; 30 ; X-X- ;.

Seeing your results Of course, just printing out your points isn't very exciting. Linux has a feature called "pipes," in which the text that is printed out in one program can be fed in as input to a second using the | character. The program gnuplotMOD you set up in part 0 is set up to take your program's output as its input. To set up the pipe, you would run it as follows:

$ ./turtle | ./gnuplotMOD
X>X ; 45 ; -F++F++F++F ;

In response, up would pop the following window:

Here's a more complex example:

$ ./turtle | ./gnuplotMOD 
A>A+A-A-A+A ; 90 ;

which would give us this:

What pictures can you draw?

To submit: Submit with the following instruction:

~/bin/submit -c=IC210 -p=lab04 turtle.cpp

Part 2 (Going Further): Lindenmayer Systmes (a.k.a. L-Systems) with One Rule

An L-System is a mechanism for creating sequences of symbols. In our case, L-Systems will be a mechanism for creating turtle instructions. What's particularly interesting, is that we can use L-Systems and the turtle to draw fractals, like the picture of Serpinski's Triangle shown on the right.

An L-System consists of a set of rules of the form $x \rightarrow w$, where $x$ is a symbol and $w$ is a sequence of symbols (i.e. a string). The meaning of this rule is that all occurrences of symbol $x$ in some input string are to be replaced with $w$. For example, if the rule is $$ a \rightarrow bbacabb $$ and the input string is $cababa$, the L-System produces $$ cababa \Rightarrow c\underline{a}b\underline{a}b\underline{a} \Rightarrow c\underline{bbacabb}b\underline{bbacabb}b\underline{bbacabb} $$ after a single step.

Your job for Part 2 is to write a program (call it Lsys.cpp) that reads input of the same form as from Part 1 (except that you may assume that there is a single rule in the first part of the input) and produces output that is the same as the input, except that the string in the third part of the output should be the result of applying the rule from the first part of the input to the string from the third part of the input.

~/$ ./Lsys
A>ABC ; 60 ; CAC ;
A>ABC ; 60 ; CABCC;
~/$ ./Lsys
x>FxFxF ; 80.5 ; xyyx ;
x>FxFxF ; 80.5 ; FxFxFyyFxFxF;

To submit: Submit with the following instruction:

~/bin/submit -c=IC210 -p=lab04 turtle.cpp Lsys.cpp

Part 2.5 (Going Further): Play the Pipes

You can do some really interesting things by combining the ./Lsys, ./turtle and ./gnuplotMOD programs. Try this example:
~/$ ./Lsys | ./turtle | ./gnuplotMOD
A > A+A-A-A+A ; 90 ; A;
Not a fascinating picture, but somewhat interesting. Things get more interesting, though, if you look and see what the ./Lsys part of this chain produced. Try running this example:
~/$ ./Lsys
A > A+A-A-A+A ; 90 ; A;
A>A+A-A-A+A ; 90 ; A+A-A-A+A;
The interesting thing here is that the output of ./Lsys is in the same format as the input. That means we can pipe the output of one running instance of ./Lsys into the input of another running instance of ./Lsys, like this:
~/$ ./Lsys | ./Lsys
A > A+A-A-A+A ; 90 ; A;
A>A+A-A-A+A ; 90 ; A+A-A-A+A+A+A-A-A+A-A+A-A-A+A-A+A-A-A+A+A+A-A-A+A;
This corresponds to running two steps of the L-system. If you pipe this through ./turtle and ./gnuplotMOD you get something more interesting. Of course, why stop there? You can chain together many ./Lsys instances with pipes to run even more steps of the L-system. Try this out:
$ ./Lsys | ./Lsys | ./Lsys | ./turtle | ./gnuplotMOD
A > A+A-A-A+A ; 90 ; A;

Part 3 (Going Further): L-Systems with One or Two Rules

Finally, modify your ./Lsys program so that the rule set may include one or two rules — comma-separated if there are two rules. When there are two rules, the left-hand sides of the two rules must refer to different symbols, and one step of the resulting system replaces each rule simultaneously. For example: suppose we have rules $$ X \rightarrow +X+Y-- \mbox{ and } Y \rightarrow -Y-X++ $$ and the input string is $XFY$, the L-System produces $$ XFY \Rightarrow \underline{X}F\underline{Y} \Rightarrow \underline{+X+Y--}F\underline{-Y-X++}. $$ Here are some examples of inputs and outputs for the new program which, recall, can handle both one rule and two rule inputs, so that all the Part 2 inputs should still work.
~/$ ./Lsys
F>F-G+F+F-F , G>GG ; 120 ; F-G-G;
F>F-G+F+F-F , G>GG ; 120 ; F-G+F+F-F-GG-GG;
~/$ ./Lsys
X>X+YF , Y>FX-Y ; 90 ; XY;
X>X+YF , Y>FX-Y ; 90 ; X+YFFX-Y;
When all is said and done, I encourage you to try these two inputs:
~/$ ./Lsys |./Lsys |./Lsys |./Lsys | ./turtle | ./gnuplotMOD
F>F-F++F-F ; 60 ; F++F++F ;
~/$ ./Lsys |./Lsys |./Lsys |./Lsys | ./turtle | ./gnuplotMOD
A>A-B--B+A++AA+B- , B>+A-BB--B-A++A+B ; 60 ; A ;
Once you've got it working, you might want to take a look at info 1 and info 2, which give a little background on these two pictures.

To submit: Submit with the following instruction (yes, this is the same as Part 2):

~/bin/submit -c=IC210 -p=lab04 turtle.cpp Lsys.cpp

Part 4 (Going Further): Bounding Boxes

Shapes like the previous two examples are called fractals. Ususally, we think about fractals as "filling up" a fixed region in the plane. In our examples, however, the region containing the lines we draw constantly grows as we do more and more steps of the L-system. In order to scale everything down — to fit within the unit square, for example — we have to compute the bounding box for our set of points. That is, we need to compute the smallest rectangle that contains all the points. Write a program (call it part4.cpp) that reads the output from ./turtle and prints out the coordinates of the bounding box for those points. For example:
$ ./Lsys | ./turtle | ./part4
A>A-B--B+A++AA+B- , B>+A-BB--B-A++A+B ; 60 ; A ;
Bounding box is: (0,0), (0,1.73205), (2.5,1.73205), (2.5,0).
HINT: We have the problem here of how to figure out that we've come to the end of the input, since there's no marker to tell us that's happened. Since we already learned about "end-of-file" and what happens with input streams when it's reached, you know how to do that.

To submit: Submit with the following instruction:

~/bin/submit -c=IC210 -p=lab04 turtle.cpp Lsys.cpp part4.cpp