Nsryjdtyk

I’m working with tetris pieces.

The pieces are defined with coordinates, where each piece has an origin block (0,0)
So an L piece could be defined as [(0,0), (0,1), (0,2), (1,2)] as well as [(0,-1), (0,0), (0,1), (1,1)] depending on where you place the origin block.

I want to check whether a set of coordinates A e.g. [(50,50), (50,51), (50,52), (51,52)] matches the shape of a given tetris piece B.

I’m currently using numpy to take away one of the A values from every value in A to reach relative coordinates, then compare with B. The ordering of A will always been in increasing order, but is not guarenteed to match the ordering of B. B is stored in a list with other tetris pieces, and throughout the program, it's origin block will remain the same. This method below seems inefficient and doesn’t account for rotations / reflections of B.

def isAinB(A,B):  # A and B are numpy arrays

    for i in range(len(A)):

        matchCoords = A - A[i]

        setM = set([tuple(x) for x in matchCoords])

        setB = set([tuple(x) for x in B])

        if setM == setB:  # Sets are used here because the ordering of M and B are not guarenteed to match

            return True

    return False

Is there an efficient method / function to implement this? (Accounting for rotations and reflections aswell if possible)

This is one way to approach it. The idea is to first build all the set of variations of a piece in some canonical coordinates (you can do this once per piece kind and reuse it), then put the given piece in the same canonical coordinates and compare.

# 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

These are some tests:

# 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

This is not a particularly smart algorithm, but it works with minimal constraints.

EDIT: Since in your case you say that the first block and the relative order will always be the same, you can redefine the canonical coordinates as follows to make it just a bit more optimal (although the performance difference will probably be negligible and its use will be more restricted):

def canonical_coords(coords):

    return tuple((y - coords[0][0], x - coords[0][1]) for x, y in coords[1:])

The first coordinate will always be (0, 0), so you can skip that and use it as reference point for the rest, and instead of a frozenset you can use a tuple for the sequence of coordinates.