Find enclosed spaces in 2D array

Question

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?

Answer 1

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

Answer 2

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 :)

Answer 3

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.

Answer 4

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