Покритикуйте, пожалуйста, код и подскажите как его сделать лучше, с учетом выбранного языка программирования.
Смысл кода — задача Да Винчи. Есть квадрат заданной размерности у которого все клетки белые. Мы можем отметить любую клетку квадрата, окрасив ее в черный цвет. При этом смежные клетки сменят свой цвет на противоположный. Код ищет все коомбинации клеток, которые надо отметить, чтобы квадрат полностью сменил свой цвет.
Так вызов:
c = Calculator(Board(2))
c.run()
Дает результат:
['1', '1', '1', '1']
Что говорит о том, что все вершины (они считаются сверху вниз и слева направо) нужно пометить.
Если интресно, то, насколько я знаю, задача не имеет доказательства, но методом перебора (для тех размерностей квадрата, что поддаются этому перебору) удалось показать, что решение существует для квадратов всех размерностей. Более того, решение существует для прямоугольников. И более того, оно существует для любой фигуры, составленной из клеток, даже с пустотами внутри.
Сам код:
'''
Created on 29.09.2010
@author: ademidov
'''import copy
class Combination:
def __init__(self, combination, board):
self.orig = copy.copy(combination)
self.combination = combination
self.board = board
def mask(self):
mask = dict()
for i in range(len(self.combination)):
mask[i] = 0
for pos, element in enumerate(self.combination):
if (element == '1'):
for neighbour in self.board.neighbours(pos):
mask[neighbour] = mask[neighbour] + 1
return mask
def check(self):
for element in self.combination:
if (element == '0'):
return False
return True
def calc(self):
for pos, value in self.mask().items():
if ((value == 1) or (value == 3)):
self.invert(pos)
def invert(self, pos):
if(self.combination[pos] == '0'):
self.combination[pos] = '1';
else:
self.combination[pos] = '0'def original(self):
return self.orig
class Board:
def __init__(self, size):
self.side = size
self.size = size * size
def posToXY(self, pos):
y = round(pos / self.side)
x = pos - y * self.side
return [x, y]
def xyToPos(self, x, y):
return y * self.side + x
def neighbours(self, pos):
result = []
[x, y] = self.posToXY(pos)
if( x > 0):
result.append(self.xyToPos(x - 1, y))
if( x < self.side - 1):
result.append(self.xyToPos(x + 1, y))
if( y > 0):
result.append(self.xyToPos(x, y - 1))
if( y < self.side - 1):
result.append(self.xyToPos(x, y + 1))
return result
class Calculator:
def __init__(self, board):
self.board = board
self.side = board.side
self.size = board.size
def combinations(self):
result = []
for n in range(2**self.size):
binVal = bin(n)[2:].zfill(self.size)
result.append(Combination([ x for x in binVal], self.board))
return result
def processCombination(self, combination):
combination.calc()
if(combination.check()):
print combination.original()
def run(self):
for combination in self.combinations():
self.processCombination(combination)
c = Calculator(Board(2))
c.run()
Здравствуйте, DemAS, Вы писали:
DAS>Покритикуйте, пожалуйста, код и подскажите как его сделать лучше, с учетом выбранного языка программирования.
DAS>Сам код:
DAS>''' DAS>Created on 29.09.2010
DAS>@author: ademidov DAS>'''
DAS>import copy
DAS>class Combination:
Лучше написать class Combination(object):
DAS> def __init__(self, combination, board): DAS> self.orig = copy.copy(combination)
Можно обойтись и без copy — self.orig = combination[:] DAS> self.combination = combination DAS> self.board = board
DAS> def mask(self): DAS> mask = dict() DAS> for i in range(len(self.combination)): DAS> mask[i] = 0
Посмотрите defaultdict
DAS> for pos, element in enumerate(self.combination):
Посмотрите izip DAS> if (element == '1'):
Если бы элементы были True и False, код был бы красивее. Скобки после if не нужны. DAS> for neighbour in self.board.neighbours(pos): DAS> mask[neighbour] = mask[neighbour] + 1
эээ. += 1 DAS> return mask
DAS> def check(self): DAS> for element in self.combination: DAS> if (element == '0'): DAS> return False DAS> return True
Если бы элементы были типа bool, можно было бы заменить на return all(self.combination)
DAS> def calc(self): DAS> for pos, value in self.mask().items(): DAS> if ((value == 1) or (value == 3)):
Можно заменить на value in (1,3) DAS> self.invert(pos)
DAS> def invert(self, pos): DAS> if(self.combination[pos] == '0'): DAS> self.combination[pos] = '1'; DAS> else: DAS> self.combination[pos] = '0'
С булевом получилось бы self.combination[pos] = not self.combination[pos]
DAS> def original(self): DAS> return self.orig
DAS>class Board: DAS> def __init__(self, size): DAS> self.side = size DAS> self.size = size * size
DAS> def posToXY(self, pos): DAS> y = round(pos / self.side) DAS> x = pos — y * self.side DAS> return [x, y]
Лучше возвратить tuple, просто написать return x, y
DAS> def xyToPos(self, x, y): DAS> return y * self.side + x
DAS> def neighbours(self, pos): DAS> result = [] DAS> [x, y] = self.posToXY(pos)
Можно без скобок обойтись DAS> if( x > 0): DAS> result.append(self.xyToPos(x — 1, y)) DAS> if( x < self.side — 1): DAS> result.append(self.xyToPos(x + 1, y)) DAS> if( y > 0): DAS> result.append(self.xyToPos(x, y — 1)) DAS> if( y < self.side — 1): DAS> result.append(self.xyToPos(x, y + 1))
DAS> return result
DAS>class Calculator: DAS> def __init__(self, board): DAS> self.board = board DAS> self.side = board.side DAS> self.size = board.size
DAS> def combinations(self): DAS> result = [] DAS> for n in range(2**self.size): DAS> binVal = bin(n)[2:].zfill(self.size) DAS> result.append(Combination([ x for x in binVal], self.board))
[ x for x in binVal] заменяется на list(binVal) DAS> return result
DAS> def processCombination(self, combination): DAS> combination.calc() DAS> if(combination.check()): DAS> print combination.original()
DAS> def run(self): DAS> for combination in self.combinations(): DAS> self.processCombination(combination)
Здравствуйте, DemAS, Вы писали:
DAS>Покритикуйте, пожалуйста, код и подскажите как его сделать лучше, с учетом выбранного языка программирования.
Покритикую саму реализацию алгоритма. Без привязки к языку
Как я понял, алгоритм заключается в следующем:
1. Генерируем все возможные последовательности 0 и 1 определенной длины.
2. Каждая такая последовательность является комбинацией.
3. Обрабатываем доску на основе этой комбинации.
а) подсчитывыем для каждой клетки количество соседей, которые на нее могли повлиять
б) по количеству соседей определяем надо ли ее инвертировать
4. Если получилась доска, состоящая из единиц — выводим комбинацию
Так вот. Данный алгоритм размазан на три класса и нигде явно не прослеживается.
А сами классы сильно связаны друг с другом, что запутывает код.
Я бы сделал так:
1. Изменил бы распределение обязанностей между классами
class Board
get(int row, int col): int
set(int row, int col, int value)
invert(int row, int col)
class Combination
Combination(последовательность нулей и единиц) -- конструктор
get(int row, int col)
Остальное бы сделал на функциях
getAllCombination(size) -- возвращает все возможные комбинации (можно сделать на yield)
isGoodCombination(board, combination) -- проверка комбинации, в принипе, можно поместить в класс Board
search(size):
b = Board(size)
for c in getAllCombination(size):
if isGoodCombination(b,c):
print result
2. Еще несколько замечаний:
а) явно использовать в публичных контрактах пару (row,col), а не индекс (row*size+col)
б) заменить "((value == 1) or (value == 3))" на "value % 2 == 1", если я правильно понял смысл этого выражения
в) можно по другому рассчитывать (calc) доску. Фактически при расчете производится подсчет количества единичных соседей (в маске). На основании этого количества определяется необходимость инвертирования. Сейчас при просмотре комбинации соседи подсчитываются по чуть-чуть (+1). По-моему лучше сделать подсчет явным — для каждой клетки сразу посчитать количество единичных соседей в маск. Другими словами, в расчете сделать цикл не по клеткам Комбинации, а по клеткам Доски.
DAS>Если интресно, то, насколько я знаю, задача не имеет доказательства, но методом перебора (для тех размерностей квадрата, что поддаются этому перебору) удалось показать, что решение существует для квадратов всех размерностей. Более того, решение существует для прямоугольников. И более того, оно существует для любой фигуры, составленной из клеток, даже с пустотами внутри.
А можно указать источник задачи с более подробным описанием? В гугле почему-то не нашел по словам задача/проблема Да Винчи.
Дело в том, что для любого квадрата, заполненного белыми клетками существует очевидное решение — комбинация в которой ВСЕ клетки надо пометить (о задаче сужу в первую очередь по представленной реализации). В то же время по Вашим словам только методом перебора "удалось показать, что решение существует для квадратов всех размерностей". Нестыковка какая-то, или я чего-то не понимаю?
Здравствуйте, Буравчик, Вы писали:
Б>Дело в том, что для любого квадрата, заполненного белыми клетками существует очевидное решение — комбинация в которой ВСЕ клетки надо пометить (о задаче сужу в первую очередь по представленной реализации).
Да, вроде квадрат 3 x 3 уже не решается предложенным тобой способом... ?
Здравствуйте, DemAS, Вы писали:
DAS> Да, вроде квадрат 3 x 3 уже не решается предложенным тобой способом... ?
Запустил программу и проверил, опасаясь, что допустил ошибку. Нет, ошибки вроде нет — вот единственное решение:
['1', '0', '1', '0', '1', '0', '1', '0', '1']
или так, если нагляднее:
x o x
o x o
x o x
Для проверки можно взять любой из ноликов. По твоей методике состояние этих клеток будет перещелкнуто 4 раза: 3 раза при щелчке по соседним клеткам и один раз по ним самим.
А правильно ли я понимаю, что если я заменю функцию:
def combinations(self):
result = []
for n in range(2**self.size):
binVal = bin(n)[2:].zfill(self.size)
result.append(Combination([ x for x in binVal], self.board))
return result
на
def combinations(self):
for n in range(2**self.size):
binVal = bin(n)[2:].zfill(self.size)
yield Combination([ x for x in binVal], self.board)
то получу тот же самый результат, но со значительно меньшими затратами памяти?
Здравствуйте, DemAS, Вы писали:
DAS>Для проверки можно взять любой из ноликов. По твоей методике состояние этих клеток будет перещелкнуто 4 раза: 3 раза при щелчке по соседним клеткам и один раз по ним самим.
Разобрался. Меня запутала фраза "Мы можем отметить любую клетку квадрата, окрасив ее в черный цвет. При этом смежные клетки сменят свой цвет на противоположный". Я посчитал, что смежные клетки инвертируются, а выбранная клетка просто окрашивается в черный цвет (не инвертируется). После прочтения блога все стало ясно.
Здравствуйте, DemAS, Вы писали:
DAS>Смысл кода — задача Да Винчи. Есть квадрат заданной размерности у которого все клетки белые. Мы можем отметить любую клетку квадрата, окрасив ее в черный цвет. При этом смежные клетки сменят свой цвет на противоположный. Код ищет все коомбинации клеток, которые надо отметить, чтобы квадрат полностью сменил свой цвет.
Эту задачу можно решить без перебора.
Возьмем пустой (белый) квадрат 2х2. И обозначим клетки буквами.
a b
c d
Пусть буква может принимать значение 0 или 1. Если 0, то не закрашиваем клетку, если 1 — то закрашиваем.
Тогда для каждой клетки должно выполняться правило: клетка + её смежные клетки = 1 (по модулю 2)
Например, для клетки а уравнение будет выглядеть так: a + b + c = 1 (по модулю 2)
Вспоминаем, что операция xor — это и есть сложение по модулю 2. Обозначим xor как *.
Тогда наше уравнение станет таким:
a * b * c = 1
Для удобства примем, что в правой части уравнения всегда стоит 0.
Чтобы избавиться от единицы справа выполним операцию (xor 1) с левой и правой частью.
a * b * c * 1 = 0
Идея в том, чтобы составить систему аналогичных линейных уравнений для каждой клетки и затем решить эту систему.
Приведу пример для квадрата 2х2.
Строим уравнения для каждой клетки:
a * b * c * 1 = 0
a * b * d * 1 = 0
a * c * d * 1 = 0
b * c * d * 1 = 0
Далее решаем эту систему выражая одни переменные через другие.
Из первого уравнения получаем: a = b * c * 1. Подставляя в остальные получаем:
c * d = 0
b * d = 0
b * c * d * 1 = 0
Из первого уравнения получаем: c = d. Подставляя в остальные получаем:
b * d = 0
b * 1 = 0
Из первого уравнения получаем: b = d. Подставляя в остальные получаем:
d * 1 = 0
Отсюда следует, что d = 1
И далее в обратном порядке:
b = d = 1
c = d = 1
a = b * c * 1 = 1 * 1 * 1 = 1
Т.е. a = b = c = d = 1, это и есть решение для квадрата 2х2
Аналогичным образом можно составить и решить систему уравнений для любого прямоугольника с любой окраской.
Самое главное — избавились от экпоненциальной сложности. Получили полиномиальную.
Это позволяет посчитать решения и для 50, и для 100 и далее
Процесс решения у нас может закончиться следующими вариантами:
Вариант 1. На каком-то шаге мы получили противоречивое уравнение вида 1 = 0. Тогда решений у исходного прямоугольника нет.
Вариант 2. Мы решили систему и все переменные либо имеют значение, либо определены через другие переменные. Тогда исходный прямоугольник имеет ровно одно решение.
Вариант 3. Мы решили систему и некоторые переменные остались свободными, т.е. их значение не определено через другие переменные (хотя сами они могут быть использованы в вычислении переменных). Тогда исходный прямоугольник имеет несколько решений. Чтобы получить их все достаточно подставлять 0 и 1 в свободные переменные и вычислять на их основе остальные переменные.
Здравствуйте, Буравчик, Вы писали:
Б>Эту задачу можно решить без перебора.
Я написал на Haskell програмку, которая находит решения приведенным выше способом. И интересная вешь получается.
Оказывается, количество решений не зависит от раскраски квадрата Зависит только от его размера.
Например, для исходного квадрата 4х4, неважно изначально белый он, полностью или частично закрашеный, всегда будет 16 решений.
А для любого квадрата 2х2 всегда одно решение.
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Буравчик, Вы писали:
Б>>Эту задачу можно решить без перебора.
Б>Я написал на Haskell програмку, которая находит решения приведенным выше способом. И интересная вешь получается.
Здравствуйте, DemAS, Вы писали:
DAS>... что решение существует для квадратов всех размерностей. Более того, решение существует для прямоугольников. И более того, оно существует для любой фигуры, составленной из клеток, даже с пустотами внутри.
Вопрос. Есть исходный квадрат 4х4.
В нем закрашена одна клетка (х).
oХoo
oooo
oooo
oooo
Надо перекрасить его в черный цвет. Что-то я не смог найти решение
Здравствуйте, Буравчик, Вы писали:
Б>Надо перекрасить его в черный цвет. Что-то я не смог найти решение
Ну, мой исходник, работающий методом перебора тоже не выдает решений
Но я напрягся и нашел источник задачи — Квант, первый номер за 2008 год. Есть в электронном виде — если надо вышлю.
На странице 29 написанно именно это утверждение, если я, конечно, что-то не упустил.
Здравствуйте, DemAS, Вы писали:
DAS> Ну, мой исходник, работающий методом перебора тоже не выдает решений DAS> Но я напрягся и нашел источник задачи — Квант, первый номер за 2008 год. Есть в электронном виде — если надо вышлю. DAS> На странице 29 написанно именно это утверждение, если я, конечно, что-то не упустил.
Я прочитал статью. Там речь идет не о рисунке на каком-нибудь прямоугольнике, а об фигуре вырезанной из бумаги.
Т.е. я (мы?) рассматриваю, например, такой изрисованный прямоугольник, который надо докрасить.
oooooo
ooxxoo
oxxxxo
ooxxoo
oooooo
Автор же говорит о такой фигуре (вместо прямоугольника), которую надо полностью закрасить
Зависит только от его размера.