How would I check if grid contains rectangles

Question

1.00/5 (1 vote)

See more:

I have a list of characters:

strings = ["..##.......",
           "#...#...#..",
           ".#..#.#..#.",
           "..#.#...#.#",
           ".#...##..#.",
           "..#.##.....",
           ".#.#.#....#",
           ".#..#.....#",
           "#.###..#...",
           "#....#....#",
           ".#......#.#"]

This represents sort of a 2d grid, with x being the number of char inside a single string and y being the number of strings. The dot represents empty spaces an the hashtag full ones.
What I need to do is to find the biggest aligned empty rectangle inside the grid. Here is an example as a photo.
https://ibb.co/BtwvGLL
I have a function to check if the space is empty or not.

What I have tried:

I tried going via x and checking if the coordinates were empty and then mark when it is not empty, going to the next line and checking if the spaces are empty to the marked line, but that doesn't work, when the top one is larger and the bottom one is still rectangle.

How would you consider solving such a problem?

Ok, so according to the first solution, I have something like this. I have a generator to go through all the coordinates, then I first find a row, then check the bottom one of the same end x coordinate the top one has and if y is more than 0, also check the top one, to find the biggest rectangle. The only problem is, that instead of 12 it returns one less, so 11.

Posted 8-Dec-20 21:58pm

Member 14631234

Updated 9-Dec-20 23:25pm

v5

Add a Solution

Comments

Patrice T 9-Dec-20 5:15am

show your code

2 solutions

Solution 2

Quote:
How would I check if grid contains rectangles

My approach would be brute force, aka check every possible rectangle.

Quote:
I tried going via x and checking if the coordinates were empty and then mark when it is not empty, going to the next line and checking if the spaces are empty to the marked line, but that doesn't work, when the top one is larger and the bottom one is still rectangle.

You have been very careful to give only extremely vague information about what you did.
The only answer is that you did it wrong, but your code is secret, no further help is possible.
[UpDate]

Quote:
Ok, so according to the first solution, I have something like this.

Can you complete your code with all necessary input so we can run it exactly the same.

Quote:
The only problem is, that instead of 12 it returns one less, so 11.

Your code do not behave the way you expect, or you don't understand why !

There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your code is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]

27.3. pdb — The Python Debugger — Python 3.6.1 documentation[^]
Debugging in Python | Python Conquers The Universe[^]
pdb – Interactive Debugger - Python Module of the Week[^]

The debugger is here to only show you what your code is doing and your task is to compare with what it should do.

Posted 9-Dec-20 7:45am

Patrice T

Updated 9-Dec-20 13:01pm

v2

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Accepted Answer · 2020-12-08T22:21:00

Think about the shape of a rectangle: it has four corner points which share two X and two Y coordinates: (X1,Y1) - (X2, Y1) - (X2, Y2) - (X1, Y2). Potentially (but not necessarily) there might be other points inside that shape, but you need all four corners to be a rectangle.
So start at the top left and look for a corner point (X1, Y1). Look right from that and see if there is a matching corner (X2, Y1). If you find it, look down from the first corner and find the next point (X1, Y2). Check if there is a corner at (X2, Y2). If there is, it's a rectangle (though you may need to check if it's empty - I don't know what the specific requirements of your system are concerning overlapped rectangles).
If there isn't, that's not a rectangle, so try looking further down for a new third point (X1, Y2). If you get to the end, try looking right for a new second point (X2, Y1) and repeat the process.

Try it on paper, and you'll see what I mean pretty quickly!