Python Deep list сравнения

Question

В настоящее время я пишу программу для решения sudoku в python только для удовольствия. Вот что я в настоящее время:

#!/usr/bin/env python 
"""Reads in a file formatted with nine lines each of which has nine characters 
corresponding to a sudoku puzzle. A blank is indicated by the value '0' 
Eventually should output a solution to the input puzzle""" 

import sys 

class cell: 
    value = 0 
    """Value of 0 means it is undetermined""" 

    def __init__(self, number): 
     self.value = number 
     self.possible = [2, 2, 2, 2, 2, 2, 2, 2, 2] 
     """Possibility a given value can be the number. 0 is impossible, 1 is definite, 2 is maybe""" 



    def selfCheck(self): 
     """Checks if the cell has only one possible value, changes the value to that number""" 
     if self.value == 0: 
       if self.possible.count(2) == 1: 
       """If there's only one possible, change the value to that number""" 
       i = 1 
       for item in self.possible: 
        if item == 2: 
         self.value = i 
         self.possible[i-1] = 1 
        i+=1 

def checkSection(section): 
    """For any solved cells in a section, marks other cells as not being that value""" 
    for cell in section: 
     if cell.value != 0: 
      for otherCell in section: 
       otherCell.possible[cell.value-1] = 0 

def checkChunk(chunk): 
    """Checks a chunk, the set of rows, columns, or squares, and marks any values that are impossible for cells based on that 
    chunk's information""" 
    for section in chunk: 
     checkSection(section) 

def selfCheckAll(chunk): 
    for section in chunk: 
     for cell in section: 
      cell.selfCheck() 

cellRows = [[],[],[],[],[],[],[],[],[]] 
cellColumns = [[],[],[],[],[],[],[],[],[]] 
cellSquares = [[],[],[],[],[],[],[],[],[]] 

infile = open(sys.argv[1], 'r') 
"""Reads the file specified on the command line""" 

i = 0 
for line in infile: 
    """Reads in the values, saves them as cells in 2d arrays""" 
    line = line.rstrip('\n') 
    for char in line: 
     row = i/9 
     column = i%9 
     newcell = cell(int(char)) 
     cellRows[row].append(newcell) 
     cellColumns[column].append(newcell) 
     row = (row/3)*3 
     column = column/3 
     square = row+column 
     cellSquares[square].append(newcell) 
     i+=1 
i = 0 
while i<50: 
    checkChunk(cellRows) 
    checkChunk(cellColumns) 
    checkChunk(cellSquares) 
    selfCheckAll(cellRows) 

    i+=1 

displayRow = [] 
for row in cellRows: 
    for cell in row: 
     displayRow.append(str(cell.value)) 

i = 0 
while i < 9: 
    output1 = ''.join(displayRow[9*i:9*i+3]) 
    output2 = ''.join(displayRow[9*i+3:9*i+6]) 
    output3 = ''.join(displayRow[9*i+6:9*i+9]) 
    print output1 + ' ' + output2 + ' ' + output3 
    if i%3 == 2: 
     print 
    i+=1 

Моя проблема с:

i = 0 
while i<50: 
    checkChunk(cellRows) 
    checkChunk(cellColumns) 
    checkChunk(cellSquares) 
    selfCheckAll(cellRows) 

    i+=1 

Я хочу, чтобы запустить код до тех пор, пока не обнаружит, что нет никаких изменений от предыдущей итерации вместо текущего жёстко 50 раз. Это может быть связано с тем, что уже нет логического следующего шага (нужно начинать грубые форсирующие значения), или головоломка полностью решена. В любом случае, мне нужна глубокая копия одного из моих текущих наборов данных для головоломки (скажем, cellRows), чтобы сравнить с тем, какие изменения могут произойти с фактической копией, когда она проходит через мои функции checkChunk.

Есть ли что-нибудь подобное в Python? (Если есть лучший способ проверить, закончен ли я, это также сработает, хотя на данный момент меня больше интересует, если я смогу сделать глубокое сравнение.)

EDIT - я попытался использовать copy.deepcopy , Хотя это создало хорошую глубокую копию, проверка равенства между двумя, использующая '==', всегда возвращалась false.

Answer 1

Очень грубое сравнение может быть сделано путем сравнения str(). Конечно, это не лучший способ сделать это, но, учитывая сложность ваших списков, все может быть в порядке.

Если вы хотите что-то более прочное, вы можете написать рекурсивную функцию, чтобы позаботиться об этом.

Answer 2

Универсальные устройства для глубокого копирования предоставляются в стандартном модуле copy: то, что вы ищете, является функцией copy.deepcopy.

Answer 3

Вы всегда можете разложить объекты и сравнить их как строки. Преобразование их в строку JSON, вероятно, является одним из самых простых способов. Я подозреваю, что есть более ресурсоэффективный способ сделать это, но он работает отлично. Вот пример:

>>> from simplejson import dumps 
>>> ls1 = [1, [2, 3], [4, [5, 6]]] 
>>> ls2 = [1, [2, 3], [4, [5, 6]]] 
>>> dumps(ls1) == dumps(ls2) 
True 
>>> 

Answer 4

Я не уверен, что сравнение строковых представлений является путь, но если производительность является проблемой, я думаю, вы можете тест. Вот быстрая попытка реализации глубинного/рекурсивного список сравнения:

from itertools import izip 

def list_compare(a, b): 
    if type(a) != type(b): 
     return False 
    if type(a) != list: 
     return a == b 
    if len(a) != len(b): 
     return False 
    for a_, b_ in izip(a, b): 
     if not list_compare(a_, b_): 
      return False 
    return True 

Он сравнивает списки рекурсивно и без элементов списка с помощью регулярного оператора равенства.

Answer 5

В вашем случае это всего лишь двумерный список. Следовательно, преобразование их в одномерный список строк и их сравнение сделают код наименьшим.

list_of_list = [[1, 2, 3, 4, 5, 6, 7, 8], [2, 3, 4, 5, 6, 7, 8, 1], [3, 4, 5, 6, 7, 8, 1, 2], [4, 5, 6, 7, 8, 1, 2, 3], [5, 6, 7, 8, 1, 2, 3, 4], [6, 7, 8, 1, 2, 3, 4, 5], [7, 8, 1, 2, 3, 4, 5, 6], [8, 1, 2, 3, 4, 5, 6, 7]] 
current_iteration = ",".join(["".join(map(str, row)) for row in list_of_list]) 
previous_iteration = ",".join(["".join(map(str, row)) for row in list_of_list]) 
if current_iteration == previous_iteration: 
    return 

Как только строка сгенерирована, вы можете преобразовать сравнительную доску таким же образом и сравнить их одинаково.

Однако, я хотел бы предложить, что сравнение их как списки непосредственно будет намного проще читать

previous_iteration = [[1,2,3], [2,3,1], [3,1,2]] 
current_iteration = [[1,2,3], [2,3,1], [3,1,2]] 

if len(current_iteration) != len(previous_iteration): 
# This check is not required in your case as the lengths will be same for all iterations 
    return False 

for index, item_list in enumerate(current_iteration): 
    if item_list != previous_iteration[index]: 
     return False 

return True