Part 0: Copy a script

Save the file gnuplotMODX (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 gnuplotMODX
Give the command ls -l to verify that file gnuplotMODX exists and is set to executable for you.
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. 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 semi-colon terminates the instructions. Imagine the turtle following these instructions while dragging a marker behind him. He traces out a path. Our job is to draw the path.

We're going to use a utility called gnuplot to actually draw the lines for us. Our job is to simulate the turtle following directions and output the XY coordinates of the points he vists. We'll use a very simple format where each line of output consists of an x-coordinate followed by a tab character ('\t') followed by a y-coordinate. If we pass data like that to gnuplot, it will draw our picture for us. To do this, we'll use a very cool Unix idea called "pipes". To see this in action, try the following command in the command shell:

echo -e "0 0\n1 1\n2 0" | ./gnuplotMOD 
This command uses "echo" to write string "0 0\n1 1\n2 0" to standard output. The "|" tells the shell to "pipe" that output into the input of the program ./gnuplotMOD, which reads these points and draws two lines — one from (0,0) to (1,1) and another from (1,1) to (2,0). When you run your Part 1 lab solution, you'll run it the same way: pipe the output to ./gnuplotMOD.

Here are the input and output specifications: Here's a few example inputs and outputs:
$ ./turtle
X>X ; 45 ; -F++F++F++F ;
0	0
0.707107	0.707107
1.41421	0
0.707107	-0.707107
0	0
$ ./turtle | ./gnuplotMOD
X>X ; 45 ; -F++F++F++F ;
The figure to the right shows the output of ./gnuplotMOD. Just to make sure we're all on the same page mathwise: if the turtle's current heading is $\theta$, taken as the angle between the positive x-axis and the current heading, and the distance of a single step is $d$, the change in $x$ and $y$ coordinates are given by $$ \begin{array}{l} \Delta x = d \cos \theta\\ \Delta y = d \sin \theta\\ \end{array} $$
Note: remember to #include <cmath> so that the sin() and cos() functions are available to you!
You can actually draw some quite lovely pictures this way. Here's an example of a nice pattern:
$ ./turtle | ./gnuplotMOD 
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+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;

The picture below should give yhou some idea of how this works. The input sequence is X-X-, with a turn angle of 30 degrees.

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 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;

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.

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 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. Tomorrow in class we'll learn the "right way" to do that. However, for now, you can try this: if you set both the x and the y variables you read in to some random crazy value like .123456789 before you do the read, then after the read they will almost certainly never have exactly the value .123456789 unless the read failed because you came to the end of the input. This allows you to check for end of input pretty reliably ... in this case! Like I said, tomorrow we'll learn to do this right.