这是一种方法。其思想是首先在一些标准坐标系中构建一个工件的所有变量集(每种工件都可以这样做一次并重用它),然后将给定的工件放在相同的标准坐标系中并进行比较。
# Rotates a piece by 90 degrees
def rotate_coords(coords):
return [(y, -x) for x, y in coords]
# Returns a canonical coordinates representation of a piece as a frozen set
def canonical_coords(coords):
x_min = min(x for x, _ in coords)
y_min = min(y for _, y in coords)
return frozenset((y - y_min, x - x_min) for x, y in coords)
# Makes all possible variations of a piece (optionally including reflections)
# as a set of canonical representations
def make_piece_variations(piece, reflections=True):
variations = {canonical_coords(piece)}
for i in range(3):
piece = rotate_coords(piece)
variations.add(canonical_coords(piece))
if reflections:
piece_reflected = [(y, x) for x, y in piece]
variations.update(make_piece_variations(piece_reflected, False))
return variations
# Checks if a given piece is in a set of variations
def matches_piece(piece, variations):
return canonical_coords(piece) in variations
以下是一些测试:
# L-shaped piece
l_piece = [(0, 0), (0, 1), (0, 2), (1, 2)]
l_piece_variations = make_piece_variations(l_piece, reflections=True)
# Same orientation
print(matches_piece([(50, 50), (50, 51), (50, 52), (51, 52)], l_piece_variations))
# True
# Rotated
print(matches_piece([(50, 50), (51, 50), (52, 50), (52, 49)], l_piece_variations))
# True
# Reflected and rotated
print(matches_piece([(50, 50), (49, 50), (48, 50), (48, 49)], l_piece_variations))
# True
# Rotated and different order of coordinates
print(matches_piece([(50, 48), (50, 50), (49, 48), (50, 49)], l_piece_variations))
# True
# Different piece
print(matches_piece([(50, 50), (50, 51), (50, 52), (50, 53)], l_piece_variations))
# False
这不是一个特别聪明的算法,但它在最小的约束下工作。
编辑:因为在您的例子中,您说第一个块和相对顺序总是相同的,所以您可以重新定义规范坐标,如下所示,使其更为优化(尽管性能差异可能可以忽略不计,而且其使用将受到更多限制):
def canonical_coords(coords):
return tuple((y - coords[0][0], x - coords[0][1]) for x, y in coords[1:])
第一个坐标将始终是(0,0),因此您可以跳过它并将其用作其余坐标的参考点,而不是
frozenset
你可以用
tuple
坐标序列。