[Community Puzzle] Rectangle Partition


#1

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.


#2

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


#3

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.


#4

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” :frowning: P.S. hope I didn’t give too much away, but since I can’t 100% this puzzle yet, it should be fine :smiley:


#5

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.


#6

Thanks for the hint :smiley: I’ll try that now and see what I can do


#7

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.


#8

10 2 1 1
5
1

hi @user938300 Try this.


#9

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% :smiley: thanks once more!


#10

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.


#11

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.


#12

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 :slight_smile:


#13

Congrets to your significant improvement. Glad that you enjoyed it.


#14

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.


#15

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.


#16

Thank you for your advice and the interesting challenge. :+1:
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 :grinning:.
I haven’t figured why the old code failed yet. :thinking:


#17

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.