menu

Questions & Answers

Find enclosed spaces in 2D array

So, I'm generating an array of spaces, which have the property that they can be either red or black. However, I want to prevent red from being enclosed by black. I have some examples to show exactly what I mean:

0 0 0 0 0 0 0 1
0 1 0 0 0 0 1 0
1 0 1 0 0 0 0 1
0 1 0 0 1 1 1 0
0 0 0 0 1 0 1 0
1 1 1 0 1 1 1 0
0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0

If red is 0 and black is 1, then this example contains four enclosures, all of which I want to avoid when I generate the array. The inputs I have are the size of the array and the number of 1s I can generate.

How would I go about doing this?

Comments:
2023-01-18 00:30:09
For each "0" space, do the sum of it's neighbours. If the sum is 8, then it's enclosed by "1". You could then randomly replace one of the "1" by a "0" (assuming you don't need a fixed number of "1" and "0")
2023-01-18 00:30:09
thats wrong, what if multiple 0's are enclosed by 1s?
2023-01-18 00:30:09
Indeed, I just thought of a solution for the example shown. Enclosure should be define more clearly. Is a "0" with four orthogonal "1" and four diagonal "0" considered enclosed ?
2023-01-18 00:30:09
It's not that clear what you are trying to achieve. Is the example input or the desired output? Could you complete your example so it has both sample input and desired output (and possibly explaination of the output)?
2023-01-18 00:30:09
@tmoreau Sorry, yes. Any number of 0s can be enclosed.
2023-01-18 00:30:09
@skyking This should be generated output. The only input is the number of 1s and the size of the array. The pattern should be generated in an approximately random manner
2023-01-18 00:30:09
@Woody1193 But there's an 0 enclosed by eight 1s, it doesn't seem to fulfill your specified requirement. And also there are 1s that's enclosed. I think you should improve your question.
2023-01-18 00:30:09
@skyking I don't care if 1s are enclosed. That is acceptable, even desirable . Also, a 0 enclosed by 8 1s doesn't fulfill the requirement. That was one of the examples of a bad result that I was trying to avoid.
Answers(4) :

So you can do the following:

  1. Fill array with zeroes
  2. Randomly select a point
  3. If the condition holds, flip color
  4. Repeat from step 2 or exit

The condition holds for all-zeros array. It is hold on any iteration. So, by induction, it is also true for the final array.

In the step 4 you can decide whether to stop or continue by doing, say N=a*b*1000 iterations or whether the ratio red/black is close to 1. In both cases, the result would be slightly biased since you start from all zeros.

Now, what is the condition. You have to ensure that all black points connected and all red points connected as well. In other words, there's maximum 2 connected clusters. Flipping a color could create more connected clusters, so you flip only when the its number is one or two. You can do the check quite efficiently using Union-Find algorithm, described here.

Edit: if however you want to permit black points to be surrounded by red ones but not vice-versa, you may change the condition to have any number of black clusters but only 0 or 1 of red clusters.

Does this code fits well for you?
Basically I fill a matrix from left to right, from top to bottom.
When I have to assign 0 or 1 to a cell, I check (north and west) if adding a 1 could enclose a 0; in this case I put a 0, else a random 0 or 1.

import sys, random

n = int(sys.argv[1])
m = int(sys.argv[2])

# fill matrix with zeroes
matrix = [[0 for _ in xrange(m)] for _ in xrange(n)]

# functions to get north, south, west and east
# cell wrt this cell.
# If we are going out of bounds, we suppose the matrix
# is sorrounded by 1s.

def get_n(r, c):
    if r <= 0: return 1
    return matrix[r - 1][c]

def get_s(r, c):
    if r >= n - 1: return 1
    return matrix[r + 1][c]

def get_w(r, c):
    if c <= 0: return 1
    return matrix[r][c - 1]

def get_e(r, c):
    if c >= m - 1: return 1
    return matrix[r][c + 1]

# Checks if the cell is already enclosed by 3 1s.  
def enclosed(r, c):
    enclosing = get_n(r, c) + get_s(r, c) + get_w(r, c) + get_e(r, c)
    if (enclosing > 3): raise Exception('Got a 0 enclosed by 1s')
    return enclosing == 3

for r in xrange(n):
    for c in xrange(m):
        # check west and north
        if enclosed(r, c - 1) or enclosed(r - 1, c):
            matrix[r][c] = 0
        else:
            matrix[r][c] = random.randint(0, 1)

        print str(matrix[r][c]) + ' ',

    print ''

Sample run: python spaces.py 10 10

Comments:
2023-01-18 00:30:09
Close, but not quite. If you'll look at my examples, you'll notice that enclosure also includes the edges of the array. So if a group of 0s is enclosed on 3 sides with the 4th being the edge of the array then it is still enclosed
2023-01-18 00:30:09
My code takes into account this fact. That's why I suppose that the matrix is sorrounded by 1s. You tried to execute the code and you fell into that issue?
2023-01-18 00:30:09
I notice now that you edited your question and you "enlarged" your definition of "enclosed". Now you want to avoid also squares of zeroes enclosed by ones.
2023-01-18 00:30:09
Your solution wouldn't work since it could generate a block of 3 or more enclosed points: (line 1) 10001 (line 2) 11111
2023-01-18 00:30:09
Yeah, now I know. The question was a bit different before. I am giving a new solution in a few hours. Some things to do before
2023-01-18 00:30:09
@affo Yes, sorry. I wasn't being quite as clear as I wanted to. The enclosure can be of any arbitrary size or shape .

This would be a possible way to check the condition:

def: findStart(myArr):
    for i in range(len(myArr)):
        for j in range(len(myArr[0])):
            if(myArr[i][j] == 0):
                return (i,j)

def: checkCon(myArr, number_Ones):
    width = len(myArr[0])
    height = len(myArr)
    pen = []                      #A list of all points that are waiting to get a visit
    vis = []                      #A list of all points that are already visited
    x = findStart(myArr)

    while(len(pen) != 0):         #Visit points as long as there are points left
        p = pen.pop()             #Pick a point to visit

        if p in vis:
           #do nothing since this point already was visited

        else:
            vis.append(p)
            x,y = p

            #A vertical check
            if(x == 0 and myArr[x+1][y] == 0):
                pen.append((x+1,y))
            elif(x == (height-1) and myArr[x-1][y] == 0):
                pen.append((x-1,y))

            else:
                if(myArr[x-1][y] == 0 and x-1 >= 0):
                    pen.append((x-1,y))
                if(myArr[x+1][y] == 0):
                    pen.append((x+1,y))


            #A horizontal check    
            if(y == 0 and myArr[x][y+1] == 0):
                pen.append((x,y+1))
            elif(y == (width-1) and myArr[x][y-1] == 0):
                pen.append((x,y-1))

            else:
                if(myArr[x][y+1] == 0):
                    pen.append((x,y+1))
                if(myArr[x][y-1] == 0 and y-1 >= 0):
                    pen.append((x,y-1))                 


    print((height*width-number_Ones) == len(vis))       #if true, alle Zeros are connected and not enclosed

To clarify this is just a concept to check the condition. The idea is to visit all connected zeros and see if there are any left (that are not connected). If that is the case, there are some enclosed.
This method also doesn't work when the 1's form a frame around the matrix like this:

1 1 1 1
1 0 0 1
1 0 0 1 
1 1 1 1

Again, just a concept :)

