import Mathlib /-! # Number Of Submatrices That Sum To Target Given a matrix and a target, return the number of non-empty submatrices that sum to target. A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2. Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'. ## Constraints - 1 <= matrix.length <= 100 - 1 <= matrix[0].length <= 100 - -1000 <= matrix[i][j] <= 1000 - -10^8 <= target <= 10^8 ## Provided examples - `matrix = [[0, 1, 0], [1, 1, 1], [0, 1, 0]], target = 0` → `4` - `matrix = [[1, -1], [-1, 1]], target = 0` → `5` - `matrix = [[904]], target = 0` → `0` ## Synthesized negative examples - invalid input: `matrix = [], target = 0` ([structural] a predicate that admits 1 <= matrix.length <= 100. predicate checking only values accepts empty matrix) - invalid input: `matrix = [[-1001]], target = 0` ([structural] a predicate that admits -1000 <= matrix[i][j] <= 1000. predicate checking only dimensions accepts value below minimum) - invalid input: `matrix = [[]], target = 0` ([structural] a predicate that admits 1 <= matrix[0].length <= 100. predicate checking only row count accepts empty row) - `matrix = [[0, 1, 0], [1, 1, 1], [0, 1, 0]], target = 0` → `3` is wrong ([structural] off-by-one in the count; one boundary submatrix is excluded. three of the four zero-sum submatrices are counted) - `matrix = [[1, -1], [-1, 1]], target = 0` → `0` is wrong ([structural] nothing requires all valid submatrices to be counted. counts none, accepted if completeness omitted) - `matrix = [[904]], target = 0` → `1` is wrong ([structural] no requirement that submatrix sum equals target. counts the sole non-empty submatrix regardless of sum) -/ namespace PNumberOfSubmatricesThatSumToTarget abbrev Input := (List (List Int)) × (Int) abbrev Output := Nat /-! ### Specification helpers -/ /-- Coordinates (x1, y1, x2, y2) form a non-empty, in-bounds submatrix whose entries sum to target. -/ def IsGoodSubmatrix (matrix : List (List Int)) (target : Int) (x1 y1 x2 y2 : Nat) : Prop := x1 ≤ x2 ∧ y1 ≤ y2 ∧ x2 < matrix.length ∧ y2 < matrix[0]!.length ∧ (∑ i ∈ Finset.Icc x1 x2, ∑ j ∈ Finset.Icc y1 y2, (matrix[i]!)[j]!) = target /-! ### Validity predicate (V) -/ /-- Valid input: a 1–100 row matrix of equal-width rows of width 1–100, cells in [-1000, 1000], target in [-10^8, 10^8]. -/ def isValidInput (input : Input) : Bool := let m := input.1 1 ≤ m.length && m.length ≤ 100 && (match m.head? with | none => false | some row => 1 ≤ row.length && row.length ≤ 100 && m.all (fun r => r.length == row.length && r.all (fun c => -1000 ≤ c && c ≤ 1000))) && (-(10^8 : Int) ≤ input.2 && input.2 ≤ (10^8 : Int)) /-! ### Ideal specification (P_spec) -/ /-- `result` is the cardinality of a finite set of quadruples holding exactly the good submatrices of the input. -/ def numSubmatrixSumTarget_spec (input : Input) (result : Output) : Prop := ∃ S : Finset (Nat × Nat × Nat × Nat), S.card = result ∧ ∀ q : Nat × Nat × Nat × Nat, q ∈ S ↔ IsGoodSubmatrix input.1 input.2 q.1 q.2.1 q.2.2.1 q.2.2.2 /-! ### Decidable specification (P_check) -/ /-- Instance: for fixed coordinates, `IsGoodSubmatrix` unfolds to decidable Nat bounds together with an equality between an `Int` finite sum and the target. -/ instance decIsGoodSubmatrix (matrix : List (List Int)) (target : Int) (x1 y1 x2 y2 : Nat) : Decidable (IsGoodSubmatrix matrix target x1 y1 x2 y2) := inferInstanceAs (Decidable (x1 ≤ x2 ∧ y1 ≤ y2 ∧ x2 < matrix.length ∧ y2 < matrix[0]!.length ∧ (∑ i ∈ Finset.Icc x1 x2, ∑ j ∈ Finset.Icc y1 y2, (matrix[i]!)[j]!) = target)) /-- Instance: any finset containing exactly the good submatrices must be the filter of the bounded coordinate box. Hence the existential specification is equivalent to the decidable assertion that `result` is that filter's cardinality. -/ instance decNumSubmatrixSumTarget (input : Input) (result : Output) : Decidable (∃ S : Finset (Nat × Nat × Nat × Nat), S.card = result ∧ ∀ q : Nat × Nat × Nat × Nat, q ∈ S ↔ IsGoodSubmatrix input.1 input.2 q.1 q.2.1 q.2.2.1 q.2.2.2) := decidable_of_iff (result = ((Finset.range input.1.length ×ˢ (Finset.range input.1[0]!.length ×ˢ (Finset.range input.1.length ×ˢ Finset.range input.1[0]!.length))).filter (fun q => IsGoodSubmatrix input.1 input.2 q.1 q.2.1 q.2.2.1 q.2.2.2)).card) (by constructor · intro h refine ⟨_, h.symm, ?_⟩ intro q simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_range] constructor · intro hb exact hb.2 · intro hgood obtain ⟨h1, h2, h3, h4, hsum⟩ := hgood exact ⟨⟨by omega, by omega, by omega, by omega⟩, ⟨h1, h2, h3, h4, hsum⟩⟩ · rintro ⟨S, hcard, hiff⟩ have hSF : S = (Finset.range input.1.length ×ˢ (Finset.range input.1[0]!.length ×ˢ (Finset.range input.1.length ×ˢ Finset.range input.1[0]!.length))).filter (fun q => IsGoodSubmatrix input.1 input.2 q.1 q.2.1 q.2.2.1 q.2.2.2) := by ext q simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_range] constructor · intro hq have hgood := (hiff q).mp hq obtain ⟨h1, h2, h3, h4, hsum⟩ := hgood exact ⟨⟨by omega, by omega, by omega, by omega⟩, ⟨h1, h2, h3, h4, hsum⟩⟩ · intro hb exact (hiff q).mpr hb.2 rw [← hcard, hSF]) /-- Executable checker obtained mechanically from the specification. -/ def numSubmatrixSumTarget_check (input : Input) (result : Output) : Bool := @decide (numSubmatrixSumTarget_spec input result) (by unfold numSubmatrixSumTarget_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem numSubmatrixSumTarget_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : numSubmatrixSumTarget_check input result ↔ numSubmatrixSumTarget_spec input result := by simp [numSubmatrixSumTarget_check] /-! ### Implementation helpers -/ /-- Value stored for key `k` in an association-list map, or zero when absent. -/ def mapGet (m : List (Int × Nat)) (k : Int) : Nat := match m with | [] => 0 | (k', v) :: rest => if k' == k then v else mapGet rest k /-- Add one to the count stored for key `k`, creating the entry when absent. -/ def mapBump (m : List (Int × Nat)) (k : Int) : List (Int × Nat) := match m with | [] => [(k, 1)] | (k', v) :: rest => if k' == k then (k', v + 1) :: rest else (k', v) :: mapBump rest k /-- Fold over column sums, counting subarrays ending at each position whose sum is `target`. -/ def countSubarraysGo (cols : List Int) (runSum : Int) (m : List (Int × Nat)) (target : Int) (acc : Nat) : Nat := match cols with | [] => acc | c :: cs => let runSum' := runSum + c countSubarraysGo cs runSum' (mapBump m runSum') target (acc + mapGet m (runSum' - target)) /-- Number of contiguous non-empty subarrays of `cols` whose entries sum to `target`. -/ def countSubarraysWithSum (cols : List Int) (target : Int) : Nat := countSubarraysGo cols 0 [(0, 1)] target 0 /-- Elementwise sum of a running band and the next row, truncated to the shorter. -/ def rowBandColumnSums (band row : List Int) : List Int := match band, row with | [], _ => [] | _, [] => [] | b :: bs, r :: rs => (b + r) :: rowBandColumnSums bs rs /-- Extend the band downward through `rows`, counting target-sum submatrices at each bottom row. -/ def countBandsFrom (band : List Int) (rows : List (List Int)) (target : Int) (acc : Nat) : Nat := let acc := acc + countSubarraysWithSum band target match rows with | [] => acc | r :: rs => countBandsFrom (rowBandColumnSums band r) rs target acc /-- Try each remaining row as the top of a band and accumulate the counts. -/ def countFromTop (rows : List (List Int)) (target : Int) (acc : Nat) : Nat := match rows with | [] => acc | r :: rs => countFromTop rs target (countBandsFrom r rs target acc) /-! ### Main algorithm (impl) -/ /-- Count submatrices summing to `target` by fixing each top row, growing the band downward, and prefix-counting column subarrays per band. -/ def countSubmatricesWithTarget (input : Input) : Output := countFromTop input.1 input.2 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem countSubmatricesWithTarget_correct (input : Input) (h : isValidInput input) : numSubmatrixSumTarget_spec input (countSubmatricesWithTarget input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([[0, 1, 0], [1, 1, 1], [0, 1, 0]], 0) #guard isValidInput ([[1, -1], [-1, 1]], 0) #guard isValidInput ([[904]], 0) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], 0)) #guard !(isValidInput ([[-1001]], 0)) #guard !(isValidInput ([[]], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard numSubmatrixSumTarget_check ([[0, 1, 0], [1, 1, 1], [0, 1, 0]], 0) 4 #guard numSubmatrixSumTarget_check ([[1, (-1)], [(-1), 1]], 0) 5 #guard numSubmatrixSumTarget_check ([[904]], 0) 0 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(numSubmatrixSumTarget_check ([[0, 1, 0], [1, 1, 1], [0, 1, 0]], 0) 3) #guard !(numSubmatrixSumTarget_check ([[1, (-1)], [(-1), 1]], 0) 0) #guard !(numSubmatrixSumTarget_check ([[904]], 0) 1) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard countSubmatricesWithTarget ([[0, 1, 0], [1, 1, 1], [0, 1, 0]], 0) == 4 #guard countSubmatricesWithTarget ([[1, (-1)], [(-1), 1]], 0) == 5 #guard countSubmatricesWithTarget ([[904]], 0) == 0 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard numSubmatrixSumTarget_check ([[0, 1, 0], [1, 1, 1], [0, 1, 0]], 0) (countSubmatricesWithTarget ([[0, 1, 0], [1, 1, 1], [0, 1, 0]], 0)) #guard numSubmatrixSumTarget_check ([[1, (-1)], [(-1), 1]], 0) (countSubmatricesWithTarget ([[1, (-1)], [(-1), 1]], 0)) #guard numSubmatrixSumTarget_check ([[904]], 0) (countSubmatricesWithTarget ([[904]], 0)) end PNumberOfSubmatricesThatSumToTarget