You are given a file containing one bootloader instruction per line. Each instruction has an operation and an integer value:
plus +1
next 2
jump +3
plus +3
jump -1
plus +2
The bootloader maintains:
A program counter pc, initially 0
A global accumulated value acc, initially 0
The program runs until either:
pc moves past the last instruction, meaning the program terminates
pc reaches an instruction that has already been executed, meaning the program is in a loop
The wording in this interview has been reported as easy to misread. The goal is not to sum every plus value in the file. You only return the accumulator reached by actually executing the program path.
All instruction indices are zero-based. For this write-up, successful termination means the program counter moves past the last instruction (pc >= len(program)). Inputs are assumed not to jump before the first instruction.
Given a program that forms a loop, run the bootloader and find the loop.
At minimum, your simulator should detect the first instruction index that would be executed twice. If asked to return the full loop, return the sequence of instruction indices from the first time that repeated instruction was seen through the end of the visited trace.
0: plus +1
1: jump +2
2: plus +100
3: next +2
4: jump -2
5: plus +5
Execution:
pc=0, acc=0 -> plus +1 -> pc=1, acc=1
pc=1, acc=1 -> jump +2 -> pc=3, acc=1
pc=3, acc=1 -> next +2 -> pc=4, acc=1
pc=4, acc=1 -> jump -2 -> pc=2, acc=1
pc=2, acc=1 -> plus +100 -> pc=3, acc=101
Instruction 3 is about to run for the second time, so the loop is:
[3, 4, 2]
Build a simulator that executes instructions from pc = 0 and records every instruction index before executing it. If the next pc has already been recorded, the program is looping.
from dataclasses import dataclass
from typing import Optional
@dataclass(frozen=True)
class Instruction:
op: str
value: int
def parse_program(lines: list[str]) -> list[Instruction]:
program = []
for line in lines:
line = line.strip()
if not line:
continue
op, raw_value = line.split()
program.append(Instruction(op, int(raw_value)))
return program
def run_program(lines: list[str]) -> tuple[bool, int, Optional[int], list[int]]:
program = parse_program(lines)
pc = 0
acc = 0
visited = set()
trace = []
n = len(program)
while pc < n:
if pc < 0:
raise ValueError("Program counter moved before the first instruction")
if pc in visited:
return False, acc, pc, trace
visited.add(pc)
trace.append(pc)
instruction = program[pc]
if instruction.op == "plus":
acc += instruction.value
pc += 1
elif instruction.op == "next":
pc += 1
elif instruction.op == "jump":
pc += instruction.value
else:
raise ValueError(f"Unknown instruction: {instruction.op}")
return True, acc, None, trace
def find_loop(lines: list[str]) -> list[int]:
terminated, _, repeated_pc, trace = run_program(lines)
if terminated or repeated_pc is None:
return []
start = trace.index(repeated_pc)
return trace[start:]
Complexity for Part 1:
Time: O(n), because each instruction is executed at most once before termination or repeat detection
Space: O(n) for the visited set and trace
The program loops because exactly one instruction was written with the wrong operation:
One jump should have been next, or
One next should have been jump
Find the bad instruction, flip only that instruction, rerun the program, and return the accumulator value from the corrected run.
In some versions of the prompt, the interviewer may describe this as the jump or next instruction associated with revisiting a line. A safe way to handle that ambiguity is to still validate the candidate by rerunning from the beginning after the flip. Do not assume the answer is the sum of all remaining plus instructions.
For the example above, flipping instruction 3 from next +2 to jump +2 produces:
pc=0, acc=0 -> plus +1 -> pc=1, acc=1
pc=1, acc=1 -> jump +2 -> pc=3, acc=1
pc=3, acc=1 -> jump +2 -> pc=5, acc=1
pc=5, acc=1 -> plus +5 -> pc=6, acc=6
The corrected program terminates, so the answer is 6.
plus instructions are never the corrupted instruction.
next may still have an integer value in the file. That value is ignored while the operation is next, but it matters if the instruction is flipped to jump.
Return the accumulator from the corrected execution path, not the sum of all plus values in the file.
A brute-force repair is acceptable for small inputs: try flipping each jump or next reached before the loop, then run the simulator from the start.
This part builds directly on Part 1:
Run the original program using the Part 1 simulator.
Look at the executed trace that leads into the loop.
For each reached jump or next, temporarily flip it.
Rerun the simulator from the beginning.
The flipped instruction that makes the program terminate is the bad instruction; return the resulting accumulator.
This brute-force repair is the approach described in the report and is usually sufficient for an interview-sized file.
The code below assumes Instruction, parse_program, and run_program from Part 1 are already defined.
def flipped(instruction: Instruction) -> Instruction:
if instruction.op == "jump":
return Instruction("next", instruction.value)
if instruction.op == "next":
return Instruction("jump", instruction.value)
return instruction
def run_program_with_patch(
program: list[Instruction],
patch_index: int,
) -> tuple[bool, int]:
pc = 0
acc = 0
visited = set()
n = len(program)
while pc < n:
if pc < 0:
raise ValueError("Program counter moved before the first instruction")
if pc in visited:
return False, acc
visited.add(pc)
instruction = program[pc]
if pc == patch_index:
instruction = flipped(instruction)
if instruction.op == "plus":
acc += instruction.value
pc += 1
elif instruction.op == "next":
pc += 1
elif instruction.op == "jump":
pc += instruction.value
else:
raise ValueError(f"Unknown instruction: {instruction.op}")
return True, acc
def repair_program(lines: list[str]) -> tuple[int, int]:
program = parse_program(lines)
terminated, _, _, trace = run_program(lines)
if terminated:
raise ValueError("Program already terminates")
for i in trace:
instruction = program[i]
if instruction.op not in {"jump", "next"}:
continue
terminated, acc = run_program_with_patch(program, i)
if terminated:
return i, acc
raise ValueError("No single jump/next flip repairs the program")
Complexity for Part 2:
Time: O(n^2) in the brute-force version, because up to n candidates may each rerun the O(n) simulator
Space: O(n) for each simulator run