A good lesson. A deeper lesson here (reference Knuth on premature optimization), since the problem can be refactored to be a simple application of the Chinese Remainder Theorem.
@herscheldecouto1642 жыл бұрын
Well Done!
@stevenlischer5 жыл бұрын
Some thoughts on this puzzle and things I will try: Each scanner is operating at a frequency and offset that will block solutions at a set interval. This can be used to skip iterations and remove scanners that are effectively redundant. As a simple example, a scanner that has a height of 2 will block all even or odd solutions depending on it's position, so there is no need to attempt those times and other scanners that have a frequency and offset that would block those solutions as well are now redundant and can be removed from the firewall because just by leaving on an even/odd time, you've already guaranteed you'll clear them. Also, since we're putting this much trouble into optimizing, why not multithread before moving to pypy, etc.?
@islandfireballkill6 жыл бұрын
A neat thing about cython is that the bounds checking is nearly entirely "free". How it does it is it just wraps things in if statements and because modern cpus and branch perdict, any branch which always jumps one way uses nearly no cpu cycles and doesn't stall the pipeline.
@MasayoMusic6 жыл бұрын
The github links don't seem to be working. Anyone know the working links?