3

我正在尝试编写一个通用程序来检查17x17 问题已解决！, 4 色 17x17 网格，没有单色矩形。解决方案链接：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，因此非常欢迎任何建议。

4

4 回答 4

4
  1. 您应该清楚地将输入/输出逻辑与验证逻辑分开（这基本上适用于任何代码）。这还包括您只将定义放在模块的顶层。实际程序通常会进入如下代码中的条件语句，该条件语句仅在直接从命令行调用文件时执行（而不是仅import由另一个文件编辑）。
  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)
于 2012-02-11T03:33:26.797 回答
1 
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)
于 2012-02-11T03:37:29.267 回答
1

强制性单线*！

假设您已将 17x17 数据加载到numpy array命名A中（请参阅@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
于 2012-02-11T03:52:36.673 回答
0

这是另一种思考方式。

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)
于 2012-02-11T05:15:13.747 回答