N-colorable grid checker

17x17_yes.txt

22133421413223443
24211233443411322
31344411143241232
41231323412144134
31112324234443221
13324314412212323
31424223321414413
43121113244323412
44334242312321211
12221344143334241
42343213231432141
42412414322133332
13212441333422114
14143334321121424
24122432134314133
33234132224231144
23443141424112231

3x3_no.txt

AAA
ABA
AAA

3x3_yes.txt

AAA
BAB
ABB

ncolor_check.py

import sys

def check(_grid):
	"""This function takes as an argument a string
	containing the colors of a grid.

	Use any unique character to represent a different color.
	Separate each line by a line break.

	Test on command line with:
	
	  $ cat 3x3_no.txt | python ncolor_check.py
	
	The 3x3_no.txt file should contain a lot of mono-chrome
	rectangles.  The _yes.txt files are good.
	"""
	lines = filter(None, _grid.split())

	def get_size(lines):
		"""Determine the size of a grid, and check to make sure it
		is of proper size"""
		w = len(lines[0])
		if any(w != len(line) for line in lines):
			print "Your grid isn't a rectangle yo"
			raise Exception
		return w, len(lines)

	def get_n_colors(lines):
		"""Get the number of colors in a grid and return a set
		of colors as well"""
		colors = set()
		for line in lines:
			for x in line:
				colors.add(x)
		return len(colors), colors

	def _check(lines, colors):
		"""Check lines for monochromatic rectangles, and return
		the number found"""
		n = 1
		cmap = {}
		for c in colors:
			cmap[c] = n
			n = n * 2
		grid = tuple((tuple(cmap[c] for c in line) for line in lines))
		found = 0
		for a in range(len(grid)-1):
			for b in range(a+1, len(grid)):
				c = [_a & _b for _a, _b in zip(grid[a], grid[b])]
				for i in range(len(c)):
					for j in range(i):
						if c[i] != 0 and c[i] == c[j]:
							found = found + 1
							print "rectangle found with vertices:"
							print "", a, i
							print "", a, j
							print "", b, i
							print "", b, j
		return found

	grid_width, grid_height = get_size(lines)
	n_colors, colors = get_n_colors(lines)

	print grid_width, "by", grid_height, "grid has", n_colors, "colors"
	found = _check(lines, colors)
	if found > 0:
		print "Solution is not correct"
	else:
		print "Solution is good!"

if __name__ == "__main__":
	check(sys.stdin.read())