修改矩阵.Python非常有趣的任务

Question

假设，我们有以下列表

mag = [
    [0, 1, 1, 1],
    [0, 1, 0, 1],
    [1, 1, 0, 1],
    [0, 1, 0, 1],
]

问题：需要添加或合并新行，例如[1, 0, 0, 1]。

Rule ：如果我添加了与某些行相重叠的列表，则应附加或合并，具体取决于已与所提供的项目重叠。

示例（开头的mag矩阵）：

mag.add([0, 0, 1, 0])
[
    [0, 1, 1, 1], # << -- here is were overlapped
    [0, 1, 1, 1], # << -- here will be merged
    [1, 1, 0, 1],
    [0, 1, 0, 1],
]

示例2 （开始时MAG矩阵）：

mag.add([0, 1, 0, 0])
[
    [0, 1, 1, 1],
    [0, 1, 0, 1],
    [1, 1, 0, 1],
    [0, 1, 0, 1], # << -- overlaps first list from end, will be appended
    [0, 1, 0, 0],
]

示例3 （开始时Mag Matrix）：

mag.add([1, 0, 0, 0])
[
    [0, 1, 1, 1],
    [0, 1, 0, 1],
    [1, 1, 0, 1], # << -- overlaps here
    [1, 1, 0, 1], # << -- here were merged
]

更清楚，假设这是Tetris，其中诸如[0, 1, 0, 1]之类的新列表是1是一个块，而0是一个自由空间。我们需要了解图形从底部移到顶部的位置。

Answer 1

在这里，我们从末端循环循环矩阵，在每行重叠时检查。如果是这样，我们会编辑上一行。如果它到达矩阵的顶部，我们将其合并。

def overlap(a, b):
    return any(x&y for x, y in zip(a, b))
def merge(a, b):
    return [x|y for x, y in zip(a, b)]
def update_matrix(mat, row):
    if overlap(mat[-1], row): # If the new row doesn't fit at all, add it at the end
        mat.append(row)
        return
    for ind, line in enumerate(reversed(mat)):
        if overlap(line, row):
            change_index = ~(ind-1)  # This trick uses negative indexing to index 
                                     # from the end of the list
            break  # We have the row to merge
    else:
        change_index = 0  # We got to the top, so we need to change the first row
    mat[change_index] = merge(mat[change_index], row)

Answer 2

这是使用numpy的矢量化解决方案。总体想法是通过检查几个条件来更新mag。首先，mag必须是0，其值上面的值必须为1，并且该更新将应用于新行包含1的列上。

一般解决方案如下：

def add(x, row):
    import numpy as np
    # Check that the row above contains a 1
    c1 = np.roll(x, 1, axis = 0) == 1
    # Coordinates on where to update with a 1
    ix_x, ix_y = (c1 & (x == 0) & (np.array(row) == 1)[:,None].T).nonzero()
    # If any values satisfy the condition update with a 1
    if ix_x.size > 0:
        mag[ix_x.min(), ix_y] = 1
    else:
        # Otherwise stack the new row at the end
        x = np.vstack([x, row])
    return x

---

现在，请使用3个建议的示例检查：

# Example 1
row = [0, 0, 1, 0]
add(mag,row)
array([[0, 1, 1, 1],
       [0, 1, 1, 1],
       [1, 1, 0, 1],
       [0, 1, 0, 1]])
# Example 2
row = [0, 1, 0, 0]
add(mag,row)
array([[0, 1, 1, 1],
       [0, 1, 0, 1],
       [1, 1, 0, 1],
       [0, 1, 0, 1],
       [0, 1, 0, 0]])
# Example 3
row = [1, 0, 0, 0]
add(mag,row)
array([[0, 1, 1, 1],
       [0, 1, 0, 1],
       [1, 1, 0, 1],
       [1, 1, 0, 1]])