Programming Challenge: Shape detection.

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