import Mathlib /-! # Set Matrix Zeroes Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. You must do it in place. ## Constraints - m == matrix.length - n == matrix[0].length - 1 <= m, n <= 200 - -2^31 <= matrix[i][j] <= 2^31 - 1 ## Provided examples - `matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]` → `[[1, 0, 1], [0, 0, 0], [1, 0, 1]]` - `matrix = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]` → `[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]` - `matrix = [[1]]` → `[[1]]` ## Synthesized negative examples - invalid input: `matrix = []` ([structural] a predicate that admits 1 <= m, n <= 200. empty matrix where at least one row is required) - invalid input: `matrix = [[-2147483649]]` ([structural] a predicate that admits -2^31 <= matrix[i][j] <= 2^31 - 1. one below the stated minimum value) - invalid input: `matrix = [[]]` ([structural] a predicate that admits 1 <= m, n <= 200. row with no columns where at least one column is required) - `matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]` → `[[1, 1, 1], [0, 0, 0], [1, 1, 1]]` is wrong ([structural] column zeroing is not required. only row zeroing is performed; column cells stay 1) - `matrix = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]` → `[[0, 0, 0, 0, 0], [0, 4, 5, 0, 0], [0, 3, 1, 0, 0]]` is wrong ([structural] output is not required to have exactly n columns. all true values match; only width is n+1) - `matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]` → `[[0, 0, 0], [1, 0, 1], [1, 0, 1]]` is wrong ([structural] the result differs from the required one in at least one position. amended 2026-08-18: second mutation of a screened positive to reach quota) -/ namespace PSetMatrixZeroes abbrev Input := List (List Int) abbrev Output := List (List Int) /-! ### Specification helpers -/ /-- Returns the entry at a row and column, if both positions exist. -/ def cellAt (matrix : List (List Int)) (i j : Nat) : Option Int := (matrix[i]?).bind (fun row => row[j]?) /-- Row `i` or column `j` of `matrix` contains a zero. -/ def RowOrColumnHasZero (matrix : List (List Int)) (i j : Nat) : Prop := (∃ row : List Int, matrix[i]? = some row ∧ 0 ∈ row) ∨ (∃ row : List Int, row ∈ matrix ∧ row[j]? = some 0) /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty rectangular matrix within the stated dimension and element bounds. -/ def isValidInput (input : Input) : Bool := match input with | [] => false | firstRow :: _ => 1 ≤ input.length && input.length ≤ 200 && 1 ≤ firstRow.length && firstRow.length ≤ 200 && input.all (fun row => row.length == firstRow.length) && input.all (fun row => row.all (fun value => (-2147483648 : Int) ≤ value && value ≤ (2147483647 : Int))) /-! ### Ideal specification (P_spec) -/ /-- `result` has the dimensions of `matrix` and zeroes exactly the rows and columns containing zeroes. -/ def setZeroes_spec (matrix : Input) (result : Output) : Prop := result.length = matrix.length ∧ (∀ (i : Nat) (hi : i < matrix.length), (result[i]?).map (fun row => row.length) = some (matrix.get ⟨i, hi⟩).length) ∧ ∀ (i : Nat) (hi : i < matrix.length) (j : Nat) (hj : j < (matrix.get ⟨i, hi⟩).length), (cellAt result i j = some 0 ↔ RowOrColumnHasZero matrix i j) ∧ (¬ RowOrColumnHasZero matrix i j → cellAt result i j = cellAt matrix i j) /-! ### Decidable specification (P_check) -/ /-- Decidable realization of `RowOrColumnHasZero`: row `i` or column `j` of `matrix` contains a zero. -/ def rowOrColumnHasZero (matrix : List (List Int)) (i j : Nat) : Bool := ((matrix[i]?).map fun row => row.contains (0 : Int)).getD false || matrix.any fun row => row[j]? == some (0 : Int) /-- Executable checker for `setZeroes_spec` with the index quantifiers truncated to the matrix dimensions. -/ def setZeroes_check (matrix : Input) (result : Output) : Bool := decide (result.length = matrix.length ∧ (∀ i : Fin matrix.length, (result[i.val]?).map (fun row => row.length) = some (matrix.get i).length) ∧ ∀ (i : Fin matrix.length) (j : Fin (matrix.get i).length), (cellAt result i.val j.val = some 0 ↔ rowOrColumnHasZero matrix i.val j.val = true) ∧ (rowOrColumnHasZero matrix i.val j.val = false → cellAt result i.val j.val = cellAt matrix i.val j.val)) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem setZeroes_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : setZeroes_check input result ↔ setZeroes_spec input result := by simp +contextual [setZeroes_check, setZeroes_spec, rowOrColumnHasZero, RowOrColumnHasZero, Fin.forall_iff, List.getElem?_eq_getElem] /-! ### Implementation helpers -/ /-- One flag per row, true iff that row contains a zero. -/ def computeZeroRows (matrix : List (List Int)) : List Bool := matrix.map fun row => row.contains (0 : Int) /-- One flag per column, true iff some row has a zero in that column. -/ def computeZeroCols (matrix : List (List Int)) : List Bool := match matrix with | [] => [] | firstRow :: rest => rest.foldl (fun flags row => flags.zipWith (fun flag value => flag || value == (0 : Int)) row) (firstRow.map fun value => value == (0 : Int)) /-- Rebuilds the matrix, zeroing each cell whose row or column flag is set. -/ def zeroMatrix (matrix : List (List Int)) (rowFlags colFlags : List Bool) : List (List Int) := (matrix.zip rowFlags).map fun (row, rowFlag) => (row.zip colFlags).map fun (value, colFlag) => if rowFlag || colFlag then (0 : Int) else value /-! ### Main algorithm (impl) -/ /-- Sets every row and column containing a zero to zero in two passes: precompute row and column zero flags, then rebuild the matrix from them. -/ def setMatrixZeroes (input : Input) : Output := let rowFlags := computeZeroRows input let colFlags := computeZeroCols input zeroMatrix input rowFlags colFlags /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem setMatrixZeroes_correct (input : Input) (h : isValidInput input) : setZeroes_spec input (setMatrixZeroes input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [[1, 1, 1], [1, 0, 1], [1, 1, 1]] #guard isValidInput [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]] #guard isValidInput [[1]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [[-2147483649]]) #guard !(isValidInput [[]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard setZeroes_check [[1, 1, 1], [1, 0, 1], [1, 1, 1]] [[1, 0, 1], [0, 0, 0], [1, 0, 1]] #guard setZeroes_check [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]] [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]] #guard setZeroes_check [[1]] [[1]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(setZeroes_check [[1, 1, 1], [1, 0, 1], [1, 1, 1]] [[1, 1, 1], [0, 0, 0], [1, 1, 1]]) #guard !(setZeroes_check [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]] [[0, 0, 0, 0, 0], [0, 4, 5, 0, 0], [0, 3, 1, 0, 0]]) #guard !(setZeroes_check [[1, 1, 1], [1, 0, 1], [1, 1, 1]] [[0, 0, 0], [1, 0, 1], [1, 0, 1]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard setMatrixZeroes [[1, 1, 1], [1, 0, 1], [1, 1, 1]] == [[1, 0, 1], [0, 0, 0], [1, 0, 1]] #guard setMatrixZeroes [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]] == [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]] #guard setMatrixZeroes [[1]] == [[1]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard setZeroes_check [[1, 1, 1], [1, 0, 1], [1, 1, 1]] (setMatrixZeroes [[1, 1, 1], [1, 0, 1], [1, 1, 1]]) #guard setZeroes_check [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]] (setMatrixZeroes [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]) #guard setZeroes_check [[1]] (setMatrixZeroes [[1]]) end PSetMatrixZeroes