Repair a looping bootloader program

A tiny bootloader stores its program as a list of text instructions. Each entry has the form "<op> <value>", where value is a signed integer. The machine has one accumulator, which starts at 0, and a program counter pc, which starts at index 0.

• plus x: add x to the accumulator, then go to pc + 1.
• next x: do nothing (the value is ignored), then go to pc + 1.
• jump x: go to pc + x.

The program terminates when pc becomes exactly len(instructions). Landing on any other index outside the program is a crash.

Part 1

Implement find_loop(instructions: list[str]) -> tuple[int, int]. Run the program until it is about to execute some instruction for the second time. Return the index of that instruction and the accumulator value at that moment, before the repeated instruction runs.

Part 2

The program loops because exactly one instruction is corrupted: a next was changed into a jump, or a jump was changed into a next (the value was kept). plus instructions are never corrupted.

Implement repair(instructions: list[str]) -> int. Change one instruction back so the program terminates, and return the accumulator value after it terminates. Raise an error if no single change works.

Constraints

• 1 <= len(instructions) <= 10^5
• -10^4 <= value <= 10^4
• Aim for better than trying every change and re-running the program each time.

Example

instructions = [
  "next 0",   # 0
  "plus 1",   # 1
  "jump 4",   # 2
  "plus 3",   # 3
  "jump -3",  # 4
  "plus -99", # 5
  "plus 1",   # 6
  "jump -4",  # 7
  "plus 6",   # 8
]

The program runs indices 0, 1, 2, 6, 7, 3, 4 and then jumps back to 1. find_loop returns (1, 5).

Changing index 7 from jump -4 to next -4 makes the program run 0, 1, 2, 6, 7, 8 and stop at index 9. repair returns 8.

Example 2

["plus 2", "next 2", "jump -2", "plus 100"] loops through 0, 1, 2, 0. find_loop returns (0, 2). Changing index 1 to jump 2 reaches index 3 and then terminates, so repair returns 102.