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

# advent-of-coden

Nir

12/08/2020, 3:08 PMFor those curious, a better algorithmic solution for day 8 part b, way too lazy to implement, see thread

Nir

12/08/2020, 3:08 PMThe 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

12/08/2020, 3:10 PMYou 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

12/08/2020, 3:10 PMNow you just run Dijstra's minimal distance algorithm, since this graph is sparse that will give NlogN

Nir

12/08/2020, 3:12 PMIn 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

12/08/2020, 3:28 PMThink actually it can be simplified quite a bit more, even just adding memoization to the naive approach is probably enough to get O(n)

5 Views