Stacking Bars
MediumOnline Assessment
Simulate bars of lumber being dropped onto a narrow shelf, where full rows are cleared.
The shelf has width columns (numbered from 0, left to right) and room for height rows. Row 1 is the floor. Each bar is a pair [column, length]: a horizontal bar that covers length consecutive columns starting at column, one cell thick. Bars are dropped one at a time, in order. Bars only move straight down, never sideways, and cells are never pushed around by later bars.
For each bar:
- Validity. If
length < 1,column < 0, orcolumn + length > width, the bar does not fit on the shelf. Ignore it completely (do not clip it). - Landing. The bar falls until it rests on something. It comes to rest in row
1 + h, wherehis the largest number such that some column the bar covers has a filled cell in rowh(andh = 0if none of its columns has any filled cell). Gaps underneath an overhang stay empty and can never be filled again by a later bar, because bars are blocked by the highest filled cell in each column. - Height limit. If the landing row is above row
height, the bar does not fit: ignore it. The shelf is unchanged. - Placement and clearing. Fill the bar's cells in its landing row. If that row is now completely filled, remove it: every row above it moves down by one row as a whole (cells keep their column and their gaps; nothing falls into the empty cells under overhangs).
Input: width and height, integers, and bars, a list of [column, length] pairs.
Output: the final shelf as a list of strings, one per row from the top row down to the floor row, with # for a filled cell and . for an empty one. Include rows only up to the highest row that has a filled cell; if the shelf is empty return [].
Example 1
- Input:
- [4,4,[[0,3],[2,2],[0,2],[1,1],[3,1],[2,1]]]
- Output:
- [".##."]
- Explanation
- On a 4-wide, 4-high shelf, [0,3] lands on the floor (
###.). [2,2] rests on column 2 and fills row 2 at columns 2-3 (..##). [0,2] lands on column 1's stack too, so it fills row 2 at columns 0-1 and the row becomes####: it is removed. [1,1] lands on the floor row's column 1 (row 2,.#..), then [3,1] fills the last gap of the floor row, which is removed, so the lone cell drops to the floor. Finally [2,1] lands next to it on the floor:.##..
Example 2
- Input:
- [4,5,[[0,2],[1,3],[0,1],[0,4],[3,1],[2,2]]]
- Output:
- ["..##","##.#"]
- Explanation
- [0,2] lands on the floor (
##..). [1,3] covers columns 1-3 and rests on column 1's cell, so it is in row 2 (.###) and the floor cell below columns 2 and 3 stays empty. [0,1] fills row 2 column 0 and completes the row, which is removed. [0,4] rests on column 1 at row 2 and completes it again; it is removed too. [3,1] lands on the floor, in the gap that is still free (##.#). [2,2] rests on column 3's cell and fills row 2 at columns 2-3, leaving the floor cell at column 2 permanently empty underneath it.
Example 3
- Input:
- [3,2,[[0,2],[1,2],[1,2],[2,2],[0,0],[0,3]]]
- Output:
- [".##","##."]
- Explanation
- [0,2] lands on the floor and [1,2] on column 1's cell (row 2,
.##). The second [1,2] would have to rest in row 3, but the shelf is only 2 rows high, so it is ignored. [2,2] runs past column 2 (2 + 2 = 4 > 3), [0,0] has length 0, and [0,3] would also land in row 3 (column 1 is 2 high): all ignored. Final shelf.##over##..
Constraints
- 1 ≤ width ≤ 12 and 1 ≤ height ≤ 30
- 0 ≤ bars.length ≤ 200
- -3 ≤ column ≤ width + 3 and 0 ≤ length ≤ width + 3 for each bar, so some bars are invalid