For those curious, a better algorithmic solution f...

# advent-of-code

[Nir]

For those curious, a better algorithmic solution for day 8 part b, way too lazy to implement, see thread

[Nir]

The brute force solution is N^2; it costs N to verify if a change leads to infinite loop or exit, and we're brute forcing every possible location

[Nir]

You can view the instruction set as a weighted graph. each instruction has an edge of cost 0 to another node. For every nop and jump you can add another edge of cost 1 for if you changed it to the opposite instruction

[Nir]

Now you just run Dijstra's minimal distance algorithm, since this graph is sparse that will give NlogN

[Nir]

In fact you can even get N running time now, according to wikipedia:

When arc weights are small integers (bounded by a parameter {\displaystyle C}), specialized queues which take advantage of this fact can be used to speed up Dijkstra's algorithm. The first algorithm of this type was Dial's algorithm (Dial 1969) for graphs with positive integer edge weights, which uses a bucket queue to obtain a running time {\displaystyle O(|E|+|V|C)}.

[Nir]

Think actually it can be simplified quite a bit more, even just adding memoization to the naive approach is probably enough to get O(n)