Registers, a Branch, and a Step Budget
A machine has k registers, numbered 0 to k - 1, all starting at 0, and a
program of n instructions, numbered 0 to n - 1. The program counter starts
at 0.
ADD r v add v to register r, then move the counter on by 1
JNZ r v if register r is not 0, move the counter on by v,
otherwise move it on by 1
HLT stop
The machine performs at most s steps. One step is exactly this, in this
order:
if the counter is outside 0 .. n-1, stop and report FAULT
otherwise execute the instruction at the counter
Print one line: the word HALT if a HLT executed, FAULT if the counter
left the program, or RUNNING if the budget of s steps ran out first,
followed by all k registers in order, separated by single spaces.
``` n = 4, k = 2, s = 100: ADD 0 1 / ADD 1 -1 / JNZ 1 -2 / HLT
register 1 is -1 after the first pass and never returns to 0, so the branch is taken every time and the HLT is never reached. The budget stops it: 100 steps are three per pass, so 33 full passes and one more ADD. -> RUNNING 34 -33 ```
``` n = 1, k = 1, s = 1: ADD 0 5
step 1 executes the ADD and leaves the counter at 1, which is outside the program. There is no step 2 in which to notice, so the run is RUNNING and not FAULT. -> RUNNING 5 ```
## What most people try first
A while loop with no budget, which hangs on the first worked example, and
then a budget bolted on afterwards in the wrong place. The second worked
example is why the place matters: noticing the counter has left the program
costs a step, so a counter left outside by the very last affordable step is
reported as RUNNING. That is a choice, and a problem that does not make it is
unanswerable rather than clever, so it is written into the statement and one
declared test pins it.
## Why the budget cannot be replaced by loop detection
In #2164 no instruction read the accumulator, so the counter sequence was fixed
and a repeat settled the question. Here JNZ reads a register, so the same
counter can behave differently on two visits: in the first worked example
instruction 2 is reached 33 times and branches every time, but a different
program could branch on one visit and fall through on the next. The state that
would have to repeat is the counter together with all k registers, and
registers hold values up to 10^9 in magnitude, so that state space is far too
large to enumerate. A budget is the honest answer, and it is why s is part of
the input rather than something a solution invents.
## Counting steps exactly
The three outcomes are mutually exclusive and the order above decides them.
Executing a HLT consumes a step, and so does the check that reports a fault.
A branch taken and a branch not taken cost the same single step. With those
settled, the run is a plain loop of at most s iterations.
## Overflow
A register is a sum of at most s operands, each up to 10^9 in magnitude,
with s up to 10^5. So a register can reach 10^14, far outside a signed 32
bit integer, whose top is 2147483647. Registers must be 64 bit. The declared
test that adds 10^9 three times reaches 3000000000, which a 32 bit build
prints as -1294967296.
## Cost
O(n + s) time and O(n + k) memory.