# Programming Challenge: Shape detection.

The programming challenges have kind of come to a grinding halt recently. I think it's time to get another challenge started!

Given a grid of symbols, representing a simple binary state of "filled" or "unfilled", determine whether or not a square is present on the grid. Squares must be 2x2 in size or larger, must be completely solid (i.e. all symbols in the NxN space are "filled"), and must not be directly adjacent to any other filled spaces.

Example, where `0` is "empty" and `1` is "filled":

``````000000
011100
011100
011100
000010

// Returns true.
``````
``````000000
011100
011100
011110
000000

// Returns false.
``````
``````000000
011100
010100
011100
000000

// Returns false.
``````

For those who want a greater challenge, try any of the following:

1. Get a count of all squares.
2. Detect squares that are touching (but not as a rectangle).
3. Detect other specific shapes like triangles or circles (you will need to be creative).
4. If doing (1) and (3), count shapes separately based on type.
5. Detect shapes within unfilled space as well (a checkerboard pattern is a great use case).

1. [2]
jzimbel
(edited )
Python 2.7: This operates by searching the grid from top to bottom for horizontal segments of 2 or more contiguous filled cells within a row, then starting a search anchored from each contiguous...

Python 2.7:
This operates by searching the grid from top to bottom for horizontal segments of 2 or more contiguous filled cells within a row, then starting a search anchored from each contiguous segment found for a shape like:

`````` 000
01110               * the 111 in this row is the contiguous segment we start from
01110
01110
000
``````

(arbitrarily scalable)
If any such shape is found, then the grid contains a square.

``````def contiguousReducer(acc, enumeratedCell):
'''
Based on state passed in the (acc)umulator and current cell's value, returns
a new state for the next cell.
State is a 3-tuple containing, in order:
- a list of 2-tuples, each giving the start and end indices of a contiguous filled segment in this row found so far
- a boolean indicating whether the previous visited cell was filled
- a boolean indicating whether we're currently in a contiguous filled segment
'''
i, cell = enumeratedCell
contiguousSegments, previousWasFilled, inContiguousSegment = acc
if previousWasFilled and cell:
if inContiguousSegment:
contiguousSegments = contiguousSegments[:-1] + [(contiguousSegments[-1][0], i + 1)]
else:
contiguousSegments = contiguousSegments + [(i - 1, i + 1)]
return (
contiguousSegments,
cell,
previousWasFilled and cell
)

def getSquareStarts(row):
'''
Computes a list of 2-tuples, each giving the start and end indices of a contiguous filled segment in this row.
End indices are exclusive: a tuple (2,5) means that there's a contiguous filled segment covering cells 2,3, and 4.
'''
return reduce(contiguousReducer, enumerate(row), ([], False, False))[0]

def gridContainsSquare(grid):
for i, row in enumerate(grid):
for startIndex, endIndex in getSquareStarts(row):
# So far we've found a single contiguous horizontal line of filled cells that might be the start of a square.
# Now we just need to check a bunch of things to see if it really is one.
sidelength = endIndex - startIndex
if (
# are there enough rows left in the (non-bordered) grid to fit a square this tall?
i + sidelength <= len(grid) - 2
# are there enough columns left in the (non-bordered) grid to fit a square this wide?
and startIndex + sidelength <= len(row) - 2
# do all segments from startIndex to endIndex in rows below this one have all filled spaces?
and all(
all(cell for cell in row[startIndex:endIndex])
for row in grid[i:i + sidelength]
)
# does the previous row have all unfilled spaces adjacent to this segment?
and not any(grid[i - 1][startIndex:endIndex])
# does the row after the last expected row of the square have all unfilled spaces adjacent to this segment?
and not any(grid[i + sidelength][startIndex:endIndex])
# does the column to the left of the left side of the expected square have all unfilled spaces?
and not any(row[startIndex - 1] for row in grid[i:i + sidelength])
# does the column to the right of the right side of the expected square have all unfilled spaces?
and not any(row[endIndex] for row in grid[i:i + sidelength])
):
return True
return False

def getGrid(str):
'''
Computes and returns a 2D list of booleans from the input string.
Grid is surrounded in a "frame" of False values (representing the "unfilled"
border) to make finding squares at the edge of the grid easier.
'''
grid = [
[True if char == '1' else False for char in line]
for line in str.split('\n')
]
boundaryRow = [False for x in grid[0]]
grid.insert(0, boundaryRow)
grid.append(boundaryRow)
return [
[False] + row + [False]
for row in grid
]

def inputContainsSquare(inputString):
return gridContainsSquare(getGrid(inputString))

