Problem 598088 · hard · Phase 05 Advanced Algorithms & Graphs

Rigid Rubble

gauntlet · simulation · grids · fixpoint iteration

A demolition site is drawn as a list of equal-length strings grid. Row 0 is the top. Each cell is . (empty), # (a fixed rock that never moves and is never removed) or an uppercase letter. All cells carrying the same letter form one rigid piece, whether or not those cells touch each other; a piece always moves as a whole and keeps its shape.

Process the board as follows.

  1. Settle. Decide which pieces are held: start with no piece held, then repeatedly mark as held any piece that has at least one cell that is in the bottom row, or directly above a rock, or directly above a cell of a different piece that is already held. Stop when no new piece can be marked. Every piece that is not held moves down exactly one row, all of them at the same time. Repeat this step until every piece is held.
  2. Clear. A row is full when it contains no . and at least one letter. If there are no full rows, the process ends. Otherwise, in every full row (all at once) each letter cell becomes .; rocks stay. Pieces keep their letters, so a piece that lost some cells is still one rigid piece made of its remaining cells (it may have no cells left). Count the rows cleared, then go back to step 1.

Return a tuple (final_grid, cleared): the final board as a list of strings and the total number of rows cleared.

Examples

Input:  grid = ["D...",
                "..E.",
                "..E.",
                "AA.B",
                "#A.B"]
Output: (["....", "....", "....", "D...", "#..."], 2)
Explanation: A and B touch the bottom row, so they are held. E falls two rows
into the gap and D falls onto A. Rows 3 and 4 are now full and are cleared
(the rock stays). D then falls one more row and lands on the rock.

Input:  grid = [".BB.",
                ".B..",
                "A...",
                "AA.#",
                "..#."]
Output: (["....", "....", ".BB.", "AB.#", "AA#."], 0)

Constraints

  • 1 <= len(grid) <= 30, 1 <= len(grid[0]) <= 30, all rows have the same length
  • every character is ., # or an uppercase letter A-Z

Goals

  • Model rigid multi-cell pieces that move as a unit on a grid
  • Compute which pieces are supported with an iterate-until-stable marking pass
  • Alternate two phases (settling and clearing) until neither changes the board
Starting Python…