Expand description
§Handheld Halting
A brute force implementation that changes every Jmp or Nop in the input one at at time then
tests the result would have O(n²) complexity for part two.
We can solve part two in O(n) complexity, executing each instruction at most twice. We start
the same as the brute force solution by stepping through the input speculatively changing each
Nop to a Jmp or vice-versa, then executing the remaining program from that point and
checking if it finishes.
The trick is to re-use the visited vec that stores if we have executed an instruction before.
As each previous failed code path will have executed some instructions, trying to execute an
instruction twice means that we know immediately we are on a bad path and can stop.
Enums§
- State 🔒
Functions§
- execute 🔒