https://www.codingame.com/training/easy/rectangle-partition
Send your feedback or ask for help here!
Created by @java_coffee_cup,validated by @Alain-Delpuch,@Deltaspace and @field3.
If you have any issues, feel free to ping them.
1 Like
I passed all test cases, except for the Hi-Density ones (which I’m assuming are there for optimizing code). Problem is, for the life of me, I can’t think of other ways to check for squares more efficiently than one by one. P.S. I’m relatively new to Python and programming by the way
6 Likes
Could you describe in details how did you check for squares “one by one”? By understanding your algorithm, it is possible to point out why your algorithm is inefficient, so that you will have a direction to make improvement.
1 Like
I created a list of all the possible pairs of x and y coordinates (including combinations with 0 and width/height), then I went through the list with a nested for loop and subtracted the values from each pair to check if they are equal (ex. if x1-x2==y1-y2 from (x1,y1) and (x2,y2) pairs). It’s a very blunt way of doing it, but I just couldn’t figure out how to approach it more “elegantly” 
P.S. hope I didn’t give too much away, but since I can’t 100% this puzzle yet, it should be fine 
1 Like
Thanks your detailed information.
In each check, you have to calculate (x1-x2) and (y1-y2), two subtractions.
When you have 1000 times of compare, you have to do the above calculation 2000 times. Most of the results have been done before.
This is why you got timeout.
You can calculate it only once, store it. When you need it again, pull it out to use directly.
8 Likes
Thanks for the hint I’ll try that now and see what I can do
thank you java_coffee_cup for the nice puzzle.
i fail only validator 6, and wonder why. Here is my try in AWK:
index every length created by the x and y measurements with a value of the number of instances.
for every length in both x and y, multiply instances and add to the count.
I’ll try and puzzle this out. Thanks again.
1 Like
thank you again @java_coffee_cup; this time for the help.
code returns 0 for your example. am i missing something? i find no 1x1 or 2x2 or 5x5 or 10x10 in there.
EDIT: needed count=0 for 100% thanks once more!
1 Like
If your code can handle non-existence of squares, there could be a bug somewhere I don’t know. For self verification, you may try write another simpler version without using indexing for cross check. You know the mapping and compare part has higher risk to conceal bugs.
Thanks for your solution description. It helped me to pass Hi-density tests.
I checked my code with this inputs
10 10 2 1
2 5
3
2
and
10 2 1 1
5
1
0
Mb it can help.
The Hi-Density tests were trickier due to heavier computations.
It forced me to rethink the problem and I finally found an elegant solution, passing from 11s computing to 1ms (11 000 times faster!)
It was really enjoyable, thanks for this 
5 Likes
Congrets to your significant improvement. Glad that you enjoyed it.
1 Like
Nice puzzle, thanks!
I’m able to pass everything save Validator 9.
Is it likely that I need further optimization or should I look elsewhere?
I appreciate that I’ve had to research and experiment to find ways to optimize in Python.
1 Like
If you can pass validator 8 and all the “Hi-density” tests, validator 9 should not be a problem in terms of computing complexity. It looks very alike the “Imbalance” test case. Nothing special or designed to be tricky in the validator. There could be a subtle logical bug in the code that you may have to design and try out unit tests.
Thanks your interest in this puzzle.
2 Likes
Thank you for your advice and the interesting challenge. 
I tweaked the code to I used catch the intersection of side lengths in height and width and passed the final validator. The code is a bit faster too 
.
I haven’t figured why the old code failed yet. 
Hello, during several days I’ve tried to optimize my code or find new algorithm to pass Hi-Density tests without success.
I give up) Could someone help me with the hint or solution?
Thank you.
It is surprising that this little puzzle attracted so many coders’ interest and at the same time causing so much difficulty to many coders as reflected by the very low (55%) success rate.
As this puzzle is meant to be an “Easy” one for practice, I decided to give some hints to help out anyone who might need it.
[Do not open the hidden text below if you do not want to see the hint]
hint
The puzzle asks for checking “sub-rectangles”. A rectangle is composed of width and height properties. By extending this concept, the puzzle is asking for checking “sub-widths” and “sub-heights”.
What is “sub-width”? Suppose you have several measurements [a, b, c] on the width side.
0…a…b…c…w
Together with the full width, you have widths :a, b, c, w. You still need the combinations of these basic widths. They are:
w-c, w-b, w-a, c-b, c-a, b-a
So there should be 10 sub-widths.
Same logic for sub-heights.
Finally, compare each of the sub-widths with each of the sub-heights, increment your counter when they match. You will get the correct sub-square count.
Note that you only need to calculate all these sub-lengths once. Store them in arrays or lists. During compare, you do not need to calculate these add or subtraction any more.
If the language you use is particularly slow, you can further optimize the data. Put the list into maps (value : count) to reduce iteration during compare. This can further speed up the execution in bigger data sets.
The above algorithm does not rule out any alternative and clever algorithms that you can think of…DP? Graph? Many possibilities.
Happy coding!
12 Likes
@java_coffee_cup You could use ROT13 or make a collapsible block (Toolbar > Options > Hide Details).