Falling Blocks

Pieces made of four squares fall one by one into a well that is width columns wide (numbered from 0 on the left) and has no top. The seven shapes are drawn below, with '#' for the squares of the piece, and your starter code already has them as SHAPES:

I: ####     O: ##     T: ###     S: .##
               ##        .#.        ##.

Z: ##.      J: #..    L: ..#
   .##         ###       ###

drops is a list of tuples (shape, turns, col). For each one, in order:

• Take the picture of shape and turn it a quarter turn clockwise, turns times (0 to 3). For example, T turned once becomes the three rows .#, ## and .#.
• Place the turned picture high above everything in the well, with its leftmost column at column col (it always fits inside the well).
• Let it fall straight down, with no sideways movement, until moving one more row down would make one of its squares overlap a filled square or go below the floor. Its squares then become filled.
• Every row that is now completely filled is removed, and all the rows above it move down by one row. Squares do not fall any further than that, even if there is space below them.

Write drop_blocks(width, drops) that returns a tuple (height, cleared): the height of the pile after all the drops (the number of rows from the floor up to and including the highest row that has a filled square, or 0 if the well is empty), and the total number of rows removed.

Examples

drop_blocks(4, [('I', 0, 0)])                  # returns (0, 1)
drop_blocks(6, [('O', 0, 0), ('O', 0, 4)])     # returns (2, 0)
drop_blocks(4, [('O', 0, 0), ('O', 0, 2)])     # returns (0, 2)
drop_blocks(5, [('T', 0, 0), ('I', 1, 4)])     # returns (4, 0)

In the first example the bar fills the bottom row of a 4-column well, which is removed at once. In the last one, the T lands with its stem on the floor, so its arms hang over two empty squares that nothing can ever fill, and the bar turned upright stands 4 squares tall in column 4.

Constraints

• 4 <= width <= 12; drops has 0 to 20,000 items.