Macros
TCCC '03 Round 2 · 2003-02-26 · by brett1479
TCCC '03 Round 2 · 2003-02-26 · by brett1479 · Dynamic Programming
Problem Statement
Problem Statement
You have been working with a macro processor that has rules of the following form:
S => replace S with aA => aA => replace A with Sb => aSb => replace S with ab => aabb
or perhaps
S => replace S with ab => ab.
These are just two possible sequences of actions out of an infinite number of possible sequences that the processor could follow with the above rules. Our problem is, we have only been given the output and are clueless as to the initial input. Given the rules of the processor, and the output text, your method will return all of the Variable Characters that could have produced the given output, in lexicographic ('A' to 'Z') order. Using the rules in the above example, if given output "aabb", your method would return {"D","S"}.
VarChar : VarOrTextChar VarOrTextChar where VarChar is an uppercase letter, and VarOrTextChar is an uppercase or lowercase letterThe macro processor only recognizes 2 kinds of characters, namely Variable Characters (uppercase letters) and Text Characters (lowercase letters). If it finds a Variable Character in the text that matches the left side of one of its rules it can replace it with the characters on the right side of that rule. If more than one rule has a left side that matches, the processor can arbitrarily choose which rule to use. This process continues until the processor gets rid of all the Variable Characters. For example, let's say the processor had the following rules:
rules = {"S:aA",
"A:Sb",
"S:ab",
"D:aA"}
Then given the string "S" it could do the following actions:S => replace S with aA => aA => replace A with Sb => aSb => replace S with ab => aabb
or perhaps
S => replace S with ab => ab.
These are just two possible sequences of actions out of an infinite number of possible sequences that the processor could follow with the above rules. Our problem is, we have only been given the output and are clueless as to the initial input. Given the rules of the processor, and the output text, your method will return all of the Variable Characters that could have produced the given output, in lexicographic ('A' to 'Z') order. Using the rules in the above example, if given output "aabb", your method would return {"D","S"}.
Constraints
- rules will contain between 1 and 50 elements, inclusive.
- Each element of rules will have 4 characters.
- The first character of each element of rules will be an uppercase letter ('A'-'Z').
- The second character of each element of rules will be a colon (':').
- The third and fourth characters of each element of rules will be uppercase or lowercase letters ('A'-'Z','a'-'z').
- output will have between 2 and 50 characters, inclusive.
- output will contain only lowercase letters ('a'-'z').
Examples
0)
{"S:aA",
"A:Sb",
"S:ab",
"D:aA"}
"aabb"
Returns: { "D", "S" }
This is the example from the problem statement.
1)
{"S:aA",
"A:Sb",
"S:ab",
"D:aA"}
"ab"
Returns: { "S" }
The only way to produce "ab" is to start with "S" and immediately replace "S" with "ab", using the third rule.
2)
{"S:aA",
"A:Sb",
"S:ab",
"D:aA"}
"aaaaabbbb"
Returns: { }
3)
{"A:aB",
"C:dE",
"Z:FG",
"B:dd"}
"qqqq"
Returns: { }
4)
{"A:aB",
"C:dE",
"Z:FG",
"B:dd"}
"add"
Returns: { "A" }
Submissions are judged against all 48 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Macros with a public method vector<string> whichOnes(vector<string> rules, string output) · 48 test cases · 2 s / 256 MB per case