March 5, 2005
     

Program / Task Name:

   L-Systems Part 1 / String Rewriting

Level:

 

 Novice / Advanced

Point Value:

 

 7

Solution(s):

 

 prob06.c

Data File(s):

 

 prob06.in

 
C programmers: your program name must be: prob06.exe
JAVA programmers: your program name must be: prob06.class

 

Task Description

In 1968, biologist Aristid Lindenmayer proposed a mathematical formalism, called L-Systems, as part of a theory of biological development. Today L-systems are used in many computer graphics applications, including fractal generation and plant modeling. You will write a program implementing the first aspect of L-Systems: string rewriting.

The program will use substitution rules to rewrite strings. Lines that begin with upper-case letters are replacement rules, which indicate how capital letters in the source string should be transformed in the result. Lines that begin with lower-case letters are program parameter values. The initial source string is labeled with a lower-case w, and the number of substitution loops with a lower-case n. Any letter or punctuation that does not have a substitution rule should remain unaltered in the result.

 

Program Input (prob06.in)

The input file (prob06.in) will contain values for n and w, and one or more substitution rules.

 

Example 1.

n=2

w=L

L=L+R+

R=-L-R

 

Example 2.

n=3

w=L

L=L+R+

R=-L-R

 

Program Output

The program should execute n substitution loops, starting from source string w, and print the final result string.  You may assume that all strings will be less than 1024 characters in length.  Three examples are given below for different values of n in the input file.

Example 1.

L+R++-L-R+

Example 2.

L+R++-L-R++-L+R+--L-R+

 

 

   
  (c) 2005 Hewlett-Packard Company