棋盘病毒模拟中的逻辑错误
Logic Error in Chessboard Virus Simulation
棋盘病毒问题类似于康威的“生命游戏”。规则是任何两个有被感染邻居的方格都会被感染。
我试过在Python中实现模拟,但是有逻辑错误。我认为正在发生的事情是董事会在一轮内更新,因此错过了中间步骤。例如,用
grid = [
[0, 1, 0, 1],
[1, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
我得到以下输出:
Initial State of board:
0 1 0 1
1 0 0 0
0 0 0 0
0 0 0 0
State 2 of board:
1 1 1 1
1 1 1 1
0 0 0 0
0 0 0 0
Infinite loop entered.
第一轮应该只显示
1 1 1 1
1 1 0 0
0 0 0 0
0 0 0 0
除非我记错了。
谁能帮我解决逻辑错误?
grid = [
[0, 1, 0, 1],
[1, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
def write(grid):
"""
Writes the lists of lists of booleans
in grid using 0 for False and 1 for True.
"""
for row in grid:
for item in row:
print(f" {item}", end="")
print()
def neighbors(grid, i, j):
"""
Returns the number of live cells
next to grid[i][j]. Does not include diagonals.
"""
num_neighbours = 0
if i > 0:
if grid[i - 1][j]:
num_neighbours = num_neighbours + 1
if i < len(grid) - 1:
if grid[i + 1][j]:
num_neighbours = num_neighbours + 1
if j > 0:
if grid[i][j - 1]:
num_neighbours = num_neighbours + 1
if j < len(grid[i]) - 1:
if grid[i][j + 1]:
num_neighbours = num_neighbours + 1
print(num_neighbours)
return num_neighbours
def update(grid):
"""
Applies the rule of the chessboard virus to grid
and returns a new grid.
"""
new_board = grid[:]
for i in range(len(grid)):
for j in range(len(grid[i])):
num_neighbours = neighbors(grid, i, j)
if num_neighbours >= 2:
new_board[i][j] = 1
return new_board
def check_all_ones(a):
return not any(c != 1 for r in a for c in r)
def main():
"""
Runs the simulation.
"""
global grid
grid = grid
print("Initial State of board:")
print()
write(grid)
state_num = 1
while True:
last_grid = grid[:] # Clone grid.
grid = update(grid)
state_num = state_num + 1
print()
print(f"State {state_num} of board:")
print()
write(grid)
if check_all_ones(grid):
print()
print("Virus has spread to whole board.")
break
if grid == last_grid:
print()
print("Infinite loop entered.")
break
if __name__ == "__main__":
main()
我认为问题在于 new_board = grid[:]
不是 'deep' 副本 - 各个行列表是来自 grid
的原始列表对象,因此更新步骤设置 + 查找所有第一次扫描中新填充的邻居。
它似乎适用于深拷贝,例如,使用 new_board = [r.copy() for r in grid]
或 new_board = copy.deepcopy(grid)
(thnx @Demi-Lune)。
正如下面@Ramirez 的评论中所述,这同样适用于主循环中的克隆。
棋盘病毒问题类似于康威的“生命游戏”。规则是任何两个有被感染邻居的方格都会被感染。
我试过在Python中实现模拟,但是有逻辑错误。我认为正在发生的事情是董事会在一轮内更新,因此错过了中间步骤。例如,用
grid = [
[0, 1, 0, 1],
[1, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
我得到以下输出:
Initial State of board:
0 1 0 1
1 0 0 0
0 0 0 0
0 0 0 0
State 2 of board:
1 1 1 1
1 1 1 1
0 0 0 0
0 0 0 0
Infinite loop entered.
第一轮应该只显示
1 1 1 1
1 1 0 0
0 0 0 0
0 0 0 0
除非我记错了。
谁能帮我解决逻辑错误?
grid = [
[0, 1, 0, 1],
[1, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
def write(grid):
"""
Writes the lists of lists of booleans
in grid using 0 for False and 1 for True.
"""
for row in grid:
for item in row:
print(f" {item}", end="")
print()
def neighbors(grid, i, j):
"""
Returns the number of live cells
next to grid[i][j]. Does not include diagonals.
"""
num_neighbours = 0
if i > 0:
if grid[i - 1][j]:
num_neighbours = num_neighbours + 1
if i < len(grid) - 1:
if grid[i + 1][j]:
num_neighbours = num_neighbours + 1
if j > 0:
if grid[i][j - 1]:
num_neighbours = num_neighbours + 1
if j < len(grid[i]) - 1:
if grid[i][j + 1]:
num_neighbours = num_neighbours + 1
print(num_neighbours)
return num_neighbours
def update(grid):
"""
Applies the rule of the chessboard virus to grid
and returns a new grid.
"""
new_board = grid[:]
for i in range(len(grid)):
for j in range(len(grid[i])):
num_neighbours = neighbors(grid, i, j)
if num_neighbours >= 2:
new_board[i][j] = 1
return new_board
def check_all_ones(a):
return not any(c != 1 for r in a for c in r)
def main():
"""
Runs the simulation.
"""
global grid
grid = grid
print("Initial State of board:")
print()
write(grid)
state_num = 1
while True:
last_grid = grid[:] # Clone grid.
grid = update(grid)
state_num = state_num + 1
print()
print(f"State {state_num} of board:")
print()
write(grid)
if check_all_ones(grid):
print()
print("Virus has spread to whole board.")
break
if grid == last_grid:
print()
print("Infinite loop entered.")
break
if __name__ == "__main__":
main()
我认为问题在于 new_board = grid[:]
不是 'deep' 副本 - 各个行列表是来自 grid
的原始列表对象,因此更新步骤设置 + 查找所有第一次扫描中新填充的邻居。
它似乎适用于深拷贝,例如,使用 new_board = [r.copy() for r in grid]
或 new_board = copy.deepcopy(grid)
(thnx @Demi-Lune)。
正如下面@Ramirez 的评论中所述,这同样适用于主循环中的克隆。