Line Automaton
A row automaton, named «Homer-2015», processes an input string of characters and outputs a transformed string based on a predefined set of replacement rules. Each rule specifies a substring to be replaced and the string that will replace it. The automaton operates as follows: it scans the list of rules to find the first applicable one, replaces the first occurrence of the specified substring in the current string, and then starts over. This process repeats until no more replacements can be made, at which point the automaton returns the final string. The collection of replacement rules is referred to as the program, and the count of these rules is the program size. The total number of replacements performed on a given input is called the number of operations.
For example, consider the automaton receiving the string abcbca with a program of size 2: 1) bac → c and 2) bc → cba. The automaton's operations proceed as follows:
The initial string is abcbca.
The substring bac from the first rule is not found in abcbca, so the automaton checks the second rule.
The substring bc from the second rule is found, so it is replaced with cba, and the process restarts.
The new string is acbabca.
Again, bac is not found, so the automaton checks the second rule.
The substring bc is found and replaced with cba, and the process restarts.
The new string is acbacbaa.
This time, bac is found and replaced with c, and the process restarts.
The new string is accbaa.
Neither bac nor bc are found, so the automaton concludes.
The final string is accbaa.
Thus, starting with abcbca, the automaton produces accbaa. The number of operations performed is 3: replacing bc with cba twice, and then bac with c.
Task
Develop programs for the row automaton to solve various string transformation tasks as described below. For each subtask, submit only the program text. You will receive full points for a subtask if the program passes all tests, or zero if any test fails.
Constraints
Each rule's search substring and replacement string must not exceed 10 characters individually (though combined they can be longer); the replacement string can be empty, but the search substring cannot. The automaton can use digits, lowercase and uppercase Latin letters (treated as distinct symbols), and the "plus" symbol (+). These symbols can be used in both search and replacement strings for all subtasks. A program's size cannot exceed 100. For any input, the number of operations must not exceed 1000.
Verification using the emulator
An emulator program is available for download to simulate the row automaton and provide additional execution details. To use it, place the emulator in a separate directory, create a file named program.txt with your program, and a file named input.txt with the input string (a newline at the end is optional). Run the emulator, which will generate the following files:
- !output.txt: contains the automaton's output string (if the program or input is incorrect, or if operations exceed the limit, this file will not be created or will be deleted). - !debug.txt: lists the string's state after each operation (if the program or input is incorrect, this file will not be created or will be deleted; if operations exceed the limit, it will contain the string's state up to that point). - !info.txt: the first line indicates if the program and input are correct (and why if not); if correct, the second line shows the number of operations, the third line shows the program size, and the fourth line shows the lengths of the longest search and replacement strings.
The emulator accepts up to four command line parameters: limits on the number of operations, program size, search string length, and replacement string length. For example, running auto.exe 2000 100 15 sets the operation limit to 2000 (instead of 1000); the program size limit remains standard (100); the search string length limit is set to 15; the replacement string length limit remains standard (10).
Subtask 1 (5 points)
The input is a string of digits with a length from 1 to 20 inclusive. The output should be the same digits sorted in ascending order. Example: 9101→0119.