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?
8
a 2D array of zeros and ones, where a 0 means empty and 1 means occupied
means that this:
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.