Disclaimer: I'm not a computer scientist, neither a mathematician, so the code I'm going to post here is probably quite ugly and not optimized. Any suggestion for improvements is welcome!You can read the original problem here. This time we are required to solve this puzzle:
The basic idea I used to solve it, is to group the points in all possible combinations of k sets (so if we have ABC points and 2 squares, the combinations will be 'A BC', 'B AC', 'C AB'); then for each group in a combination find the square that contains those points and get the maximum square's side length of the combination. The result is the minimum side length between all combinations.You are given n points in the plane. You are asked to cover these points with k squares.The squares must all be the same size, and their edges must all be parallel to the coordinate axes.
This brute-force algorithm is quite heavy and while it can solve the small input set quite easily it's no match for the large input. The solution took me quite some time to sort it out but i finally managed to make several simplifications and to solve the large input in about 17s (good enough for me).
The Python 3 code is at the end of the post. I've also made a multiprocessing version that use the same algorithm (when the un-optimized algorithm was running for hours...) but right now it's only half a second faster than the single processor one.
