import Mathlib /-! # Maximal Rectangle Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area. ## Constraints - rows == matrix.length - cols == matrix[i].length - 1 <= row, cols <= 200 - matrix[i][j] is '0' or '1'. ## Provided examples - `matrix = [["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]]` → `6` - `matrix = [["0"]]` → `0` - `matrix = [["1"]]` → `1` ## Synthesized negative examples - invalid input: `matrix = []` ([structural] a predicate that admits 1 <= row, cols <= 200. empty matrix gives zero rows) - invalid input: `matrix = [["0", "1"], ["0"]]` ([structural] a predicate that admits cols == matrix[i].length. ragged rows; first-row-length check misses shorter row) - invalid input: `matrix = [["2"]]` ([structural] a predicate that admits matrix[i][j] is '0' or '1'.. digit outside binary alphabet) - `matrix = [["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]]` → `20` is wrong ([structural] drops the containing-only-1s condition; returns largest rectangle area in the whole grid. 4x5 rectangle area 20; not all cells are 1) - `matrix = [["0"]]` → `1` is wrong ([structural] maximality is stated without soundness: the answer need not be an area of any actual rectangle. no all-1 rectangle exists, so 1 exceeds every attainable area) - `matrix = [["1"]]` → `2` is wrong ([structural] largest area stated as an upper bound without requiring a rectangle to attain it. no rectangle has area 2; accepted by spec without soundness) -/ namespace PMaximalRectangle abbrev Input := List (List String) abbrev Output := Nat /-! ### Specification helpers -/ /-- The rectangle with top row `r`, left column `c`, height `h`, and width `w` lies inside `matrix` and every cell it covers is the string "1". -/ def IsAllOnesRectangle (matrix : List (List String)) (r c h w : Nat) : Prop := r + h ≤ matrix.length ∧ ∀ i, r ≤ i → i < r + h → ∀ j, c ≤ j → j < c + w → (matrix[i]?).bind (·[j]?) = some "1" /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 200 rows, all rows of equal length between 1 and 200, every cell the string "0" or the string "1". -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 200 && input.all (fun row => 1 ≤ row.length && row.length ≤ 200 && row.all (fun cell => cell == "0" || cell == "1")) && (match input.head? with | none => true | some row0 => input.all (fun row => row.length == row0.length)) /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest area attained by an all-"1" rectangle of `input`: some such rectangle has area `result` and none has a larger one. -/ def maximalRectangleArea_spec (input : Input) (result : Output) : Prop := IsGreatest {a | ∃ r c h w : Nat, IsAllOnesRectangle input r c h w ∧ a = h * w} result /-! ### Decidable specification (P_check) -/ /-- The cell of `matrix` at row `i`, column `j` is the string "1". -/ def cellIsOne (matrix : Input) (i j : Nat) : Bool := (matrix[i]?).bind (·[j]?) == some "1" /-- Boolean form of `IsAllOnesRectangle`: the height-`h`, width-`w` block at (`r`, `c`) lies in `matrix` and covers only "1" cells. -/ def allOnesRect (matrix : Input) (r c h w : Nat) : Bool := r + h ≤ matrix.length && (List.range h).all (fun di => (List.range w).all (fun dj => cellIsOne matrix (r + di) (c + dj))) /-- Every rectangle parameter tuple with `r, h ≤ rows` and `c, w ≤ cols`. -/ def rectParams (rows cols : Nat) : List (Nat × Nat × Nat × Nat) := (List.range (rows + 1)).flatMap (fun r => (List.range (cols + 1)).flatMap (fun c => (List.range (rows + 1)).flatMap (fun h => (List.range (cols + 1)).map (fun w => (r, c, h, w))))) /-- Executable checker for `maximalRectangleArea_spec` over the bounded rectangle parameters. -/ def maximalRectangleArea_check (input : Input) (result : Output) : Bool := let rows := input.length let cols := (input.head?.map (·.length)).getD 0 (rectParams rows cols).any (fun (r, c, h, w) => allOnesRect input r c h w && h * w == result) && (rectParams rows cols).all (fun (r, c, h, w) => !(allOnesRect input r c h w) || h * w ≤ result) theorem allOnesRect_eq_true_iff (matrix : Input) (r c h w : Nat) : allOnesRect matrix r c h w = true ↔ IsAllOnesRectangle matrix r c h w := by simp only [allOnesRect, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, List.mem_range, cellIsOne, beq_iff_eq] constructor · rintro ⟨hr, hall⟩ refine ⟨hr, ?_⟩ intro i hir hi j hjc hj have hi' : i - r < h := by omega have hj' : j - c < w := by omega simpa [Nat.add_sub_of_le hir, Nat.add_sub_of_le hjc] using hall (i - r) hi' (j - c) hj' · rintro ⟨hr, hall⟩ refine ⟨hr, ?_⟩ intro di hdi dj hdj exact hall (r + di) (by omega) (by omega) (c + dj) (by omega) (by omega) theorem mem_rectParams_iff (rows cols r c h w : Nat) : (r, c, h, w) ∈ rectParams rows cols ↔ r ≤ rows ∧ c ≤ cols ∧ h ≤ rows ∧ w ≤ cols := by simp [rectParams] lemma valid_row_length_eq_cols (input : Input) (hv : isValidInput input) {i : Nat} {row : List String} (hir : input[i]? = some row) : row.length = (input.head?.map (·.length)).getD 0 := by cases input with | nil => simp at hir | cons first rest => have hm : row ∈ first :: rest := List.mem_of_getElem? hir simp [isValidInput, List.all_eq_true] at hv simp only [List.head?_cons, Option.map_some, Option.getD_some] grind lemma allOnesRectangle_bounded_rep (input : Input) (hv : isValidInput input) {r c h w : Nat} (hr : IsAllOnesRectangle input r c h w) : ∃ r' c' h' w', r' ≤ input.length ∧ c' ≤ (input.head?.map (·.length)).getD 0 ∧ h' ≤ input.length ∧ w' ≤ (input.head?.map (·.length)).getD 0 ∧ IsAllOnesRectangle input r' c' h' w' ∧ h' * w' = h * w := by by_cases hh : h = 0 · subst h exact ⟨0, 0, 0, 0, by simp [IsAllOnesRectangle]⟩ by_cases hw : w = 0 · subst w exact ⟨0, 0, 0, 0, by simp [IsAllOnesRectangle]⟩ have hinside : r + h ≤ input.length := hr.1 have hcell := hr.2 r (by omega) (by omega) (c + w - 1) (by omega) (by omega) rcases Option.bind_eq_some_iff.mp hcell with ⟨row, hrow, hcol⟩ have hlast : c + w - 1 < row.length := (List.getElem?_eq_some_iff.mp hcol).choose have hrowlen := valid_row_length_eq_cols input hv hrow exact ⟨r, c, h, w, by omega, by omega, by omega, by omega, hr, rfl⟩ theorem wx_root (input : Input) (result : Output) (hf : ∀ r c h w, allOnesRect input r c h w = true ↔ IsAllOnesRectangle input r c h w) (hb : ∀ r c h w, IsAllOnesRectangle input r c h w → ∃ r' c' h' w', (r', c', h', w') ∈ rectParams input.length ((input.head?.map (·.length)).getD 0) ∧ IsAllOnesRectangle input r' c' h' w' ∧ h' * w' = h * w) : maximalRectangleArea_check input result ↔ maximalRectangleArea_spec input result := by simp only [maximalRectangleArea_check, Bool.and_eq_true, List.any_eq_true, List.all_eq_true, Prod.exists, Prod.forall, beq_iff_eq, Bool.or_eq_true, Bool.not_eq_true_eq_eq_false, decide_eq_true_eq, Bool.eq_false_iff, hf, maximalRectangleArea_spec, IsGreatest, upperBounds, Set.mem_setOf_eq] constructor · rintro ⟨⟨r, c, ht, w, hm, hr, he⟩, hu⟩ refine ⟨⟨r, c, ht, w, hr, he.symm⟩, ?_⟩ rintro a ⟨r, c, ht, w, hr, rfl⟩ obtain ⟨r', c', ht', w', hm', hr', he'⟩ := hb r c ht w hr have hh := hu r' c' ht' w' hm' grind only [] · rintro ⟨⟨r, c, ht, w, hr, he⟩, hu⟩ obtain ⟨r', c', ht', w', hm', hr', he'⟩ := hb r c ht w hr constructor · exact ⟨r', c', ht', w', hm', hr', he'.trans he.symm⟩ · intro r c ht w hm by_cases hr : IsAllOnesRectangle input r c ht w · exact Or.inr (hu ⟨r, c, ht, w, hr, rfl⟩) · exact Or.inl (fun he => hr ((hf r c ht w).mp he)) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem maximalRectangleArea_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : maximalRectangleArea_check input result ↔ maximalRectangleArea_spec input result := by apply wx_root input result (allOnesRect_eq_true_iff input) intro r c ht w hr obtain ⟨r', c', ht', w', hrr, hcc, hhh, hww, hr', he⟩ := allOnesRectangle_bounded_rep input h hr exact ⟨r', c', ht', w', (mem_rectParams_iff _ _ _ _ _ _).mpr ⟨hrr, hcc, hhh, hww⟩, hr', he⟩ /-! ### Implementation helpers -/ /-- Largest rectangle area inside a column-height histogram, via a monotone stack of (start index, height) pairs flushed by a trailing sentinel 0. -/ def largestRectangleInHistogram (heights : List Nat) : Nat := let rec pop (stack : List (Nat × Nat)) (best i h start : Nat) : Nat × List (Nat × Nat) × Nat := match stack with | [] => (best, [], start) | (j, hj) :: rest => if hj > h then pop rest (Nat.max best (hj * (i - j))) i h j else (best, stack, start) let rec go (stack : List (Nat × Nat)) (best i : Nat) (hs : List Nat) : Nat := match hs with | [] => best | h :: rest => let (best', stack', start) := pop stack best i h i go ((start, h) :: stack') best' (i + 1) rest go [] 0 0 (heights ++ [0]) /-! ### Main algorithm (impl) -/ /-- Maximal all-"1" rectangle area by scanning rows while maintaining consecutive-"1" column heights and taking each row's largest histogram rectangle. -/ def largestRectangleArea (input : Input) : Output := let cols := (input.head?.map (·.length)).getD 0 let rec go (rows : Input) (rowIdx : Nat) (heights : List Nat) (best : Nat) : Nat := match rows with | [] => best | _row :: rest => let heights' := (List.range cols).map (fun j => if cellIsOne input rowIdx j then (heights[j]?).getD 0 + 1 else 0) go rest (rowIdx + 1) heights' (Nat.max best (largestRectangleInHistogram heights')) go input 0 (List.replicate cols 0) 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem largestRectangleArea_correct (input : Input) (h : isValidInput input) : maximalRectangleArea_spec input (largestRectangleArea input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]] #guard isValidInput [["0"]] #guard isValidInput [["1"]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [["0", "1"], ["0"]]) #guard !(isValidInput [["2"]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard maximalRectangleArea_check [["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]] 6 #guard maximalRectangleArea_check [["0"]] 0 #guard maximalRectangleArea_check [["1"]] 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(maximalRectangleArea_check [["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]] 20) #guard !(maximalRectangleArea_check [["0"]] 1) #guard !(maximalRectangleArea_check [["1"]] 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard largestRectangleArea [["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]] == 6 #guard largestRectangleArea [["0"]] == 0 #guard largestRectangleArea [["1"]] == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard maximalRectangleArea_check [["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]] (largestRectangleArea [["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]]) #guard maximalRectangleArea_check [["0"]] (largestRectangleArea [["0"]]) #guard maximalRectangleArea_check [["1"]] (largestRectangleArea [["1"]]) end PMaximalRectangle