Python：如何使我的 4 色检查器更具可读性

Question

我试图编写一个通用程序来检查 17x17 问题已解决！，17x17 网格的 4 色，没有单色矩形。解决方案链接：17.txt。

这就是我写的：

from itertools import product

def is_solution(myfile,m,n):
    """ m-lines, n-columns """
    grid = [c.strip() for c in line.split(',')] for line in open(myfile).readlines()]
    for x0,y0 in product(xrange(m),xrange(n)):
        start = grid[x0][y0]
        for x in xrange(x0+1,m):
            if grid[x][y0] == start:
                for y in xrange(y0+1,n):
                    if grid[x0][y] == start == grid[x][y]:
                            return False
    return True


print is_solution('17.txt',17,17)

是否有一种更易读、简洁或有效的方式（按优先顺序）来编写此内容？也许对不同的数据结构有不同的方法......因为我现在正在学习Python，所以非常欢迎任何建议。

Answer 1

1. 您应该将输入/输出逻辑与验证逻辑完全分开（这基本上适用于任何代码）。这还包括您仅将定义放在模块的顶层。实际的程序通常会进入如下代码所示的条件，仅当直接从命令行调用该文件时才会执行该条件（如果仅由另一个文件导入则不会执行）。
2. 网格的尺寸可以从输入中得出。这里不需要单独的参数。
3. 您应该使用整数而不是字符串（这是可选的，但更干净，IMO）

我的尝试（从 STDIN 获取文件，可以像 python script.py <17.txt 一样调用）：

import itertools

def has_monochromatic_rectangles(grid):
  # use range instead of xrange here (xrange is not in Python 3)
  points = list(itertools.product(range(len(grid)), range(len(grid[0]))))
  # check if for any rectangle, all 4 colors are equal
  # (this is more brute-force than necessary, but you placed simplicity
  # above efficiency. Also, for 17x17, it doesn't matter at all ;)
  return any(grid[x1][y1] == grid[x1][y2] == grid[x2][y1] == grid[x2][y2]
             for (x1,y1), (x2,y2) in itertools.product(points, points)
             if x1 != x2 and y1 != y2)

def has_max_colors(grid, most):
  # collect all grid values and uniquify them by creating a set
  return len(set(sum(grid, []))) <= most

if __name__ == '__main__':
  # read from STDIN (could easily be adapted to read from file, URL, ...)
  import sys
  grid = [map(int, line.split(',')) for line in sys.stdin]

  assert has_max_colors(grid, 4)
  assert not has_monochromatic_rectangles(grid)

Answer 2

import urllib
grid=urllib.urlopen("http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17.txt")
grid=[map(int,row.split(",")) for row in grid]
print grid

def check_grid(grid):
    for i in range(17):
        for j in range(17):
            for i2 in range(i):
                for j2 in range(j):
                    colours=[grid[a][b] for a in (i,i2) for b in (j,j2)]
                    assert(len(set(colours))>1)

check_grid(grid)
grid[1][1]=2
check_grid(grid)

Answer 3

强制性单行*！

假设您已将 17x17 数据加载到名为 A 的 numpy array 中（请参阅 @robertking 使用 urllib 的答案），您可以使用一行 numpy！

 print (array([len(set(A[i:i+k1,j:j+k2][zip(*[(0,0), (0,-1),(-1,0),(-1,-1)])])) for i in xrange(16) for j in xrange(16) for k1 in xrange(2,17) for k2 in xrange(2,17)])!=1).all()

* 实际上不要在一行中执行此操作。为了清楚起见，这里对其进行了一些扩展：

corners = zip(*[(0,0), (0,-1),(-1,0),(-1,-1)])

for k1 in xrange(2,17):
    for k2 in xrange(2,17):
        for i in xrange(16):
            for j in xrange(16):

                # Pull out each sub-rectange
                sub = A[i:i+k1, j:j+k2]

                # Only use the corners
                sub = sub[corners]

                # Count the number of unique elements
                uniq = len(set(sub))

                # Check if all corners are the same
                if uniq == 1: 
                    print False
                    exit()
print True

Answer 4

这是另一种思考方式。

import urllib
grid=urllib.urlopen("http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17.txt")
grid=[map(int,row.split(",")) for row in grid]

def check(grid):
    colour_positions=lambda c,row:set(i for i,colour in enumerate(row) if colour==c) #given a row and a colour, where in the row does that colour occur
    to_check=[[colour_positions(c,row) for row in grid] for c in range(1,5)] #for each row and each colour, get the horizontal positions.
    from itertools import combinations
    for i in to_check:
        for a,b in combinations(i,2):
            if len(a&b)>1: #for each colour, for each combination of rows, do we ever get more than 1 horizontal position in common (e.g. a rectangle)
                return False
    return True

print check(grid)
grid[1][1]=2
print check(grid)