import Mathlib /-! # Spiral Matrix Given an m x n matrix, return all elements of the matrix in spiral order. ## Constraints - m == matrix.length - n == matrix[i].length - 1 <= m, n <= 10 - -100 <= matrix[i][j] <= 100 ## Provided examples - `matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]` → `[1, 2, 3, 6, 9, 8, 7, 4, 5]` - `matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]` → `[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]` - `matrix = [[1]]` → `[1]` ## Synthesized negative examples - invalid input: `matrix = []` ([structural] a predicate that admits 1 <= m, n <= 10. zero rows; violates the minimum m) - invalid input: `matrix = [[1, 2], [3]]` ([structural] a predicate that admits n == matrix[i].length. ragged rows; no single n fits all rows) - invalid input: `matrix = [[-101]]` ([structural] a predicate that admits -100 <= matrix[i][j] <= 100. element one below the allowed minimum) - `matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]` → `[1, 2, 3, 4, 5, 6, 7, 8, 9]` is wrong ([structural] a specification that drops the spiral-order constraint accepts any ordering. row-major has all elements but not in spiral order) - `matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]` → `[1, 5, 9, 10, 11, 12, 8, 4, 3, 2, 6, 7]` is wrong ([structural] drops clockwise orientation constraint. same spiral, counter-clockwise) - `matrix = [[1]]` → `[]` is wrong ([structural] completeness clause missing; nothing requires every matrix element to appear. empty list omits the only matrix element) -/ namespace PSpiralMatrix abbrev Input := List (List Int) abbrev Output := List Int /-! ### Specification helpers -/ /-- The cells of an `m × n` grid as `(row, column)` pairs in clockwise spiral order, peeling one boundary ring at a time and recursing inward. -/ def spiralCoords : Nat → Nat → List (Nat × Nat) | 0, _ => [] | _, 0 => [] | m + 1, n + 1 => let top := (List.range (n + 1)).map fun j => (0, j) let right := (List.range m).map fun i => (i + 1, n) let bottom := if m = 0 then [] else (List.range n).map fun j => (m, n - 1 - j) let left := if n = 0 then [] else (List.range (m - 1)).map fun i => (m - 1 - i, 0) let inner := (spiralCoords (m - 1) (n - 1)).map fun p => (p.1 + 1, p.2 + 1) top ++ right ++ bottom ++ left ++ inner termination_by m n => m + n decreasing_by simp_wf; omega /-- `v` is the value of the cell visited at step `i` of the clockwise spiral walk over `matrix`. -/ def SpiralEntry (matrix : List (List Int)) (i : Nat) (v : Int) : Prop := ∃ r c, (spiralCoords matrix.length (matrix.headD []).length)[i]? = some (r, c) ∧ ∃ row, matrix[r]? = some row ∧ row[c]? = some v /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 10 rows, all rows of one common length of 1 to 10 columns, and every entry between -100 and 100 inclusive. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10 && input.all (fun row => row.length == (input.headD []).length) && input.all (fun row => 1 ≤ row.length && row.length ≤ 10) && input.all (fun row => row.all (fun x => -100 ≤ x && x ≤ 100)) /-! ### Ideal specification (P_spec) -/ /-- `result` has exactly one entry per cell of `input`, and for every index `i` of `result`, `result[i]` is the value of the cell visited at step `i` of the clockwise spiral walk over `input`. -/ def spiralOrder_spec (input : Input) (result : Output) : Prop := result.length = input.length * (input.headD []).length ∧ ∀ i (h : i < result.length), SpiralEntry input i result[i] /-! ### Decidable specification (P_check) -/ /-- Decidable realization of `SpiralEntry`: the coordinate at step `i` of the spiral walk determines `r` and `c`, and the row lookup determines `row`. -/ def spiralEntryCheck (matrix : List (List Int)) (i : Nat) (v : Int) : Bool := match (spiralCoords matrix.length (matrix.headD []).length)[i]? with | none => false | some (r, c) => match matrix[r]? with | none => false | some row => decide (row[c]? = some v) /-- Executable checker for `spiralOrder_spec` over the indices of `result`. -/ def spiralOrder_check (input : Input) (result : Output) : Bool := result.length == input.length * (input.headD []).length && (List.finRange result.length).all fun i => spiralEntryCheck input i.val (result.get i) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem spiralOrder_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : spiralOrder_check input result ↔ spiralOrder_spec input result := by have entry_iff (matrix : Input) (i : Nat) (v : Int) : spiralEntryCheck matrix i v = true ↔ SpiralEntry matrix i v := by cases hc : (spiralCoords matrix.length (matrix.headD []).length)[i]? with | none => simp only [spiralEntryCheck, SpiralEntry, hc]; simp | some p => rcases p with ⟨r, c⟩ cases hr : matrix[r]? with | none => simp only [spiralEntryCheck, SpiralEntry, hc]; simp [hr] | some row => simp only [spiralEntryCheck, SpiralEntry, hc]; simp [hr] simp only [spiralOrder_check, spiralOrder_spec, Bool.and_eq_true, beq_iff_eq, List.all_eq_true, List.mem_finRange, forall_true_left, entry_iff] constructor · rintro ⟨hlen, hall⟩ refine ⟨hlen, ?_⟩ intro i hi exact hall ⟨i, hi⟩ · rintro ⟨hlen, hall⟩ refine ⟨hlen, ?_⟩ intro i exact hall i.val i.isLt /-! ### Implementation helpers -/ /-- The matrix entry at row `r` and column `c`, defaulting to `0` when either index is out of range. -/ def getCell (matrix : List (List Int)) (r c : Nat) : Int := match matrix[r]? with | none => 0 | some row => (row[c]?).getD 0 /-! ### Main algorithm (impl) -/ /-- Clockwise spiral traversal by mapping the specification's spiral coordinate list to the corresponding matrix entries. -/ def matrixSpiralOrder (input : Input) : Output := (spiralCoords input.length (input.headD []).length).map fun p => getCell input p.1 p.2 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem matrixSpiralOrder_correct (input : Input) (h : isValidInput input) : spiralOrder_spec input (matrixSpiralOrder input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [[1, 2, 3], [4, 5, 6], [7, 8, 9]] #guard isValidInput [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] #guard isValidInput [[1]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [[1, 2], [3]]) #guard !(isValidInput [[(-101)]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard spiralOrder_check [[1, 2, 3], [4, 5, 6], [7, 8, 9]] [1, 2, 3, 6, 9, 8, 7, 4, 5] #guard spiralOrder_check [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7] #guard spiralOrder_check [[1]] [1] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(spiralOrder_check [[1, 2, 3], [4, 5, 6], [7, 8, 9]] [1, 2, 3, 4, 5, 6, 7, 8, 9]) #guard !(spiralOrder_check [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] [1, 5, 9, 10, 11, 12, 8, 4, 3, 2, 6, 7]) #guard !(spiralOrder_check [[1]] []) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard matrixSpiralOrder [[1, 2, 3], [4, 5, 6], [7, 8, 9]] == [1, 2, 3, 6, 9, 8, 7, 4, 5] #guard matrixSpiralOrder [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] == [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7] #guard matrixSpiralOrder [[1]] == [1] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard spiralOrder_check [[1, 2, 3], [4, 5, 6], [7, 8, 9]] (matrixSpiralOrder [[1, 2, 3], [4, 5, 6], [7, 8, 9]]) #guard spiralOrder_check [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] (matrixSpiralOrder [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]) #guard spiralOrder_check [[1]] (matrixSpiralOrder [[1]]) end PSpiralMatrix