0

Lets say that our Tetris board is represented as a 2D array of zeros and ones, where a 0 means empty and 1 means occupied, and you where asked to find the highest row in which a tetromino exists.

Assuming that we didn't keep track of the height that is for every tetramino placed check if its row is > previously placed tetromino, if so then height = row.

Obviously the most inefficient way is to iterate through the whole 2D array and perhaps stop whenever a full row of zeros is encountered. Another approach that I thought of is binary search, where you start at the middle row and check if it's empty then my new interval is limited to rows below, else the row of interests is located top.

  • Is this an efficient way of finding height?
  • What is a better approach?

enter image description here

Improve this question
8
  • 5
    How large of a board are you contemplating? If it's less than, say, 100 x 100, the brute-force approach is almost certainly the most efficient one. Binary searches and the like work better with extremely large data sets, not relatively small ones like this.
    – Robert Harvey
    Commented Aug 25, 2016 at 16:12
  • I agree with Robert Harvey, if we are talking about a regular tetris board, even if it seems that brute force is "bad" for a small data set is the simplest (not necessarily the fastest). If you a looking at a huge Tetris board (lets suppose 1000x1000) then the binary search becomes a better option
    – Oscar Picchi
    Commented Aug 25, 2016 at 16:29
  • 1
    Could you show a drawing or something to help illustrate the question?
    – Tulains Córdova
    Commented Aug 25, 2016 at 16:45
  • it's a regular sized tetris board, but I'm interested in learning about different and "neat" ways to find the height. could the tetris board be represented as a graph instead of an array and using dfs turn this into a path finding problem?
    – Raed Tabani
    Commented Aug 25, 2016 at 17:29
  • @TulainsCórdova sure, updated
    – Raed Tabani
    Commented Aug 25, 2016 at 17:29

1 Answer 1

Reset to default
3

a 2D array of zeros and ones, where a 0 means empty and 1 means occupied

means that this:

enter image description here

looks like this:

0000000000
0010000101
1110001111
1111111110
1110111111

You want to know the height of the highest block. 3 in this case. Last time I played this game you also wanted to know when a row was filled so you could eliminate it. There is a simple calculation you can do that will answer both questions. Sum the rows.

0000000000 = 0 
0010000101 = 3 <= first non zero sum
1110001111 = 7  
1111111110 = 9 
1110111111 = 9

First non zero from the top is the highest. Same calculation will tell you a row should be removed when it hits 10.

It's not fancy but who cares? It's fast, it works, and it's easy to debug.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.