IDZToICE
2020 TCO Semi 2 · 2020-11-12 · by misof
Problem Statement
This task is about two simple low-level programming languages. We'll call them IDZ and ICE.
Both programming languages share the feature that we perform simple operations on registers. A register is a variable that contains a non-negative integer. (In the model these can grow arbitrarily but for the purpose of this problem standard 32-bit integers are enough.) There are 26 registers, labeled A to Z. In the beginning, registers A and B contain input values and all other registers contain zeros.
Both programming languages also share the feature that a program is a sequence of some n instructions, numbered from 0 to n-1. Execution of the program begins with instruction 0 and terminates when we get to the non-existing instruction n. The instructions used in this problem are:
- "INC x": Increment register x and continue to the next instruction.
- "DEC x": Decrement register x and continue to the next instruction.
(Decrementing a register with a zero leaves it at zero.) - "ZERO x y z": If register x contains a zero, continue to instruction y, otherwise continue to instruction z.
(The numbers y and z must be between 0 and n, inclusive. Jumping to instruction n terminates the program.) - "CLEAR x": Set register x to zero and continue to the next instruction.
- "EQUAL x y u v": If registers x and y contain the same value, continue to instruction u, otherwise continue to instruction v.
(The numbers u and v must be between 0 and n, inclusive. Jumping to instruction n terminates the program.)
The programming language IDZ only uses the instructions INC, DEC, and ZERO. The programming language ICE only uses INC, CLEAR, and EQUAL.
The output for a program in IDZ is the final value in register C (if and when the program terminates). ICE uses Z as its output register.
You are given the
The returned program may contain at most 500 instructions. The program you return is verified using black-box testing. Your answer will be considered correct if for each of the inputs generated by our grader the following holds:
- If the given program still runs after 100,000 steps of execution, yours must also still run after 100,000 steps of execution.
- If the given program terminates within 100,000 steps of execution, yours must terminate within 1,000,000 steps of execution and return the same value. (Your register Z must contain the same value as the register C for the given program.)
Notes
- During the black-box testing of your return value all test cases used will have inputs in the range [0, 10^4].
- Black-box testing is deterministic in the sense that for each input the same set of tests will be used for all submissions by all contestants.
- For the given constraints there is always at least one valid answer.
Constraints
- program will contain between 1 and 50 instructions, inclusive.
- Each instruction in program will be a valid INC, DEC, or ZERO instruction.
- Each instruction in program will only use the registers A through J.
{"INC C", "INC C", "INC C"}
Returns: {"INC Z", "INC Z", "INC Z" }
A program that always returns 3. We return a very similar ICE program that increments the correct output register three times. (Remember that ICE uses Z, not C, as its output register.)
{"INC D", "INC D"}
Returns: { }
A program that always returns 0 (as the final value in D does not matter). We return another such program: an empty program. As it doesn't have an instruction 0, its execution terminates immediately.
{"ZERO D 0 1"}
Returns: {"CLEAR A", "EQUAL K L 0 2" }
The input is an infinite cycle, we return another infinite cycle in the other language.
{"ZERO B 1 0"}
Returns: {"EQUAL B Z 1 0" }
Both programs return 0 if B = 0 and run forever otherwise.
{"ZERO A 5 1",
"DEC A",
"ZERO B 7 3",
"DEC B",
"ZERO J 0 0",
"ZERO B 6 7",
"INC C"}
Returns: {"EQUAL A B 1 2", "INC Z" }
Here is the input program with added line numbers: 0. ZERO A 5 1 1. DEC A 2. ZERO B 7 3 3. DEC B 4. ZERO J 0 0 5. ZERO B 6 7 6. INC C The program returns C = 1 if A = B and C = 0 otherwise. The reference solution returns the following (asymptotically faster) program in ICE: 0. EQUAL A B 1 2 1. INC Z
{"INC C",
"ZERO A 6 2",
"DEC A",
"INC C",
"INC C",
"ZERO A 6 2"}
Returns: {"INC C", "EQUAL A K 7 2", "EQUAL A K 4 3", "INC K", "INC C", "INC C", "EQUAL A K 7 2", "EQUAL C M 11 8", "INC M", "INC Z", "EQUAL C M 11 8" }
The given IDZ program computes the function 2*A + 1. The ICE program returned by our solution looks as follows: 0. INC C 1. EQUAL A D 6 2 2. INC C 3. INC C 4. INC D 5. EQUAL A D 6 2
{"ZERO A 5 1",
"DEC A",
"ZERO B 2 3",
"DEC B",
"ZERO J 0 0",
"ZERO B 6 7",
"INC C"}
Returns: {"EQUAL A B 3 1", "INC A", "EQUAL A B 4 1", "INC Z" }
The given IDZ program runs forever if A > B, returns 1 if A = B, and returns 0 if A < B. For each valid input with A <= B it will terminate within 100,000 steps. The ICE program returned by our solution looks as follows: 0. EQUAL A B 3 1 1. INC A 2. EQUAL A B 4 1 3. INC Z The input program runs in Theta(A) on inputs on which it terminates while the returned one runs in Theta(B-A). Even though the two programs contain different algorithms, the returned program satisfies all formal criteria from the problem statement which makes it an acceptable answer.
{"DEC A",
"ZERO A 5 2",
"DEC A",
"INC C",
"ZERO A 5 2",
"DEC B",
"ZERO B 10 7",
"DEC B",
"INC C",
"ZERO B 10 7"}
Returns: {"EQUAL A D 6 1", "INC D", "EQUAL A D 6 3", "INC Z", "INC D", "EQUAL A D 6 3", "CLEAR D", "EQUAL B D 13 8", "INC D", "EQUAL B D 13 10", "INC Z", "INC D", "EQUAL B D 13 10" }
Both the given program and the example returned program return the value (max(0,A-1) + max(0,B-1)) and they both compute it in Theta(A+B) time.
{"INC C", "DEC C", "DEC C", "INC C"}
Returns: {"INC Z" }
Remember that a register cannot be decremented below zero.
{"ZERO A 11 1", "DEC A", "ZERO B 7 3", "DEC B", "INC C", "INC D", "ZERO B 7 3", "ZERO D 0 8", "DEC D", "INC B", "ZERO D 0 8"}
Returns: {"EQUAL A K 14 1", "EQUAL A K 3 2", "INC K", "EQUAL B L 9 4", "EQUAL B L 6 5", "INC L", "INC C", "INC D", "EQUAL B L 9 4", "EQUAL D N 0 10", "EQUAL D N 12 11", "INC N", "INC B", "EQUAL D N 0 10", "EQUAL C M 18 15", "INC M", "INC Z", "EQUAL C M 18 15" }
multiplication
Submissions are judged against all 85 archived test cases, of which 10 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class IDZToICE with a public method vector<string> transform(vector<string> program) · 85 test cases · 2 s / 256 MB per case