2168. An Address Held in a Register

A machine has four registers numbered 0 to 3, all starting at 0, a memory of m cells numbered 0 to m - 1 whose starting values are given, and a program of n instructions numbered from 0. The counter starts at 0.

LOAD r a copy memory cell a into register r LOADI r t copy the memory cell whose NUMBER is held in register t into register r STOREI t r copy register r into the memory cell whose NUMBER is held in register t ADD r v add v to register r JNZ r v if register r is not 0, move the counter on by v, otherwise by 1 HLT stop

Every instruction except JNZ and HLT moves the counter on by 1.

The a on a LOAD is guaranteed to be a real cell number. The register holding the address on a LOADI or a STOREI is NOT: a register is just a number, so it can hold anything. If the address it holds is below 0 or at least m, the instruction does not execute, nothing changes, and the run stops with FAULT.

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 two lines. The first is the outcome word, one of HALT, FAULT or RUNNING. The second is all m memory cells in order, separated by single spaces.

``` n = 3, m = 4, s = 100, memory 7 8 9 10 LOAD 0 2 / STOREI 1 0 / HLT

LOAD 0 2 puts 9 into register 0. STOREI 1 0 writes register 0 into the cell numbered by register 1, which is still 0, so cell 0 becomes 9. -> HALT 9 8 9 10 ```

``` n = 3, m = 2, s = 100, memory 5 6 ADD 0 -1 / LOADI 1 0 / HLT

register 0 becomes -1, and LOADI 1 0 wants the cell numbered -1. -> FAULT 5 6 ```

## What most people try first

Indexing the memory array with whatever the register holds. In C and C++ a negative index reads whatever happens to sit before the array, so the program prints a plausible wrong answer. In Python a negative index silently reads from the END of the list, which is worse, because it is well defined and still wrong: on the second worked example memory[-1] is 6, and the run would continue to a HALT instead of faulting.

So the bound has to be tested before the access, both ends of it, and the answer to "is this address legal" is 0 <= address < m and nothing looser.

## Why the fault must leave memory alone

A STOREI with a bad address is refused, so the memory printed afterwards is exactly what the previous instruction left. Checking the bound after writing, or writing to a clamped address, changes the second line of the output as well as the first. One declared test is a STOREI that walks its address up through the whole memory and one cell past the end, so the memory printed shows every legal write and none beyond.

## Why LOAD and LOADI must be told apart by their whole names

LOAD is a prefix of LOADI. A decoder that compares a fixed number of characters, or switches on the first letter, treats them as the same instruction. In this bank a C solution that tested only the first letter of an opcode silently failed every C test on one problem while passing the other four languages, because set and sub share an s. Compare whole words.

## Overflow

A register is a sum of up to s operands of magnitude 10^9, with s up to 10^5, so it can reach 10^14, far outside a signed 32 bit integer whose top is 2147483647. Registers and memory cells must be 64 bit. Note that this makes an address held in a register potentially enormous, which is another reason the bound test cannot be a single comparison against m.

## Cost

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

Constraints - `1 ≤ n ≤ 2000` - `1 ≤ m ≤ 2000` - `1 ≤ s ≤ 100000` - each opcode is exactly `LOAD`, `LOADI`, `STOREI`, `ADD`, `JNZ` or `HLT` - every register number is 0, 1, 2 or 3, and all four start at 0 - `-10^9 ≤ v ≤ 10^9`, and every starting memory value is in the same range - the `a` on a `LOAD` satisfies `0 ≤ a < m`; an address held in a register does not have to - an instruction with an out of range address does not execute and stops the run