I have a grid, defined like this:
['..##.......',
'#...#...#..',
'.#..#.#..#.',
'..#.#...#.#',
'.#...##..#.',
'..#.##.....',
'.#.#.#....#',
'.#..#.....#',
'#.###..#...',
'#....#....#',
'.#......#.#']
[2, 7, 3, 3, 8, 2, 3, 3, 4, 7, 3, 2, 3, 12, 2, 4, 3, 5, 3, 3, 4, 4, 7]
Where dot is a empty space and # is full. Now what I need to do is to find the biggest rectangle there is, by searching the grid. In this example it is 12 (6 - 8, all rows contain 4 dots). What I do is I save the first coordinate, go via x and see if the space is empty. If it is empty, I save x until I find that is it full. If it is full I go check bellow row of the same lenght and continue that, until I find a row that if not completly empty.
If y > 0 I also check above, so that I can get the ones overlapping aswell. My problem is, my program works fine on this array, and these 2 also:
['..##.......',
'#...#...#..',
'.#..#.#..#.',
'..#.#...#.#',
'.#...##..#.',
'..#.##.....']
Biggest is 7, gives an array = [2, 7, 3, 3, 6, 2, 3, 3, 4, 5, 3, 2, 3]
['..##.......',
'#...#...#..',
'.#..#.#..#.',
'..#.#...#.#',
'.#...##..#.',
'..#.##.....']
Biggest is 8, gives an array = [8, 7, 7, 2, 4]
But if I try something like this:
['.#.#.',
'...#.',
'...#.',
'####.',
'#....',
'#...#']
It returns 8 instead of 6 and gives an array = [8, 7, 7, 2, 4, 3]. What would be the problem?
This is my code
gen = ((x, y) for y in range(0, len(array)) for x in range(0, len(array[0])))
loc = {"x1": 0, "y1": 0, "x2": 0, "y2": 0}
temp = []
count = 0
for x, y in gen:
if not array[y][x] == "#":
loc["x2"] = x
count += 1
elif count > 1:
i = 0
check = False
temp_y = y
y += 1
while i <= loc["x2"] and y < len(array):
if not array[y][i] == "#":
if i == loc["x2"]:
check = True
else:
break
if check:
count += i + 1
i = 0
loc["y2"] = y
y += 1
check = False
else:
i += 1
y = temp_y
if y > 0:
i = 0
y -= 1
while i <= loc["x2"] and y < len(array):
if not array[y][i] == "#":
if i == loc["x2"]:
check = True
else:
break
if check:
count += i + 1
i = 0
loc["y2"] = y
y -= 1
check = False
else:
i += 1
temp.append(count)
count = 0
loc["x1"] = x
loc["y1"] = y
print(temp)
print(max(temp))
So what I do is, I find a empty space, then check below and above for the height. I am also counting how big it is (from how many empty spaces it is combined), then I save that amount inside another array (the array with numbers)
Example:
['...#..']
['3, 2]
Or a bigger one:
['...#...#.#',
'....#.###.',
'###...####']
[6 (because of the second row), 3, 1, 4, 5, 1, 1, 3]
The problem is (see below), that it works ok, until it hits the third row, then it just loses its mind.
['..##.......',
'#...#...#..',
'.#..#.#..#.',
'..#.#...#.#',
'.#...##..#.',
'..#.##.....',
'.#.#.#....#',
'.#..#.....#',
'#.###..#...',
'#....#....#',
'.#......#.#']
[2, 7, 3, 3, 8, 2, 3, 3, 4, 7, 3, 2, 3, 12, 2, 4, 3, 5, 3, 3, 4, 4, 7]
from Python searching by grid
No comments:
Post a Comment