[Community Puzzle] Rectangle Partition

Puzzles
#126

Seems to me this post in 2019 should help:

#127

Another hint found to be helpful by other coders:

using a map structure

1 Like
#128

Yes . Thank you .
My algorithm was the same ideea all I needed to do was to compare which list is smaller and to the search there.

#129

Hi there,

i just wanted to say thank you since this was somehow the most challenging puzzle on easy so far.
In the end this was pretty easy but for any reasons the way to develope the right algorithm takes a while. But anyway it was fun so thank you for the nice puzzel

1 Like
#130

Loved the hi-density puzzles. I thought I had it completed in a few minutes and then I had to sit and think for another hour on how to pass the hi-density time constraint. Really nice way to make an “easy” puzzle easy while also being difficult. Fun puzzle.

1 Like
#131

If you implement this in python, you will get a timeout.

#132

even with the hint i could not solve this question, I guess I am just too dumb oh well.

#133

I’m by no means an expert programmer, but I really love coding puzzles. They force me to actually code, instead of watching tutorials. They also force me to keep digging for “cleaner methods”. I used Python for this.

It took me a while to wrap my head around the problem of finding the lengths of each side to compare, but I finally found a function that would run through the list of values, and spit out an array of other values, that I would put in another array, and then keep reducing this new array until it got down to 1 element.

Then I did a super quick compare of something like:
for i in listX:
for j in listY:
if i = j then increment counter

This spat out an answer for everything BUT the high density ones. Those ones kept timing out.

It took me about 3 hours to keep chipping away until I found a lot better, and faster ways to do the comparisons.

Thank you so much for this puzzle, it was a tremendous amount of fun, and helped me learn some really smart methods to compare.

3 Likes
#134

At some point, I failed a test because of the logging I was doing.
Once removing the logging, all tests passed.
But I probably could optimize that stuff, thought later about using dictionaries of counters, instead of list filled with identical values, this could probably save a lot of time.
Maybe it used to be necessary, then the hardware got upgraded, and it’s now possible to evade an expected timeout :smiley:

#135

Hello everyone! Thank you for an interesting task. It doesn’t seem difficult when you don’t get to the “Hi-density” test :relaxed: I, like many, died on this test.
Step by step, my code became more and more efficient (about 2 times). As a result, for 4 implementations, I managed to pass these tests. As a result, the implementation turned out to be 7 times more time efficient than the very first attempt.
I am very glad to solve such problems, as they help me deepen my knowledge of C ++.

3 Likes
#136

Just a heads-up to anyone attempting the puzzle using Haskell: you’ll probably want to start out by deleting the O(n^2) auto-generated code for parsing the locations of the divisions. Similar advice might apply in other languages.

#137

Hello,

In python the use of dict improve drastically the speed of the script.
The solution for me was to create two list for x and y of the different length of segment possible and then use counter to create dict with the number of time you have each values and then it was really simple to get the number of squares.

#138

If you’re counting the squares one by one that means you’re calculating some things multiple times - maybe the possible widths of all squares in a row.

You can start by calculating all possible widths and all possible heights and how many times each one appears than calculate by that.

For example if there are 3 occurrences of vertical lines spaced 7 apart and 5 occurrences of horizontal lines spaced 7 apart that means there are exactly 3*5=15 squares with side length 7.

#139

I agree with others above that this should be a Medium problem. It’s not about the code to complete this being overly complex… Once you know what you need to do, it’s easy to write the code to solve it (I would argue though that this is true of most coding problems). The problem is that the timeouts are so tight that the breadth of acceptable solutions is very small and requires a lot of optimizing your code. In my mind, an Easy problem should be accessible to new developers who understand the fundamentals and are trying to build their skills. I feel like this problem would instead frustrate a lot of people in this category and discourage them, even though they have technically correct problem solutions which are just not quite optimal. In the Medium difficulty category, I would expect this kind of problem where you need to expand on those foundations, optimize, and think outside of the box a bit.

2 Likes
#140

Got it working now thanks to the hint with mapping :slight_smile: Thanks! But I doubt that is an easy puzzle and not suited for beginners.

#141

Hi,

I’ve sucessfully passed all tests but i’m wondering what kind of logic could be done to have the same result ?

I’ve started to make another version using Coordinates but i don’t know what i could do with them.

I’ve also seen QuadTree, maybe a version of this, validating a square if all vertices touch 4 known stored vertices from the Base rectangle ?

Thanks in advance to anyone that will respond to this.

#142

That’s an interesting idea I did not think of.
Using coordinates would not change the applicable algorithms. It changes the data structure.

With this data structure,
Pro: you get details of the squares (their exact locations) in the final result.
Con: you use more memory space to define the structure and more CPU cycles to calculate the locations.

#143

Thanks for the challenge !
As a lot of people here, i started with the “easy” blunt way of resolving this problem. And, as a lot of people here, i struggled with timeouts for the High density cases.
This got me thinking a lot, and thanks to all the tips in this discussion, i managed to visualize a simpler and more efficient way to do. After that, i got a 100% solution very quickly.
Thanks everybody !
Mike from Toulouse

2 Likes
#144

Yeah came from quadrople for loops to dict method. I made so far, yet cannot pass hi-dens 2. Sadly, give up. Any help or reading that will save me from this missery is gladly accepted, thanks a lot!

c = 0
x_part = {}
y_part = {}

for i, x1 in enumerate(XL):
    for x2 in XL[i+1:]:
        try:
            x_part[x2-x1] += 1
        except:
            x_part[x2-x1] = 1

for i, y1 in enumerate(YL):
    for y2 in YL[i+1:]:
        try:
            y_part[y2-y1] += 1
        except:
            y_part[y2-y1] = 1

for x in x_part:
    for y in y_part:
        if y == x:
            c += y_part[y] * x_part[x]
print(c)
#145

There is a better way to check if something is in a dictionary (y_part) than looping through it and checking every key.

1 Like