2167. A Program That Rewrites Itself

A machine has an accumulator and a program of n instructions numbered from 0. The counter and the accumulator both start at 0.

ADD v add v to the accumulator, then move the counter on by 1 JMP v move the counter on by v SET i v replace the OPERAND of instruction i with v, then move the counter on by 1. Instruction i is guaranteed to be an ADD or a JMP, and its opcode is left alone. HLT stop

The machine performs at most s steps, and one step is: if the counter is outside 0 to n - 1, stop and report FAULT; otherwise execute the instruction there. Print the outcome word, one of HALT, FAULT or RUNNING, and then the accumulator, separated by a single space.

``` n = 4, s = 100: SET 2 0 / JMP 2 / JMP -1 / HLT

SET 2 0 rewrites instruction 2 from JMP -1 to JMP 0, counter 1. JMP 2 sets the counter to 3, which is the HLT, so instruction 2 is never reached and the rewrite never matters. -> HALT 0 ```

``` n = 3, s = 100: SET 1 7 / ADD 0 / HLT

SET 1 7 rewrites instruction 1 from ADD 0 to ADD 7, counter 1. ADD 7 now adds 7 rather than 0. -> HALT 7 ```

## What most people try first

Reusing the loop detection from #2164. There the counter never read anything that could change, so a repeated instruction proved the run was stuck. Here a SET can rewrite the very JMP that is about to run, so the same instruction reached twice can send control two different places. Marking instructions and stopping on a repeat gives a wrong LOOP on a program that goes on to halt, so this problem has a step budget instead and reports RUNNING honestly.

The second common slip is decoding the program once into a fixed table and then running from a separate copy. Every read of an operand must see the latest write to it, which means one mutable table and no second copy of the operands.

## Why the budget is the only honest answer

To decide looping you would have to find a repeat of the whole machine state, which here is the counter together with every operand in the program. That is n numbers of up to 10^9 in magnitude, so the state space is far beyond enumeration, and the question of whether such a program halts is exactly the kind of question a fixed budget exists to sidestep. Stating the budget in the input is what makes the problem answerable.

## The order inside a SET, which is where the bug lives

SET i v writes to instruction i and then moves the counter on by one. Two cases are worth separating:

i is the SET itself the opcode stays SET, and the guarantee in the statement rules this out: i is always an ADD or a JMP i is the NEXT instruction the write lands before that instruction runs, so the new operand is the one used i is an earlier JMP the write takes effect for every later visit, which is how a program can escape a loop it is already in

A declared test has a SET that rewrites a JMP the run later returns to, so a solution that caches operands fails it while passing the straight-line cases.

## Overflow

The accumulator is a sum of at most s operands of magnitude up to 10^9, with s up to 10^5, so it can reach 10^14. A signed 32 bit integer stops at 2147483647, so the accumulator must be 64 bit. Note that the declared test which adds 10^9 twice reaches 2000000000, and that FITS in 32 bits, so it is not tagged as an overflow: only the larger sums need the width.

## Cost

O(n + s) time and O(n) memory.

Constraints - `1 ≤ n ≤ 2000` - `1 ≤ s ≤ 100000` - each opcode is exactly `ADD`, `JMP`, `SET` or `HLT` - `-10^9 ≤ v ≤ 10^9` - `0 ≤ i < n` on a `SET`, and instruction `i` is always an `ADD` or a `JMP` - a `SET` changes only the operand, never the opcode - the counter and the accumulator both start at 0