The problem has two parts actually. Generating the board state, and then checking if it is correct. I realised that checking the correctness was actually worse than just being sure correct states were always generated. This is what I did:

Note that I have defined self.WallSpaces to be an array equal in length to the height of my array, comprised of integers with the number of bits equal to the width of my array. self.Width and self.Height provide the end indices for the array. Basically, Intersects works by checking all the spaces surrounding a point for 1s, except the direction the space was "built from" (see below) and returning True if any of these are the edge of the array or a 1.

def Intersects(self, point, direction):
    if (point[0] > 0):
        if (direction != [1, 0] and self.WallSpaces[point[0] - 1] & (1 << point[1]) != 0):
            return True
        if (point[1] == 0 or self.WallSpaces[point[0] - 1] & (1 << (point[1] - 1)) != 0):
            return True
        if (point[1] == self.Width or self.WallSpaces[point[0] - 1] & (1 << (point[1] + 1)) != 0):
            return True
    else:
        return True
    if (point[0] < self.Height):
        if (direction != [-1, 0] and self.WallSpaces[point[0] + 1] & (1 << point[1]) != 0):
            return True
        if (point[1] == 0 or self.WallSpaces[point[0] + 1] & (1 << (point[1] - 1)) != 0):
            return True
        if (point[1] == self.Width or self.WallSpaces[point[0] + 1] & (1 << (point[1] + 1)) != 0):
            return True
    else:
        return True
    if (point[1] == 0 or (direction != [0, 1] and self.WallSpaces[ point[0] ] & (1 << (point[1] - 1)) != 0)):
        return True
    if (point[1] == self.Width or (direction != [0, -1] and self.WallSpaces[ point[0] ] & (1 << (point[1] + 1)) != 0)):
        return True
    return False

The directions GPacW.Left, GPacW.Right, GPackW.Up, and GPacW.Down represent the cardinal directions for movement. This function works by constructing "walls" in the array from random points, which can turn in random directions, ending when they have intersected twice.

def BuildWalls(self):
    numWalls = 0
    directions = [ [GPacW.Left, GPacW.Right], [GPacW.Up, GPacW.Down] ]
    start = [ random.randint(0, self.Height), random.randint(0, self.Width) ]
    length = 0
    horizontalOrVertical = random.randint(0, 1)
    direction = random.randint(0, 1)
    d = directions[horizontalOrVertical][direction]
    intersected = False
    while (numWalls < self.Walls):
        while (start == [0, 0] or start == [self.Height, self.Width] or self.Intersects(start, d)):
            start = [ random.randint(0, self.Height), random.randint(0, self.Width) ]
        if (length == 0):
            horizontalOrVertical = not horizontalOrVertical
            direction = random.randint(0, 1)
            length = random.randint(3, min(self.Height, self.Width))
            d = directions[horizontalOrVertical][direction]
        if (self.WallSpaces[ start[0] ] & (1 << start[1] ) == 0):
            self.WallSpaces[ start[0] ] |= 1 << start[1]
            numWalls += 1
            length -= 1
        if (0 <= (start[0] + d[0]) <= self.Height and 0 <= (start[1] + d[1]) <= self.Width):
            start[0] += d[0]
            start[1] += d[1]
        else:
            start = [0,0]
        if (self.Intersects(start, d)):
            if (intersected):
                intersected = False
                start = [0,0]
                length = 0
            else:
                intersected = True
    return