How to check if a set of coordinates matches a tetris piece in Python

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)

edited Nov 19 '18 at 12:15

asked Nov 19 '18 at 11:04

Legatro

1,3553917

2

subtract a threshhold (e,g: the vector of the origin block) from all the coordiantes such that your origin block ends up on [0.0] and then compare with a predefined list of tetris pieces?
– vencaslac
Nov 19 '18 at 11:09

1

do you care about rotations?
– Maarten Fabré
Nov 19 '18 at 11:10

1

Besides rotations, do you also want to consider reflections? (traditionally reflections are considered to be different pieces, as in, they have different colors in classic Tetris, but I don't know for you). Importantly, is the order of the given coordinates guaranteed? That is, do they always start in the same "origin" block, and cover the piece in the same relative order?
– jdehesa
Nov 19 '18 at 12:01

@jdehesa Reflections would also help with the solution I'm looking for. The origin block will always be the same for a given piece, and the ordering will be the same. I've elaborated on this in the question to make it more clear. Thanks!
– Legatro
Nov 19 '18 at 12:11

add a comment |

I’m working with tetris pieces.

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.

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)

edited Nov 19 '18 at 12:15

asked Nov 19 '18 at 11:04

Legatro

1,3553917

2

subtract a threshhold (e,g: the vector of the origin block) from all the coordiantes such that your origin block ends up on [0.0] and then compare with a predefined list of tetris pieces?
– vencaslac
Nov 19 '18 at 11:09

1

do you care about rotations?
– Maarten Fabré
Nov 19 '18 at 11:10

1

Besides rotations, do you also want to consider reflections? (traditionally reflections are considered to be different pieces, as in, they have different colors in classic Tetris, but I don't know for you). Importantly, is the order of the given coordinates guaranteed? That is, do they always start in the same "origin" block, and cover the piece in the same relative order?
– jdehesa
Nov 19 '18 at 12:01

@jdehesa Reflections would also help with the solution I'm looking for. The origin block will always be the same for a given piece, and the ordering will be the same. I've elaborated on this in the question to make it more clear. Thanks!
– Legatro
Nov 19 '18 at 12:11

add a comment |

I’m working with tetris pieces.

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.

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)

edited Nov 19 '18 at 12:15

asked Nov 19 '18 at 11:04

Legatro

1,3553917

I’m working with tetris pieces.

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.

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)

python numpy coordinates tetris

edited Nov 19 '18 at 12:15

asked Nov 19 '18 at 11:04

Legatro

1,3553917

edited Nov 19 '18 at 12:15

asked Nov 19 '18 at 11:04

Legatro

1,3553917

edited Nov 19 '18 at 12:15

asked Nov 19 '18 at 11:04

Legatro

1,3553917

asked Nov 19 '18 at 11:04

Legatro

1,3553917

asked Nov 19 '18 at 11:04

Legatro

1,3553917

2

subtract a threshhold (e,g: the vector of the origin block) from all the coordiantes such that your origin block ends up on [0.0] and then compare with a predefined list of tetris pieces?
– vencaslac
Nov 19 '18 at 11:09

1

do you care about rotations?
– Maarten Fabré
Nov 19 '18 at 11:10

1

Besides rotations, do you also want to consider reflections? (traditionally reflections are considered to be different pieces, as in, they have different colors in classic Tetris, but I don't know for you). Importantly, is the order of the given coordinates guaranteed? That is, do they always start in the same "origin" block, and cover the piece in the same relative order?
– jdehesa
Nov 19 '18 at 12:01

@jdehesa Reflections would also help with the solution I'm looking for. The origin block will always be the same for a given piece, and the ordering will be the same. I've elaborated on this in the question to make it more clear. Thanks!
– Legatro
Nov 19 '18 at 12:11

add a comment |

2

subtract a threshhold (e,g: the vector of the origin block) from all the coordiantes such that your origin block ends up on [0.0] and then compare with a predefined list of tetris pieces?
– vencaslac
Nov 19 '18 at 11:09

1

do you care about rotations?
– Maarten Fabré
Nov 19 '18 at 11:10

1

Besides rotations, do you also want to consider reflections? (traditionally reflections are considered to be different pieces, as in, they have different colors in classic Tetris, but I don't know for you). Importantly, is the order of the given coordinates guaranteed? That is, do they always start in the same "origin" block, and cover the piece in the same relative order?
– jdehesa
Nov 19 '18 at 12:01

@jdehesa Reflections would also help with the solution I'm looking for. The origin block will always be the same for a given piece, and the ordering will be the same. I've elaborated on this in the question to make it more clear. Thanks!
– Legatro
Nov 19 '18 at 12:11

subtract a threshhold (e,g: the vector of the origin block) from all the coordiantes such that your origin block ends up on [0.0] and then compare with a predefined list of tetris pieces?
– vencaslac
Nov 19 '18 at 11:09

do you care about rotations?
– Maarten Fabré
Nov 19 '18 at 11:10

Besides rotations, do you also want to consider reflections? (traditionally reflections are considered to be different pieces, as in, they have different colors in classic Tetris, but I don't know for you). Importantly, is the order of the given coordinates guaranteed? That is, do they always start in the same "origin" block, and cover the piece in the same relative order?
– jdehesa
Nov 19 '18 at 12:01

@jdehesa Reflections would also help with the solution I'm looking for. The origin block will always be the same for a given piece, and the ordering will be the same. I've elaborated on this in the question to make it more clear. Thanks!
– Legatro
Nov 19 '18 at 12:11

add a comment |

1 Answer
1

active

oldest

votes

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.

edited Nov 19 '18 at 12:32

answered Nov 19 '18 at 12:26

jdehesa

22.2k43150

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53373245%2fhow-to-check-if-a-set-of-coordinates-matches-a-tetris-piece-in-python%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

# 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.

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.

edited Nov 19 '18 at 12:32

answered Nov 19 '18 at 12:26

jdehesa

22.2k43150

add a comment |

# 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.

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.

edited Nov 19 '18 at 12:32

answered Nov 19 '18 at 12:26

jdehesa

22.2k43150

add a comment |

# 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.

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.

edited Nov 19 '18 at 12:32

answered Nov 19 '18 at 12:26

jdehesa

22.2k43150

# 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.

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.

edited Nov 19 '18 at 12:32

answered Nov 19 '18 at 12:26

jdehesa

22.2k43150

edited Nov 19 '18 at 12:32

answered Nov 19 '18 at 12:26

jdehesa

22.2k43150

answered Nov 19 '18 at 12:26

jdehesa

22.2k43150

answered Nov 19 '18 at 12:26

jdehesa

22.2k43150

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu