Instantly share code, notes, and snippets.

# sirpengi/17x17_yes.txt Created Feb 14, 2012

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