ECOO '19 R1 P2 - L-Systems Go

View as PDF
Submit solution
Points: 5 (partial)
Time limit: 30.0s
Memory limit: 512M
Problem type

A Lindenmayer system (L-system) is a parallel rewriting system and a type of formal grammar. Some uses of L-systems include creating visual representations of vegetation, flowers, trees, and grasses.

An L-system consists of an axiom and a set of rules.

  • The axiom (A) is a string that represents the starting state of the L-system.
  • The set of rules defines what happens to each letter in an iteration of the system.

Given the axiom, set of rules, and the number of iterations for which to run the system, you are tasked with generating a two-letter code followed by the length of the final state. The two-letter code will be the concatenation of the first letter and last letter of the final state.

Input Specification

The input will contain 10 datasets. Each dataset begins with three terms R, T, A (1 \le R \le 26, 1 \le T \le 30, 1 \le |A| \le 5), the number of rules, the number of iterations, and the axiom. The next R lines each contain a character C followed by a string S (1 \le |S| \le 3) which represents a rule stating that each occurrence of C should be replaced with the string S. It is guaranteed that each letter in the system will have a corresponding rule.

For the first 4 cases, T \le 5. For the first 7 cases, T \le 12.

Output Specification

For each dataset, output a concatenation of first and last letter of the state and the length of the state after T iterations.

Sample Input (Two Datasets Shown)

3 5 AC
A CAB
B CB
C ACB
4 5 AD
A AC
B ACA
C BD
D B

Sample Output

CB 288
AB 60

Explanation of Sample Datasets

In the first dataset, the first iteration is AC > CABACB.

In the second dataset, the first two iterations are AD > ACB > ACBDACA.

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org

Comments


  • 1
    Narcariel  commented on April 29, 2020, 3:57 p.m.

    How do you fix an RTE?


    • 4
      ross_cleary  commented on April 29, 2020, 4:02 p.m.

      The string is becoming too big, that is why you get the RTE. You need to find a better solution that only keeps track of the first letter, last letter and the length, and does not store the full string.


      • 3
        Narcariel  commented on April 29, 2020, 4:04 p.m.

        Thx


  • 2
    ross_cleary  commented on April 24, 2020, 11:16 p.m.

    It may be helpful to know that the the initial string and the rules only consist of uppercase letters of the alphabet, as implied by the constraints.