import Mathlib /-! # Bricks Falling When Hit You are given an m x n binary grid, where each 1 represents a brick and 0 represents an empty space. A brick is stable if: It is directly connected to the top of the grid, or At least one other brick in its four adjacent cells is stable. You are also given an array hits, which is a sequence of erasures we want to apply. Each time we want to erase the brick at the location hits[i] = (row_i, col_i). The brick on that location (if it exists) will disappear. Some other bricks may no longer be stable because of that erasure and will fall. Once a brick falls, it is immediately erased from the grid (i.e., it does not land on other stable bricks). Return an array result, where each result[i] is the number of bricks that will fall after the ith erasure is applied. Note that an erasure may refer to a location with no brick, and if it does, no bricks drop. ## Constraints - m == grid.length - n == grid[i].length - 1 <= m, n <= 200 - grid[i][j] is 0 or 1. - 1 <= hits.length <= 4 * 10^4 - hits[i].length == 2 - 0 <= x_i <= m - 1 - 0 <= y_i <= n - 1 - All (x_i, y_i) are unique. ## Provided examples - `grid = [[1, 0, 0, 0], [1, 1, 1, 0]], hits = [[1, 0]]` → `[2]` - `grid = [[1, 0, 0, 0], [1, 1, 0, 0]], hits = [[1, 1], [1, 0]]` → `[0, 0]` - `grid = [[0]], hits = [[0, 0]]` → `[0]` ## Synthesized negative examples - invalid input: `grid = [[1, 0], [1]], hits = [[0, 0]]` ([structural] a predicate that admits n == grid[i].length. row lengths differ; a predicate using only grid[0].length accepts it) - invalid input: `grid = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], hits = [[0, 200]]` ([structural] a predicate that admits 1 <= m, n <= 200. one past the stated width; a predicate checking only m ignores n) - invalid input: `grid = [[2]], hits = [[0, 0]]` ([structural] a predicate that admits grid[i][j] is 0 or 1.. a predicate that accepts any nonzero value takes 2 as a brick) - `grid = [[1, 0, 0, 0], [1, 1, 1, 0]], hits = [[1, 0]]` → `[1]` is wrong ([structural] the returned count is one less than the true number that fall. one step below the correct count) - `grid = [[1, 0, 0, 0], [1, 1, 0, 0]], hits = [[1, 1], [1, 0]]` → `[-1, 0]` is wrong ([structural] result[0] is -1, a negative value that can never equal a count of falling bricks. negative counts are below any possible fall count) - `grid = [[0]], hits = [[0, 0]]` → `[1]` is wrong ([structural] drops the clause that hits on empty cells cause no drops. assumes the hit erases a brick and counts it) -/ namespace PBricksFallingWhenHit abbrev Input := (List (List Nat)) × (List (List Nat)) abbrev Output := List Int /-! ### Specification helpers -/ /-- The value stored in cell `(r, c)` of `g`, or `0` when the coordinate is out of range. -/ def cellAt (g : List (List Nat)) (r c : Nat) : Nat := (g.getD r []).getD c 0 /-- `p` and `q` share a side, i.e. they are four-adjacent cells. -/ def Adjacent (p q : Nat × Nat) : Prop := (p.1 = q.1 ∧ (p.2 + 1 = q.2 ∨ q.2 + 1 = p.2)) ∨ (p.2 = q.2 ∧ (p.1 + 1 = q.1 ∨ q.1 + 1 = p.1)) /-- `(r, c)` holds a brick connected to the top row through a path of adjacent bricks. -/ def IsStable (g : List (List Nat)) (r c : Nat) : Prop := ∃ c₀ : Nat, cellAt g 0 c₀ = 1 ∧ Relation.ReflTransGen (fun p q : Nat × Nat => Adjacent p q ∧ cellAt g q.1 q.2 = 1) (0, c₀) (r, c) /-- `g` with cell `(r, c)` overwritten by `v`; out-of-range coordinates leave `g` unchanged. -/ def setCell (g : List (List Nat)) (r c v : Nat) : List (List Nat) := g.set r ((g.getD r []).set c v) /-- The coordinate pair `(r, c)` named by a hit row `[r, c]`. -/ def hitCoord (h : List Nat) : Nat × Nat := (h.getD 0 0, h.getD 1 0) /-- One erasure step: `fallen` is exactly the set of cells occupied in `before` with the brick at `hit` cleared that were stable in `before` but not after the erasure, and `after` is the erased grid with every cell of `fallen` cleared. -/ def FallsStep (before : List (List Nat)) (hit : Nat × Nat) (fallen : Finset (Nat × Nat)) (after : List (List Nat)) : Prop := let erased := setCell before hit.1 hit.2 0 (∀ p : Nat × Nat, p ∈ fallen ↔ cellAt erased p.1 p.2 = 1 ∧ IsStable before p.1 p.2 ∧ ¬ IsStable erased p.1 p.2) ∧ ∀ r c : Nat, cellAt after r c = if (r, c) ∈ fallen then 0 else cellAt erased r c /-! ### Validity predicate (V) -/ /-- Valid input: a rectangular binary grid with 1 to 200 rows and 1 to 200 columns, and a list of 1 to 40000 distinct in-bounds hit pairs, each of length exactly 2. -/ def isValidInput (input : Input) : Bool := let grid := input.1 let hits := input.2 let m := grid.length let n := (grid.getD 0 []).length 1 ≤ m && m ≤ 200 && 1 ≤ n && n ≤ 200 && grid.all (fun row => row.length == n && row.all (fun cell => cell ≤ 1)) && 1 ≤ hits.length && hits.length ≤ 40000 && hits.all (fun h => h.length == 2 && h.getD 0 0 < m && h.getD 1 0 < n) && hits.all (fun h => (hits.filter (fun h' => h' == h)).length == 1) /-! ### Ideal specification (P_spec) -/ /-- `result` has one entry per hit, and there exist a chain of grid states starting at `grid` and a fallen set for each hit such that every step obeys `FallsStep` and every entry of `result` is the cardinality of that step's fallen set. -/ def bricksFallingWhenHit_spec (input : Input) (result : Output) : Prop := result.length = input.2.length ∧ ∃ states : List (List (List Nat)), ∃ fallen : List (Finset (Nat × Nat)), states.length = input.2.length + 1 ∧ fallen.length = input.2.length ∧ states.getD 0 [] = input.1 ∧ ∀ i : Nat, i < input.2.length → FallsStep (states.getD i []) (hitCoord (input.2.getD i [])) (fallen.getD i ∅) (states.getD (i + 1) []) ∧ result.getD i 0 = ((fallen.getD i ∅).card : Int) /-! ### Decidable specification (P_check) -/ /-- The four side-adjacent neighbours of `p`; Nat underflow repeats cells, which the fill filters out. -/ def neighborsOf (p : Nat × Nat) : List (Nat × Nat) := [(p.1 + 1, p.2), (p.1, p.2 + 1), (p.1 - 1, p.2), (p.1, p.2 - 1)] /-- Every in-bounds coordinate of `g`, listed row by row. -/ def allCells (g : List (List Nat)) : List (Nat × Nat) := (List.range g.length).flatMap fun r => (List.range (g.getD r []).length).map fun c => (r, c) /-- Flood fill from `comp` through adjacent brick cells of `g`, with `fuel` bounding the iterations. -/ def stableCellsAux (g : List (List Nat)) (comp : List (Nat × Nat)) : Nat → List (Nat × Nat) | 0 => comp | fuel + 1 => let fresh := (comp.flatMap neighborsOf).foldl (fun acc q => if cellAt g q.1 q.2 == 1 && !comp.contains q && !acc.contains q then acc ++ [q] else acc) [] if fresh.isEmpty then comp else stableCellsAux g (comp ++ fresh) fuel /-- The cells connected to the top row through adjacent bricks, decided by flood fill. -/ def stableCells (g : List (List Nat)) : List (Nat × Nat) := let seeds := ((List.range (g.getD 0 []).length).filter fun c => cellAt g 0 c == 1).map fun c => (0, c) stableCellsAux g seeds (allCells g).length /-- The unique `FallsStep` witnesses for hit `h`: the fallen cells and the grid after they drop. -/ def stepFalls (g : List (List Nat)) (h : List Nat) : List (Nat × Nat) × List (List Nat) := let hit := hitCoord h let erased := setCell g hit.1 hit.2 0 let stableBefore := stableCells g let stableAfter := stableCells erased let fallen := (allCells erased).filter fun p => cellAt erased p.1 p.2 == 1 && stableBefore.contains p && !stableAfter.contains p let after := fallen.foldl (fun acc p => setCell acc p.1 p.2 0) erased (fallen, after) /-- Walk the hit chain, checking each reported count against the fallen cells of that step. -/ def checkChain (g : List (List Nat)) (hits : List (List Nat)) (result : List Int) : Bool := match hits, result with | [], [] => true | h :: hs, r :: rs => let (fallen, after) := stepFalls g h r == (fallen.length : Int) && checkChain after hs rs | _, _ => false /-- Executable checker for `bricksFallingWhenHit_spec` along the unique chain of grid states. -/ def bricksFallingWhenHit_check (input : Input) (result : Output) : Bool := input.2.length == result.length && checkChain input.1 input.2 result theorem bf_cellAt_setCell_zero (g : List (List Nat)) (r c r' c' : Nat) : cellAt (setCell g r c 0) r' c' = if r' = r ∧ c' = c then 0 else cellAt g r' c' := by unfold cellAt setCell simp only [List.getD_eq_getElem?_getD, List.getElem?_set] grind theorem bf_mem_allCells (g : List (List Nat)) (p : Nat × Nat) : p ∈ allCells g ↔ p.1 < g.length ∧ p.2 < (g.getD p.1 []).length := by unfold allCells simp grind theorem bf_brick_mem (g : List (List Nat)) (p : Nat × Nat) (h : cellAt g p.1 p.2 = 1) : p ∈ allCells g := by rw [bf_mem_allCells] unfold cellAt at h simp only [List.getD_eq_getElem?_getD] at * grind theorem bf_neighbors_adj (p q : Nat × Nat) (h : q ∈ neighborsOf p) : q = p ∨ Adjacent p q := by simp [neighborsOf, Adjacent, Prod.ext_iff] at * omega theorem bf_adj_neighbors (p q : Nat × Nat) (h : Adjacent p q) : q ∈ neighborsOf p := by simp [neighborsOf, Adjacent, Prod.ext_iff] at * omega theorem bf_allCells_nodup (g : List (List Nat)) : (allCells g).Nodup := by unfold allCells rw [List.nodup_flatMap] constructor · intro r _ exact (List.nodup_range).map (fun a b h => by simpa using h) · exact List.nodup_range.pairwise_of_forall_ne (fun a _ b _ hab => by simp [Function.onFun, List.disjoint_left]; grind) theorem bf_fold (g : List (List Nat)) (comp : List (Nat × Nat)) : ∀ (xs acc : List (Nat × Nat)), acc.Nodup → (xs.foldl (fun acc q => if cellAt g q.1 q.2 == 1 && !comp.contains q && !acc.contains q then acc ++ [q] else acc) acc).Nodup ∧ ∀ q, q ∈ xs.foldl (fun acc q => if cellAt g q.1 q.2 == 1 && !comp.contains q && !acc.contains q then acc ++ [q] else acc) acc ↔ q ∈ acc ∨ (q ∈ xs ∧ cellAt g q.1 q.2 = 1 ∧ q ∉ comp) := by intro xs induction xs with | nil => intro acc hacc; simp [hacc] | cons x xs ih => intro acc hacc rw [List.foldl_cons] by_cases hc : (cellAt g x.1 x.2 == 1 && !comp.contains x && !acc.contains x) = true · rw [if_pos hc] simp at hc have hn : (acc ++ [x]).Nodup := by rw [List.nodup_append]; simp; grind obtain ⟨h1, h2⟩ := ih (acc ++ [x]) hn refine ⟨h1, fun q => ?_⟩ rw [h2]; simp; grind · rw [if_neg hc] obtain ⟨h1, h2⟩ := ih acc hacc refine ⟨h1, fun q => ?_⟩ rw [h2] simp at hc simp; grind theorem bf_isStable_congr (g g' : List (List Nat)) (hc : ∀ r c, cellAt g r c = cellAt g' r c) (r c : Nat) : IsStable g r c ↔ IsStable g' r c := by have hf : cellAt g = cellAt g' := funext fun r => funext fun c => hc r c unfold IsStable rw [hf] theorem bf_isStable_brick (g : List (List Nat)) (r c : Nat) (h : IsStable g r c) : cellAt g r c = 1 := by obtain ⟨c₀, h0, hr⟩ := h cases hr with | refl => exact h0 | tail _ hs => exact hs.2 theorem bf_aux_succ (g : List (List Nat)) (comp : List (Nat × Nat)) (fuel : Nat) : stableCellsAux g comp (fuel + 1) = (if ((comp.flatMap neighborsOf).foldl (fun acc q => if cellAt g q.1 q.2 == 1 && !comp.contains q && !acc.contains q then acc ++ [q] else acc) []).isEmpty then comp else stableCellsAux g (comp ++ (comp.flatMap neighborsOf).foldl (fun acc q => if cellAt g q.1 q.2 == 1 && !comp.contains q && !acc.contains q then acc ++ [q] else acc) []) fuel) := rfl theorem bf_aux (g : List (List Nat)) : ∀ (fuel : Nat) (comp : List (Nat × Nat)), comp.Nodup → (∀ p ∈ comp, IsStable g p.1 p.2) → (allCells g).length ≤ comp.length + fuel → (∀ p ∈ stableCellsAux g comp fuel, IsStable g p.1 p.2) ∧ comp ⊆ stableCellsAux g comp fuel ∧ (∀ p ∈ stableCellsAux g comp fuel, ∀ q, Adjacent p q → cellAt g q.1 q.2 = 1 → q ∈ stableCellsAux g comp fuel) := by intro fuel induction fuel with | zero => intro comp hnd hst hlen show (∀ p ∈ comp, IsStable g p.1 p.2) ∧ comp ⊆ comp ∧ (∀ p ∈ comp, ∀ q, Adjacent p q → cellAt g q.1 q.2 = 1 → q ∈ comp) refine ⟨hst, List.Subset.refl _, fun p _ q _ hq => ?_⟩ by_contra hqn have hsub : (q :: comp) ⊆ allCells g := by intro x hx rcases List.mem_cons.mp hx with rfl | hx · exact bf_brick_mem g _ hq · exact bf_brick_mem g _ (bf_isStable_brick g _ _ (hst x hx)) have := (List.subperm_of_subset (List.nodup_cons.mpr ⟨hqn, hnd⟩) hsub).length_le simp only [List.length_cons] at this omega | succ fuel ih => intro comp hnd hst hlen rw [bf_aux_succ] obtain ⟨hfn, hfm⟩ := bf_fold g comp (comp.flatMap neighborsOf) [] List.nodup_nil generalize (comp.flatMap neighborsOf).foldl (fun acc q => if cellAt g q.1 q.2 == 1 && !comp.contains q && !acc.contains q then acc ++ [q] else acc) [] = F at hfn hfm ⊢ by_cases he : F.isEmpty = true · rw [if_pos he] have hF0 : F = [] := List.isEmpty_iff.mp he refine ⟨hst, List.Subset.refl _, fun p hp q hadj hq => ?_⟩ by_contra hqn have := (hfm q).mpr (Or.inr ⟨List.mem_flatMap.mpr ⟨p, hp, bf_adj_neighbors p q hadj⟩, hq, hqn⟩) simp [hF0] at this · rw [if_neg he] have hpos : 0 < F.length := by cases F <;> simp_all have hnd' : (comp ++ F).Nodup := by rw [List.nodup_append] refine ⟨hnd, hfn, ?_⟩ intro a ha b hb hab subst hab rcases (hfm a).mp hb with h0 | ⟨_, _, hn⟩ · simp at h0 · exact hn ha have hst' : ∀ p ∈ comp ++ F, IsStable g p.1 p.2 := by intro p hp rcases List.mem_append.mp hp with hp | hp · exact hst p hp · rcases (hfm p).mp hp with h0 | ⟨hx, hq, hqn⟩ · simp at h0 · obtain ⟨p0, hp0, hn⟩ := List.mem_flatMap.mp hx rcases bf_neighbors_adj p0 p hn with rfl | hadj · exact absurd hp0 hqn · obtain ⟨c₀, h0, hr⟩ := hst p0 hp0 exact ⟨c₀, h0, hr.tail ⟨hadj, hq⟩⟩ have hlen' : (allCells g).length ≤ (comp ++ F).length + fuel := by rw [List.length_append]; omega obtain ⟨h1, h2, h3⟩ := ih (comp ++ F) hnd' hst' hlen' exact ⟨h1, fun x hx => h2 (List.mem_append_left _ hx), h3⟩ theorem bf_mem_stableCells (g : List (List Nat)) (p : Nat × Nat) : p ∈ stableCells g ↔ IsStable g p.1 p.2 := by have hdef : stableCells g = stableCellsAux g (((List.range (g.getD 0 []).length).filter fun c => cellAt g 0 c == 1).map fun c => (0, c)) (allCells g).length := rfl have hsn : (((List.range (g.getD 0 []).length).filter fun c => cellAt g 0 c == 1).map fun c => (0, c)).Nodup := (List.nodup_range.filter _).map (fun a b h => by simpa using h) have hss : ∀ q ∈ (((List.range (g.getD 0 []).length).filter fun c => cellAt g 0 c == 1).map fun c => (0, c)), IsStable g q.1 q.2 := by intro q hq simp only [List.mem_map, List.mem_filter, List.mem_range, beq_iff_eq] at hq obtain ⟨c, ⟨_, hc⟩, rfl⟩ := hq exact ⟨c, hc, .refl⟩ obtain ⟨h1, h2, h3⟩ := bf_aux g (allCells g).length _ hsn hss (by omega) rw [hdef] refine ⟨h1 p, fun hp => ?_⟩ obtain ⟨c₀, h0, hr⟩ := hp have hs0 := h2 (show (0, c₀) ∈ (((List.range (g.getD 0 []).length).filter fun c => cellAt g 0 c == 1).map fun c => (0, c)) by simp only [List.mem_map, List.mem_filter, List.mem_range, beq_iff_eq] exact ⟨c₀, ⟨((bf_mem_allCells g (0, c₀)).mp (bf_brick_mem g (0, c₀) h0)).2, h0⟩, rfl⟩) have key : ∀ b, Relation.ReflTransGen (fun p q : Nat × Nat => Adjacent p q ∧ cellAt g q.1 q.2 = 1) (0, c₀) b → b ∈ stableCellsAux g (((List.range (g.getD 0 []).length).filter fun c => cellAt g 0 c == 1).map fun c => (0, c)) (allCells g).length := by intro b hb induction hb with | refl => exact hs0 | tail _ hs ih => exact h3 _ ih _ hs.1 hs.2 exact key _ hr theorem bf_FallsStep_iff (before : List (List Nat)) (hit : Nat × Nat) (fallen : Finset (Nat × Nat)) (after : List (List Nat)) : FallsStep before hit fallen after ↔ ((∀ p : Nat × Nat, p ∈ fallen ↔ cellAt (setCell before hit.1 hit.2 0) p.1 p.2 = 1 ∧ IsStable before p.1 p.2 ∧ ¬ IsStable (setCell before hit.1 hit.2 0) p.1 p.2) ∧ ∀ r c : Nat, cellAt after r c = if (r, c) ∈ fallen then 0 else cellAt (setCell before hit.1 hit.2 0) r c) := Iff.rfl theorem bf_foldl_setCell (L : List (Nat × Nat)) : ∀ (g : List (List Nat)) (r c : Nat), cellAt (L.foldl (fun acc p => setCell acc p.1 p.2 0) g) r c = if (r, c) ∈ L then 0 else cellAt g r c := by induction L with | nil => intro g r c; simp | cons x L ih => intro g r c rw [List.foldl_cons, ih, bf_cellAt_setCell_zero] simp only [List.mem_cons, Prod.ext_iff] grind theorem bf_stepFalls (g : List (List Nat)) (h : List Nat) : (stepFalls g h).1.Nodup ∧ FallsStep g (hitCoord h) (stepFalls g h).1.toFinset (stepFalls g h).2 := by have h1 : (stepFalls g h).1 = (allCells (setCell g (hitCoord h).1 (hitCoord h).2 0)).filter (fun p => cellAt (setCell g (hitCoord h).1 (hitCoord h).2 0) p.1 p.2 == 1 && (stableCells g).contains p && !(stableCells (setCell g (hitCoord h).1 (hitCoord h).2 0)).contains p) := rfl have h2 : (stepFalls g h).2 = (stepFalls g h).1.foldl (fun acc p => setCell acc p.1 p.2 0) (setCell g (hitCoord h).1 (hitCoord h).2 0) := rfl refine ⟨?_, ?_⟩ · rw [h1] exact (bf_allCells_nodup _).filter _ rw [bf_FallsStep_iff] constructor · intro p rw [List.mem_toFinset, h1, List.mem_filter] constructor · rintro ⟨-, hp⟩ simpa [bf_mem_stableCells, and_assoc] using hp · rintro ⟨ha, hb, hc⟩ exact ⟨bf_brick_mem _ _ ha, by simp [bf_mem_stableCells, ha, hb, hc]⟩ · intro r c rw [h2, bf_foldl_setCell] simp only [List.mem_toFinset] theorem bf_step_congr (g g' : List (List Nat)) (hc : ∀ r c, cellAt g r c = cellAt g' r c) (hit : Nat × Nat) (F F' : Finset (Nat × Nat)) (a a' : List (List Nat)) (hs : FallsStep g hit F a) (hs' : FallsStep g' hit F' a') : F = F' ∧ ∀ r c, cellAt a r c = cellAt a' r c := by rw [bf_FallsStep_iff] at hs hs' have hE : ∀ r c, cellAt (setCell g hit.1 hit.2 0) r c = cellAt (setCell g' hit.1 hit.2 0) r c := by intro r c rw [bf_cellAt_setCell_zero, bf_cellAt_setCell_zero, hc] have hF : F = F' := by ext p rw [hs.1 p, hs'.1 p, hE, bf_isStable_congr g g' hc, bf_isStable_congr _ _ hE] refine ⟨hF, fun r c => ?_⟩ rw [hs.2, hs'.2, hF, hE] def bfChain (g : List (List Nat)) (hits : List (List Nat)) (result : List Int) : Prop := ∃ states : List (List (List Nat)), ∃ fallen : List (Finset (Nat × Nat)), states.length = hits.length + 1 ∧ fallen.length = hits.length ∧ states.getD 0 [] = g ∧ ∀ i : Nat, i < hits.length → FallsStep (states.getD i []) (hitCoord (hits.getD i [])) (fallen.getD i ∅) (states.getD (i + 1) []) ∧ result.getD i 0 = ((fallen.getD i ∅).card : Int) theorem bf_checkChain_cons (g : List (List Nat)) (h : List Nat) (hs : List (List Nat)) (r : Int) (rs : List Int) : checkChain g (h :: hs) (r :: rs) = (r == ((stepFalls g h).1.length : Int) && checkChain (stepFalls g h).2 hs rs) := rfl theorem bf_sound : ∀ (hits : List (List Nat)) (g : List (List Nat)) (result : List Int), checkChain g hits result = true → result.length = hits.length ∧ bfChain g hits result := by intro hits induction hits with | nil => intro g result hc cases result with | nil => exact ⟨rfl, [g], [], rfl, rfl, rfl, fun i hi => absurd hi (Nat.not_lt_zero _)⟩ | cons r rs => simp [checkChain] at hc | cons h hs ih => intro g result hc cases result with | nil => simp [checkChain] at hc | cons r rs => rw [bf_checkChain_cons, Bool.and_eq_true, beq_iff_eq] at hc obtain ⟨hr, hrest⟩ := hc obtain ⟨hlen, states, fallen, hsl, hfl, hs0, hall⟩ := ih _ _ hrest obtain ⟨hnd, hstep⟩ := bf_stepFalls g h refine ⟨by simp [hlen], g :: states, (stepFalls g h).1.toFinset :: fallen, by simp [hsl], by simp [hfl], rfl, ?_⟩ intro i hi cases i with | zero => refine ⟨?_, ?_⟩ · simp only [List.getD_cons_zero, List.getD_cons_succ, hs0] exact hstep · simp only [List.getD_cons_zero] rw [hr, List.toFinset_card_of_nodup hnd] | succ i => simp only [List.getD_cons_succ] exact hall i (by simp only [List.length_cons] at hi; omega) theorem bf_complete : ∀ (hits : List (List Nat)) (g g' : List (List Nat)) (result : List Int), (∀ r c, cellAt g r c = cellAt g' r c) → result.length = hits.length → bfChain g' hits result → checkChain g hits result = true := by intro hits induction hits with | nil => intro g g' result _ hl _ cases result with | nil => rfl | cons r rs => simp at hl | cons h hs ih => intro g g' result hc hl hch cases result with | nil => simp at hl | cons r rs => obtain ⟨states, fallen, hsl, hfl, hs0, hall⟩ := hch rcases states with _ | ⟨s0, _ | ⟨s1, srest⟩⟩ · simp at hsl · simp at hsl rcases fallen with _ | ⟨F, frest⟩ · simp at hfl have h0 := hall 0 (by simp) simp only [List.getD_cons_zero, List.getD_cons_succ] at h0 hs0 subst hs0 obtain ⟨hnd, hstep⟩ := bf_stepFalls g h obtain ⟨hF, hcell⟩ := bf_step_congr g s0 hc (hitCoord h) _ _ _ _ hstep h0.1 rw [bf_checkChain_cons, Bool.and_eq_true, beq_iff_eq] refine ⟨by rw [h0.2, ← hF, List.toFinset_card_of_nodup hnd], ?_⟩ refine ih _ s1 rs hcell (by simpa using hl) ⟨s1 :: srest, frest, by simpa using hsl, by simpa using hfl, rfl, fun i hi => ?_⟩ have := hall (i + 1) (by simp only [List.length_cons]; omega) simpa only [List.getD_cons_succ] using this /-- On valid input the checker accepts exactly the specified outputs. -/ theorem bricksFallingWhenHit_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : bricksFallingWhenHit_check input result ↔ bricksFallingWhenHit_spec input result := by have hsp : bricksFallingWhenHit_spec input result ↔ result.length = input.2.length ∧ bfChain input.1 input.2 result := Iff.rfl have hck : bricksFallingWhenHit_check input result = (input.2.length == result.length && checkChain input.1 input.2 result) := rfl rw [hsp, hck, Bool.and_eq_true, beq_iff_eq] constructor · rintro ⟨-, hc⟩ exact bf_sound _ _ _ hc · rintro ⟨hl, hch⟩ exact ⟨hl.symm, bf_complete _ _ _ _ (fun _ _ => rfl) hl hch⟩ /-! ### Implementation helpers -/ /-- Union-find state over cell nodes, with node `0` as the virtual top. -/ structure Dsu where parent : Array Nat rank : Array Nat size : Array Nat /-- Materializes the list grid as nested arrays for constant-time reads and writes. -/ def toGridArray (grid : List (List Nat)) : Array (Array Nat) := grid.toArray.map fun row => row.toArray /-- Reads cell `(r, c)` of an array grid, returning `0` outside the rectangle. -/ def getCellArr (g : Array (Array Nat)) (r c : Nat) : Nat := (g.getD r #[]).getD c 0 /-- Writes cell `(r, c)` of an array grid when the coordinate is in bounds. -/ def setCellArr (g : Array (Array Nat)) (r c v : Nat) : Array (Array Nat) := if r < g.size && c < (g.getD r #[]).size then g.set! r ((g.getD r #[]).set! c v) else g /-- Maps coordinate `(r, c)` to its DSU node, reserving node `0` for the top. -/ def cellIndex (n r c : Nat) : Nat := r * n + c + 1 /-- Follows parent pointers to the root, using the node count as fuel. -/ def findRoot (d : Dsu) (x : Nat) : Nat → Nat | 0 => x | fuel + 1 => let p := d.parent.getD x 0 if p = x then x else findRoot d p fuel /-- Rewrites every node on one parent chain to point directly to `root`. -/ def compressPath (d : Dsu) (x root : Nat) : Nat → Dsu | 0 => d | fuel + 1 => let p := d.parent.getD x 0 if p = x then d else compressPath { d with parent := d.parent.set! x root } p root fuel /-- Finds the representative of `x` and path-compresses its chain. -/ def find (d : Dsu) (x : Nat) : Nat × Dsu := let fuel := d.parent.size let root := findRoot d x fuel (root, compressPath d x root fuel) /-- Unions two DSU nodes by rank while maintaining root component sizes. -/ def union (d : Dsu) (a b : Nat) : Dsu := let (ra, d1) := find d a let (rb, d2) := find d1 b if ra = rb then d2 else let rka := d2.rank.getD ra 0 let rkb := d2.rank.getD rb 0 let sa := d2.size.getD ra 0 let sb := d2.size.getD rb 0 if rka < rkb then { d2 with parent := d2.parent.set! ra rb, size := d2.size.set! rb (sa + sb) } else if rkb < rka then { d2 with parent := d2.parent.set! rb ra, size := d2.size.set! ra (sa + sb) } else { d2 with parent := d2.parent.set! rb ra rank := d2.rank.set! ra (rka + 1) size := d2.size.set! ra (sa + sb) } /-- The current number of bricks in the component containing the virtual top. -/ def topSize (d : Dsu) : Nat := let root := findRoot d 0 d.parent.size d.size.getD root 0 /-- Builds the DSU for the grid remaining after every hit brick has been erased. -/ def initDsuAfterAllHits (g : Array (Array Nat)) : Dsu := let m := g.size let n := (g.getD 0 #[]).size let nodes := m * n + 1 let size0 := (List.range m).foldl (fun sz r => (List.range n).foldl (fun sz2 c => if getCellArr g r c == 1 then sz2.set! (cellIndex n r c) 1 else sz2) sz) (Array.replicate nodes 0) let d0 : Dsu := { parent := (List.range nodes).toArray rank := Array.replicate nodes 0 size := size0 } (List.range m).foldl (fun d r => (List.range n).foldl (fun d c => if getCellArr g r c == 1 then let idx := cellIndex n r c let dA := if r = 0 then union d 0 idx else d let dB := if c + 1 < n && getCellArr g r (c + 1) == 1 then union dA idx (cellIndex n r (c + 1)) else dA if r + 1 < m && getCellArr g (r + 1) c == 1 then union dB idx (cellIndex n (r + 1) c) else dB else d) d) d0 /-- Restores one originally present brick in reverse and counts the bricks it anchors to top. -/ def restoreAndCount (orig cur : Array (Array Nat)) (n : Nat) (d : Dsu) (h : List Nat) : Array (Array Nat) × Dsu × Int := let hit := hitCoord h let r := hit.1 let c := hit.2 if r < cur.size && c < (cur.getD r #[]).size && getCellArr orig r c == 1 then let cur1 := setCellArr cur r c 1 let oldTop := topSize d let idx := cellIndex n r c let d1 := if r = 0 then union d 0 idx else d let d2 := (neighborsOf (r, c)).foldl (fun acc q => if q.1 < cur1.size && q.2 < (cur1.getD q.1 #[]).size && getCellArr cur1 q.1 q.2 == 1 then union acc idx (cellIndex n q.1 q.2) else acc) d1 let newTop := topSize d2 (cur1, d2, ((newTop - oldTop - 1 : Nat) : Int)) else (cur, d, 0) /-! ### Main algorithm (impl) -/ /-- Flat union over component labels: every node stores its component id directly, so merging relabels one component in a single array pass with no pointer chasing. -/ def flatUnion (label csize : Array Nat) (a b : Nat) : Array Nat × Array Nat := let la := label.getD a 0 let lb := label.getD b 0 if la = lb then (label, csize) else let sa := csize.getD la 0 let sb := csize.getD lb 0 let label' := label.map (fun l => if l = lb then la else l) let csize' := (csize.set! la (sa + sb)).set! lb 0 (label', csize') /-- The number of bricks in the component containing the virtual top node `0`. -/ def flatTopSize (label csize : Array Nat) : Nat := csize.getD (label.getD 0 0) 0 /-- Component labels and sizes for the grid remaining after every hit brick is erased. -/ def initFlatDsu (g : Array (Array Nat)) : Array Nat × Array Nat := let m := g.size let n := (g.getD 0 #[]).size let nodes := m * n + 1 let csize0 := (List.range m).foldl (fun sz r => (List.range n).foldl (fun sz2 c => if getCellArr g r c == 1 then sz2.set! (cellIndex n r c) 1 else sz2) sz) (Array.replicate nodes 0) let label0 := (List.range nodes).toArray (List.range m).foldl (fun acc r => (List.range n).foldl (fun st c => if getCellArr g r c == 1 then let idx := cellIndex n r c let stA := if r = 0 then flatUnion st.1 st.2 0 idx else st let stB := if c + 1 < n && getCellArr g r (c + 1) == 1 then flatUnion stA.1 stA.2 idx (cellIndex n r (c + 1)) else stA if r + 1 < m && getCellArr g (r + 1) c == 1 then flatUnion stB.1 stB.2 idx (cellIndex n (r + 1) c) else stB else st) acc) (label0, csize0) /-- Restores one originally present brick in reverse and counts the bricks it anchors to top. -/ def restoreFlatAndCount (orig cur : Array (Array Nat)) (n : Nat) (st : Array Nat × Array Nat) (h : List Nat) : Array (Array Nat) × (Array Nat × Array Nat) × Int := let hit := hitCoord h let r := hit.1 let c := hit.2 if r < cur.size && c < (cur.getD r #[]).size && getCellArr orig r c == 1 then let cur1 := setCellArr cur r c 1 let oldTop := flatTopSize st.1 st.2 let idx := cellIndex n r c let st1 := if r = 0 then flatUnion st.1 st.2 0 idx else st let st2 := (neighborsOf (r, c)).foldl (fun acc q => if q.1 < cur1.size && q.2 < (cur1.getD q.1 #[]).size && getCellArr cur1 q.1 q.2 == 1 then flatUnion acc.1 acc.2 idx (cellIndex n q.1 q.2) else acc) st1 let newTop := flatTopSize st2.1 st2.2 (cur1, st2, ((newTop - oldTop - 1 : Nat) : Int)) else (cur, st, 0) /-- Reverse-time DSU: erase all hits, union surviving bricks, then restore hits backward. -/ def hitBricks (input : Input) : Output := let orig := toGridArray input.1 let erased := input.2.foldl (fun g h => let hit := hitCoord h setCellArr g hit.1 hit.2 0) orig let n := (erased.getD 0 #[]).size let st0raw := initFlatDsu erased let st0 := input.2.foldl (fun st h => let hit := hitCoord h if hit.1 < erased.size && hit.2 < n && getCellArr orig hit.1 hit.2 == 1 then (st.1, st.2.set! (cellIndex n hit.1 hit.2) 1) else st) st0raw let (_, _, out) := input.2.reverse.foldl (fun (cur, st, acc) h => let (cur1, st1, count) := restoreFlatAndCount orig cur n st h (cur1, st1, count :: acc)) (erased, st0, ([] : Output)) out /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem hitBricks_correct (input : Input) (h : isValidInput input) : bricksFallingWhenHit_spec input (hitBricks input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([[1, 0, 0, 0], [1, 1, 1, 0]], [[1, 0]]) #guard isValidInput ([[1, 0, 0, 0], [1, 1, 0, 0]], [[1, 1], [1, 0]]) #guard isValidInput ([[0]], [[0, 0]]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([[1, 0], [1]], [[0, 0]])) #guard !(isValidInput ([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 200]])) #guard !(isValidInput ([[2]], [[0, 0]])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard bricksFallingWhenHit_check ([[1, 0, 0, 0], [1, 1, 1, 0]], [[1, 0]]) [2] #guard bricksFallingWhenHit_check ([[1, 0, 0, 0], [1, 1, 0, 0]], [[1, 1], [1, 0]]) [0, 0] #guard bricksFallingWhenHit_check ([[0]], [[0, 0]]) [0] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(bricksFallingWhenHit_check ([[1, 0, 0, 0], [1, 1, 1, 0]], [[1, 0]]) [1]) #guard !(bricksFallingWhenHit_check ([[1, 0, 0, 0], [1, 1, 0, 0]], [[1, 1], [1, 0]]) [(-1), 0]) #guard !(bricksFallingWhenHit_check ([[0]], [[0, 0]]) [1]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard hitBricks ([[1, 0, 0, 0], [1, 1, 1, 0]], [[1, 0]]) == [2] #guard hitBricks ([[1, 0, 0, 0], [1, 1, 0, 0]], [[1, 1], [1, 0]]) == [0, 0] #guard hitBricks ([[0]], [[0, 0]]) == [0] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard bricksFallingWhenHit_check ([[1, 0, 0, 0], [1, 1, 1, 0]], [[1, 0]]) (hitBricks ([[1, 0, 0, 0], [1, 1, 1, 0]], [[1, 0]])) #guard bricksFallingWhenHit_check ([[1, 0, 0, 0], [1, 1, 0, 0]], [[1, 1], [1, 0]]) (hitBricks ([[1, 0, 0, 0], [1, 1, 0, 0]], [[1, 1], [1, 0]])) #guard bricksFallingWhenHit_check ([[0]], [[0, 0]]) (hitBricks ([[0]], [[0, 0]])) end PBricksFallingWhenHit