3

17x17 の問題を確認するための一般的なプログラムを作成しようとしていました。、単色の長方形のない a17x17 グリッドの 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を学んでいるので、どんなアドバイスも大歓迎です。

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(urllib を使用するための @robertking の回答を参照) にロードしたと仮定すると、numpy を使用して 1 行で実行できます。

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

* 実際にはこれを 1 行で実行しないでください。ここでは、わかりやすくするために少し展開しています。

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 に答える