Python: как сделать мою 4-х цветную шашку более читабельной

Question

Я пытался написать общую программу для проверки Проблема 17x17 РЕШЕНА! , 4-цветная сетка a17x17 без монохроматических прямоугольников.Ссылка на решение: 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. Вы должны четко отделить логику для ввода / вывода от логики проверки (это в основном относится к любому коду). Это также включает в себя то, что вы помещаете определения только на верхний уровень модуля. Фактическая программа обычно переходит в условное, как в приведенном ниже коде, который выполняется только в том случае, если файл вызывается непосредственно из командной строки (а не если он только 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)

Answer 2

Обязательный однострочный *!

Предполагая, что вы загрузили данные 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

Answer 3

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