Level 1 Run the program and find the loop
A tiny boot program is a list of text lines, one instruction per line: an operation name, a space, and a signed integer operand such as +3, -2 or 0.
| operation | effect |
|---|---|
plus n |
add n to the accumulator (which starts at 0), then move to the next line |
next n |
move to the next line; the operand does nothing |
jump n |
move to line current + n |
Lines are numbered from 0. The program stops in one of two ways:
- it exits: the line to run next is outside
0 .. len(lines) - 1(past either end), or - it loops: the line to run next has already been run once. Stop before running it a second time.
Implement:
parse(lines: list[str]) -> list[tuple[str, int]]turns each line into(op, n). Ignore extra spaces around the parts.run(lines: list[str]) -> tuple[int, int | None]runs the program and returns(accumulator, loop_line).loop_lineis the index of the line that was about to run a second time, orNoneif the program exited.
prog = ["plus +2", "jump +2", "plus +100", "plus -1", "jump -3"]
run(prog) # (1, 1): ran lines 0, 1, 3, 4; line 4 jumps back to line 1
run(["plus 5", "next -9", "plus 1"]) # (6, None): ran off the end
run([]) # (0, None)
A jump 0 loops on itself immediately after running once.