I've been having fun trying to optimize day 6 on #AdventOfCode, which is my slowest day. My original implementation was 590 millis. Changing the data structure to minimize repeated work took it to 55 millis. Moving from Vec> to Array2 saved another 13%. github.com/omalley/adve...
Impressive times. That is my slowest day by far. I might have to look at what you did, and see if it applies to C++, to see if I can fix mine...
It all should be translatable to C++. I basically created a small (max 4 items) stack for each place in the grid. When I move to a new square, I push my previous position to new location's stack. That lets me unwind my path and detect loops. The code iterates backwards and puts a block on the spot.
That means I don't need to redo the previous stuff, because I start right at the new block. I then pop off the path back to the block and do the previous location.
Thank you for making me look back at that day. Found a silly bug and went from ~400ms to ~80ms on my fast machine and a whopping 1.6s down to ~350ms on my slow-poke test machine. Had a silly mistake in my loop detection code. Now Day 7 is the hold-up for me....