inputA = '''
000000
011100
011100
011100
000010
'''.strip()
inputB = '''
000000
011100
011100
011110
000000
'''.strip()
inputC = '''
000000
011100
010100
011100
000000
'''.strip()

print inputContainsSquare(inputA) # True
print inputContainsSquare(inputB) # False
print inputContainsSquare(inputC) # False
``````
1. jzimbel
I iterated on this a little too much and ended up with a thing that finds all the squares in the input grid and prints the grid back out with all of the squares bolded. from sys import stdin MARK...

I iterated on this a little too much and ended up with a thing that finds all the squares in the input grid and prints the grid back out with all of the squares bolded.

``````from sys import stdin

MARK = '\033[1m'
END_MARK = '\033[0m'

def getGrid(str):
'''
Computes and returns a 2D list of booleans from the input string.
Grid is surrounded in a "frame" of False values (representing the "unfilled"
border) to make finding squares at the edge of the grid easier.
'''
grid = [
[True if char == '1' else False for char in line]
for line in str.split('\n')
]
rowLength = len(grid[0])
if any(len(row) != rowLength for row in grid):
raise ValueError('Input grid must have equal-length rows.')
boundaryRow = [False for x in grid[0]]
grid.insert(0, boundaryRow)
grid.append(boundaryRow)
return [
[False] + row + [False]
for row in grid
]

def getSquareStarts(row):
'''
Computes a list of 2-tuples, each giving the start and end indices of a contiguous filled segment in this row.
End indices are exclusive: a tuple (2,5) means that there's a contiguous filled segment covering cells 2,3, and 4.
'''
contiguousSegments = []
previousWasFilled = False
inContiguousSegment = False
for i, cell in enumerate(row):
if previousWasFilled and cell:
if inContiguousSegment:
contiguousSegments[-1] = (contiguousSegments[-1][0], i + 1)
else:
contiguousSegments.append((i - 1, i + 1))
inContiguousSegment = previousWasFilled and cell
previousWasFilled = cell
return contiguousSegments

def findSquaresInGrid(grid):
'''
Returns a list containing (x, y, sidelength) tuples where x and y give the coordinates of the top left corner of a
filled square in the given grid.
'''
squares = []
for i, row in enumerate(grid):
for startIndex, endIndex in getSquareStarts(row):
# So far we've found a single contiguous horizontal line of filled cells that might be the start of a square.
# Now we just need to check a bunch of things to see if it really is one.
sidelength = endIndex - startIndex
if (
# are there enough rows left in the (non-bordered) grid to fit a square this tall?
i + sidelength <= len(grid) - 1
# do all segments from startIndex to endIndex in rows below this one have all filled spaces?
and all(
all(row[startIndex:endIndex])
for row in grid[i:i + sidelength]
)
# does the previous row have all unfilled spaces adjacent to this segment?
and not any(grid[i - 1][startIndex:endIndex])
# does the row after the last expected row of the square have all unfilled spaces adjacent to this segment?
and not any(grid[i + sidelength][startIndex:endIndex])
# does the column to the left of the left side of the expected square have all unfilled spaces?
and not any(row[startIndex - 1] for row in grid[i:i + sidelength])
# does the column to the right of the right side of the expected square have all unfilled spaces?
and not any(row[endIndex] for row in grid[i:i + sidelength])
):
squares.append((startIndex - 1, i -1, sidelength))
return squares

def markSquares(inputString):
'''
Finds solid squares of "1"'s in the given input and returns a new string with each square marked in bold.
'''
squares = findSquaresInGrid(getGrid(inputString))
output = inputString.split('\n')
for i in range(len(squares)):
cornerX, cornerY, sidelength = squares[i]
for y in range(cornerY, cornerY + sidelength):
output[y] = (
output[y][:cornerX]
+ MARK
+ output[y][cornerX:cornerX + sidelength]
+ END_MARK
+ output[y][cornerX + sidelength:]
)
# adjust x indices that were affected by the insertion of the formatting characters
squares = [
(
otherX + len(MARK) + len(END_MARK) if otherY in range(cornerY, cornerY + sidelength) and otherX >= cornerX else otherX,
otherY,
otherSidelength
)
for otherX, otherY, otherSidelength in squares
]
return '\n'.join(output)

def main():
if stdin.isatty():
print 'Enter a grid. Enter a blank line when done.'
inputString = ''
inputLine = None
while inputLine != '':
try:
inputLine = raw_input()
except EOFError:
break
inputString += inputLine + '\n'
inputString = inputString.strip()
print markSquares(inputString)

if __name__ == '__main__':
main()
``````

Fun thing: save a 2D 0's and 1's Menger sponge generated by this script and pass it to my python script to see it highlight everything nicely.

``````python mark_squares.py < menger_sponge.txt
``````