OneInstructionOnly
TCO21 Algo Semi 2 · 2021-11-12 · by misof
Problem Statement
Assembly languages usually have a small collection of instructions to add, compare, store data into memory, and so on.
But some instructions are so powerful that a single instruction is enough to write any program at all.
The memory of our program is a finite array memory[0..M-1]. Each element of memory is an integer. (Initially these integers must be non-negative and small, but during the run of your program they may become negative and/or big.)
The content of this memory is both your program and your data.
The only instruction you can use in your program is the instruction "take one cell of memory, subtract the value of another cell from it, and if the result is zero or negative, jump".
Each instruction takes three arguments: three indices into memory. Thus, usually a program is a sequence of triples of integers (but much wilder things including self-overwriting programs are possible).
Here is a full interpreter of this language, written in Python. The input is a sequence of integers: the initial content of the array memory[].
#############################################################
import sys
memory = [ int(x) for x in sys.stdin.read().split() ]
try:
while True:
ip = memory[0]
a, b, c = memory[ip], memory[ip+1], memory[ip+2]
memory[a] -= memory[b]
if memory[a] <= 0: memory[0] = c
else: memory[0] += 3
except:
print( memory[1] )
#############################################################
Explanation:
The cell memory[0] stores the instruction pointer (below also denoted "ip").
The execution of your program is a potentially infinite loop that looks as follows.
- Look at memory[0] to read the current ip.
- Look at the values a = memory[ip], b = memory[ip+1], and c = memory[ip+2].
- Subtract memory[b] from memory[a].
- If memory[a] is now zero or negative, set ip to c (jump to that address), otherwise increment ip by 3 (move to the next triple).
Execution ends if your program tries to access a value outside the existing memory. The output is the value memory[1] at the end of the run.
----------------------------
Your task is to implement exponentiation (more precisely, a very small number taken to a moderately large power) in this "programming language".
You are given integers A and B.
Construct and return any
- memory[] must have between 2 and 70 elements, inclusive.
- Initially, each element of memory[] must be between 0 and 20,000, inclusive.
- When executed on your memory[], the interpreter must terminate in at most 200,000 steps.
- During the execution of the program the values in your memory must not underflow -(10^5000) or overflow 10^5000.
- The returned value must be A to the power of B.
Notes
- The step during which your solution makes an invalid memory access and terminates is not counted.
Constraints
- A will be between 0 and 7, inclusive.
- B will be between 1 and 20,000, inclusive.
- A to the power of B will not exceed 10^5000.
7
1
Returns: {42, 7 }
The program is supposed to return 7^1 = 7. Our program will finish in 0 steps: already in the beginning the instruction pointer points outside our memory, so the program terminates and the value memory[1] = 7 is returned.
3
7
Returns: {4, 2185, 1, 0, 3, 2, 8, 1000, 1, 3, 0, 1, 3, 0, 4242 }
This program will execute three steps and then terminate. The very first step looks as follows: We have ip = 4. We take a=memory[4], b=memory[5], c=memory[6]. We have a=3, b=2, c=8. We subtract memory[b] from memory[a]. Thus, memory[3] is now equal to 0 - 1 = (-1). As the new value is <= 0, we set ip to c = 8. Memory now looks as follows: {8, 2185, 1, -1, 3, 2, 8, 1000, 1, 3, 0, 1, 3, 0, 4242 } Second step: As ip=8, we take a=memory[8], b=memory[9], and c=memory[10]. We then perform memory[a] -= memory[b], and as the result is positive, we don't jump: ip is incremented from 8 to 11. Third step: As ip=11, we take a=memory[11], b=memory[12], and c=memory[13]. Again we subtract, again the result is positive, and so ip is incremented to 14. Attempted but not executed fourth step: As ip=14, we try to take a=memory[14], b=memory[15], and c=memory[16]. The indices 15 and 16 are not valid indices into memory, thus the execution of our program terminates after three steps, and the current content of memory[1] is returned. Note that even if memory did have two more cells, the program would still terminate here, as now a=4242 is not a valid index into memory.
1
1
Returns: {42, 1 }
1
1000
Returns: {42, 1 }
7
1
Returns: {42, 7 }
Submissions are judged against all 103 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class OneInstructionOnly with a public method vector<int> program(int A, int B) · 103 test cases · 2 s / 256 MB per case