Thanks for your code, it inspired me to try to make a faster version.
At first I tried other ways but at the end I implemented almost the same as you did, but just using the pygame methods for speed up (in exchange it is tied to pygame now, yours works just for python). For next time at least there will be some tests that can be re-used.
IIRC the algorithm tries to make as big rectangles if possible, so it does some sort of union them (without extra pixels). One can see how the algorithm splits the rects using the sript 'gumm_needs_to_see.py' (needs pygame) in my repo . Use arrow keys to move forward, space to change between the two algorithms (so you see differences between them in the result). It will go through all rect configurations (and some more) from the article .
My code has been tried to be written for performance that is why it might not be that readable (and also because there are many cases). Also I'm not sure anymore why it is around 2x faster only with -OO flags (looking at the code there aren't any asserts or such).
On 28.03.2017 14:19, Jason Marshall wrote: