# How to find the substitutions that convert the starting sequence into the final sequence? CCC19J5

Here is Canadian Computing Competition 2019 Junior problem 5 on dmoj.ca. You can also see the original problem at cemc.uwaterloo.ca as well.

A substitution rule describes how to take a sequence of symbols and convert it into a different sequence of symbols. For example, ABA→BBB, is a substitution rule which means that ABA can be replaced with BBB. Using this rule, the sequence AABAA would be transformed into the sequence ABBBA (the substituted symbols are in bold).

In this task, you will be given three substitution rules, a starting sequence of symbols and a final sequence of symbols. You are to use the substitution rules to convert the starting sequence into the final sequence, using a specified number of substitutions.

For example, if the three substitution rules were:

AA → AB
AB → BB
B → AA

We could convert the sequence AB into AAAB in 4 steps, by the following substitutions:

AB → BB → AAB → AAAA → AAAB,

where the symbols to be replaced are shown in bold. More specifically, from the initial sequence AB, substitute rule 2 starting at position 1, to get the result BB. From BB, substitute rule 3, starting at position 1, to get the result AAB. From AAB, substitute rule 3, starting at position 3, to get the result AAAA. From AAAA, substitute rule 1, starting at position 3, to get the result AAAB, which is the final sequence.

Input Specification

The first three lines will contain the substitution rules. Each substitution rule will be a sequence of A's and B's, followed by a space following by another sequence of A's and B's. Both sequences will have between one and five symbols.

The next line contains three space separated values, $$S$$, $$I$$ and $$F$$. The value $$S(1\le S\le 15)$$ is an integer specifying the number of steps that must be used, and the values $$I$$ (the initial sequence) and $$F$$ (the final sequence) are sequences of A's and B's, where there are at least one and at most 5 symbols in $$I$$ and at least one and at most 50 symbols in $$F$$.

For 7 of the 15 marks available, $$S\le 6$$.

For an additional 7 of the 15 available marks, $$S\le 12$$.

Output Specification

The output will be $$S$$ lines long and describes the substitutions in order.

Line $$i$$ of the output will contain three space-separated values, $$R_i$$, $$P_i$$, and $$W_i$$:

$$R_i$$ is the substitution rule number (either 1, 2 or 3) that will be used. $$P_i$$ is the starting position index of where the substitution rule will be applied in the sequence. Notice that the string is 1-indexed (i.e., the first character of the string is at index 1). $$W_i$$ is the sequence that results from this substitution. Specifically, $$W_i$$ is the sequence of symbols that results by applying substitution rule $$R_i$$ starting at position $$P_i$$ from the previous sequence of symbols, $$W_{i−1}$$, where we define $$W_0$$ to be the initial sequence $$I$$. Note that $$W_S=F$$, the final sequence.

There will always be at least one sequence of $$S$$ substitutions that will convert $$I$$ into $$F$$. If there is more than one possible sequence of substitutions, any valid sequence will be accepted.

I tried using recursion but the program isn't fast enough. Can anyone help?

• Please follow our rules for identifying copied material: cs.stackexchange.com/help/referencing. In particular, you should clearly indicate which material was copied from another source. If your question consists primarily or almost entirely of copied material, it probably isn't suitable here. – D.W. Nov 21 '19 at 3:54
• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving contest-style questions for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Nov 21 '19 at 3:55
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – D.W. Nov 21 '19 at 3:55