Wednesday, 16 December 2020

Python searching by grid

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