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

Raed Tabani
  • 537
  • 1
  • 4
  • 7
  • 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 Aug 25 '16 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 Aug 25 '16 at 16:29
  • 1
    Could you show a drawing or something to help illustrate the question? – Tulains Córdova Aug 25 '16 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 Aug 25 '16 at 17:29
  • @TulainsCórdova sure, updated – Raed Tabani Aug 25 '16 at 17:29
  • Well, that's not what you asked in your question. You asked about "efficiency." If you now want "novel" answers, of the kind that are learning exercises only, then you should ask about that instead. – Robert Harvey Aug 25 '16 at 18:30
  • "Assuming that we didn't keep track of the height" - well, what kind of trackkeeping do you want to be excluded, which kind do think is acceptable? If you do not keep track of anything than the 2D board itself, and forbid, for example, even the sums mentioned by @CandiedOrange, I guess your binary search approach cannot be beaten in terms of efficiency. – Doc Brown Aug 25 '16 at 20:32
  • Well, you surely read my comment and had time enough for clarification. Downvoted and voting to close as "unclear". I consider to change this when you answer my question. – Doc Brown Aug 27 '16 at 08:41

1 Answers1

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.

candied_orange
  • 102,279
  • 24
  • 197
  • 315