The One Change That Makes It Halt
A program of n instructions, numbered 0 to n - 1, runs on the machine of
#2164: the counter and the accumulator start at 0,
ACC v add v to the accumulator, counter on by 1
JMP v counter on by v
NOP v counter on by 1, ignoring v
and the program HALTS when the counter is exactly n. A counter below 0 or
above n is a fault and is not a halt.
The program as given never halts. That is a guarantee about the input, not something to check.
Exactly one instruction must be changed, and the only change allowed is to swap
an opcode between JMP and NOP, keeping its operand. An ACC cannot be
changed. Find the SMALLEST index whose swap makes the program halt, and print
that index and the accumulator at the moment it halts, separated by a single
space. If no single swap makes it halt, print NONE.
``` 9 instructions: 0 NOP 0 1 ACC 1 2 JMP 4 3 ACC 3 4 JMP -3 5 ACC -99 6 ACC 1 7 JMP -4 8 ACC 6
as given: 0, 1, 2, 6, 7, 3, 4, 1, and 1 has already run, so it loops. swapping instruction 7 from JMP to NOP gives 0, 1, 2, 6, 7, 8, then the counter is 9, which is n, so it halts. The accumulator collected 1 at instruction 1, 1 at instruction 6 and 6 at instruction 8. -> 7 8 ```
``` 6 instructions: 0 ACC 1 1 NOP 4 2 ACC 2 3 JMP -2 4 ACC 4 5 JMP -3
as given it loops around 1, 2, 3. Swapping 1 to JMP sends the counter to 5, which loops back to 2. Swapping 3 to NOP sends it to 4 and then 5, which loops back to 2. Neither halts, and no other instruction on the path can be swapped. -> NONE ```
## What most people try first
Trying every instruction and rerunning the whole program each time, which is
O(n^2) and is perfectly fine at n = 2000. It is also the right first
answer, and the reference solution does exactly that. The interesting part is
why a linear solution exists and what makes it correct, because the argument is
short and the shortcut is wrong without it.
## The faster argument
Two facts, each cheap to compute:
PATH the instructions the unchanged program actually executes. It never
repeats one, so PATH has at most n entries and one pass finds it,
along with the accumulator on arriving at each.
REACH the instructions from which control reaches the halt in the UNCHANGED
program. One backward walk from the halt over the reversed control
flow graph finds all of them.
Changing an instruction that is not on PATH changes nothing: the two runs
coincide step by step and neither ever touches it. So only instructions on PATH
are candidates, in index order. For a candidate i, the swap sends control to
a new target t, and from t onwards every instruction is unchanged, so the
modified program halts exactly when t is the halt itself or t is in REACH.
## Why the guarantee is load bearing
Following unchanged edges from t is only the same as running the modified
program if that walk never arrives back at i, because at i the modified
program would take the other branch. Suppose it did arrive at i and still
reached the halt. Then i is in REACH. But i is on PATH, and the walk from
any instruction is determined, so if i reached the halt then the unchanged
program would halt. The statement guarantees it does not. So no instruction on
PATH is in REACH, and the walk from t cannot pass through i.
Drop the guarantee and the shortcut breaks. For the one instruction program
NOP 0, which halts as given, REACH holds instruction 0; the swap to JMP 0
loops forever, and the reachability test would wrongly report a halt. That is
exactly why the guarantee is stated rather than assumed.
## Overflow
With up to 2000 instructions and operands up to 10^9, the accumulator can
reach 2 * 10^12, which is past the 2147483647 a signed 32 bit integer
holds, so it must be 64 bit. The declared test whose answer is 2000000000
still FITS in 32 bits and is therefore not tagged as an overflow.
## Cost
O(n^2) for the direct version, or O(n) for the reachability version, and
O(n) memory either way.