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 String[] program: a program in the language IDZ that only uses the registers A to J. Return any program in the language ICE that meets the specifications listed below.
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.)
Definition
- Class:
- IDZToICE
- Method:
- transform
- Parameters:
- String[]
- Returns:
- String[]
- Method signature:
- String[] transform(String[] program)
- (be sure your method is public)
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.
Examples
{"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{"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.