Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
N-colorable grid checker
22133421413223443
24211233443411322
31344411143241232
41231323412144134
31112324234443221
13324314412212323
31424223321414413
43121113244323412
44334242312321211
12221344143334241
42343213231432141
42412414322133332
13212441333422114
14143334321121424
24122432134314133
33234132224231144
23443141424112231
AAA
ABA
AAA
AAA
BAB
ABB
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())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment