AoC 2016 day 11

[Clement-Lelievre]

Hi Mr Norvig,

In recent months I've been doing a lot of AoC puzzles in Python.
Today I solved 2016 day 11 then noticed you said in your dedicated notebook at the time that your own solution ran in about 14 min for part 2. I checked the Reddit thread for that day and many if not all Python solutions also took several minutes to complete for part 2.
I've been impressed by your concise and clear, functional style and overall efficiency across all your AoC solutions, therefore I'm surprised my own Python solution takes only about 2 seconds to run for part 2.

I guess there must be other explaining factors than the difference in hardware between then and now, or the fact that background processes may have slowed down your run at the time.
I hardly believe my solution is that much optimized (especially since I did not consider the symmetry trick you mention in the notebook) so I'm guessing it must contain some flaw somewhere.

If you'd like to have a look at my implementation, I'd be more than happy to be proven wrong and learn in the process.

Kind regards,

Clement

[Carreau]

Hi Clement,

I haven't dived into it for quite some time, but 2 thing come to my mind:

1. I find it really astonishing that a AOC puzzle need 14 min run time, I expect a few second.
   So my guess is there might be something weird with the 14 minutes.

2. I would suggest running a (line) profiler on @norvig code, see what is slow. Something like https://github.com/pyutils/line_profiler

With such a difference even without looking at the code, knowing that @norvig write relatively good code I doubt the code itself is slow. It is likely that it tries to explore a much bigger graph. I would start looking into wether the graph explored are of the same size.

Like if you have a generator and chip together, maybe @norvig code explore possibilities of re-separating them and yours does not ?