import Mathlib /-! # Spiral Matrix Ii Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order. ## Constraints - 1 <= n <= 20 ## Provided examples - `n = 3` → `[[1, 2, 3], [8, 9, 4], [7, 6, 5]]` - `n = 1` → `[[1]]` - `n = 2` → `[[1, 2], [4, 3]]` ## Synthesized negative examples - invalid input: `n = 0` ([structural] a predicate that admits 1 <= n <= 20. empty matrix; below the minimum dimension) - invalid input: `n = 21` ([structural] a predicate that admits 1 <= n <= 20. one past the stated maximum) - invalid input: `n = 100` ([structural] a predicate that admits 1 <= n <= 20. two orders of magnitude past the maximum) - `n = 3` → `[[1, 2, 3], [4, 5, 6], [7, 8, 9]]` is wrong ([structural] spiral order omitted; any arrangement of 1..9 accepted. row-major fill satisfies shape and content, fails spiral) - `n = 1` → `[[0]]` is wrong ([structural] nothing requires the entries to be the integers 1..n^2; an all-zero matrix is accepted. zero is the trivial fill) - `n = 2` → `[[0, 1], [3, 2]]` is wrong ([structural] range is not required to start at 1. values are one lower, but still a spiral) -/ namespace PSpiralMatrixIi abbrev Input := Nat abbrev Output := List (List Nat) /-! ### Specification helpers -/ /-- `t` is the number placed at zero-based row `r` and column `c` in the clockwise `n × n` spiral beginning at the top-left. -/ def SpiralOrdering (n r c t : Nat) : Prop := r < n ∧ c < n ∧ let layer := min (min r c) (min (n - 1 - r) (n - 1 - c)) let side := n - 2 * layer let before := 4 * layer * (n - layer) ((r = layer ∧ t = before + 1 + (c - layer)) ∨ (c = layer + side - 1 ∧ t = before + side + (r - layer)) ∨ (r = layer + side - 1 ∧ c < layer + side - 1 ∧ t = before + 2 * side - 1 + (layer + side - 1 - c)) ∨ (c = layer ∧ layer < r ∧ r < layer + side - 1 ∧ t = before + 3 * side - 2 + (layer + side - 1 - r))) /-! ### Validity predicate (V) -/ /-- Valid input: a positive dimension of at most 20. -/ def isValidInput (input : Input) : Bool := 1 ≤ input && input ≤ 20 /-! ### Ideal specification (P_spec) -/ /-- `result` is the `input × input` matrix whose every in-bounds cell contains its unique clockwise spiral number. -/ def spiralMatrix_spec (input : Input) (result : Output) : Prop := result.length = input ∧ (∀ row ∈ result, row.length = input) ∧ ∀ r c : Nat, r < input → c < input → ∃ t : Nat, SpiralOrdering input r c t ∧ (result[r]?).bind (fun row => row[c]?) = some t ∧ ∀ u : Nat, SpiralOrdering input r c u → u = t /-! ### Decidable specification (P_check) -/ /-- Boolean analogue of `SpiralOrdering`, used by the executable checker. -/ def spiralOrderingB (n r c t : Nat) : Bool := decide (r < n) && decide (c < n) && (let layer := min (min r c) (min (n - 1 - r) (n - 1 - c)) let side := n - 2 * layer let before := 4 * layer * (n - layer) (decide (r = layer) && decide (t = before + 1 + (c - layer))) || (decide (c = layer + side - 1) && decide (t = before + side + (r - layer))) || (decide (r = layer + side - 1) && decide (c < layer + side - 1) && decide (t = before + 2 * side - 1 + (layer + side - 1 - c))) || (decide (c = layer) && decide (layer < r) && decide (r < layer + side - 1) && decide (t = before + 3 * side - 2 + (layer + side - 1 - r)))) /-- Executable checker for `spiralMatrix_spec`: cells range over `List.range input` and spiral values over `0 .. input^2`. -/ def spiralMatrix_check (input : Input) (result : Output) : Bool := result.length == input && result.all (fun row => row.length == input) && (List.range input).all fun r => (List.range input).all fun c => (List.range (input * input + 1)).any fun t => spiralOrderingB input r c t && ((result[r]?).bind (fun row => row[c]?) == some t) && (List.range (input * input + 1)).all fun u => !(spiralOrderingB input r c u) || u == t theorem ordering_reflect (n r c t : Nat) : spiralOrderingB n r c t = true ↔ SpiralOrdering n r c t := by simp only [spiralOrderingB, SpiralOrdering, Bool.and_eq_true, Bool.or_eq_true, decide_eq_true_eq, and_assoc, or_assoc] theorem root_of_bridges (bound : ∀ n r c t, isValidInput n → SpiralOrdering n r c t → t < n * n + 1) (input : Input) (result : Output) (h : isValidInput input) : spiralMatrix_check input result ↔ spiralMatrix_spec input result := by simp only [spiralMatrix_check, Bool.and_eq_true, beq_iff_eq, List.all_eq_true, List.mem_range, List.any_eq_true, Bool.or_eq_true, Bool.not_eq_true', Bool.eq_false_iff, ordering_reflect, spiralMatrix_spec] constructor · rintro ⟨⟨hlen, hrows⟩, hc⟩ refine ⟨hlen, hrows, ?_⟩ intro r c hr hc' obtain ⟨t, ht, ⟨ho, he⟩, hu⟩ := hc r hr c hc' refine ⟨t, ho, he, ?_⟩ intro u hou exact (hu u (bound input r c u h hou)).resolve_left (by simpa [ordering_reflect] using hou) · rintro ⟨hlen, hrows, hc⟩ refine ⟨⟨hlen, hrows⟩, ?_⟩ intro r hr c hc' obtain ⟨t, ho, he, hu⟩ := hc r c hr hc' refine ⟨t, bound input r c t h ho, ⟨ho, he⟩, ?_⟩ intro u _ by_cases hou : SpiralOrdering input r c u · exact Or.inr (hu u hou) · exact Or.inl (by simpa [ordering_reflect] using hou) theorem ordering_bound (n r c t : Nat) (_hv : isValidInput n) (ho : SpiralOrdering n r c t) : t < n * n + 1 := by obtain ⟨hr, hc, ho⟩ := ho let l := min (min r c) (min (n - 1 - r) (n - 1 - c)) let s := n - 2 * l let b := 4 * l * (n - l) change (r = l ∧ t = b + 1 + (c - l)) ∨ (c = l + s - 1 ∧ t = b + s + (r - l)) ∨ (r = l + s - 1 ∧ c < l + s - 1 ∧ t = b + 2 * s - 1 + (l + s - 1 - c)) ∨ (c = l ∧ l < r ∧ r < l + s - 1 ∧ t = b + 3 * s - 2 + (l + s - 1 - r)) at ho have hlr : l ≤ r := by dsimp [l]; omega have hlc : l ≤ c := by dsimp [l]; omega have hrl : r + l < n := by dsimp [l]; omega have hcl : c + l < n := by dsimp [l]; omega have hs : s + 2 * l = n := by dsimp [s]; omega have hsp : 0 < s := by omega have hid : b + s * s = n * n := by have hsub : n - l = s + l := by omega dsimp [b] rw [hsub, ← hs] ring have ht : t ≤ b + s * s := by by_cases h1 : s = 1 · have : t ≤ b + 1 := by rcases ho with h | h | h | h <;> omega nlinarith · have h2 : 2 ≤ s := by omega have hmax : t + 4 ≤ b + 4 * s := by rcases ho with h | h | h | h <;> omega have hsq : 4 * s ≤ s * s + 4 := by have he : s - 2 + 2 = s := by omega nlinarith [Nat.zero_le ((s - 2) * (s - 2))] omega omega /-- On valid input the checker accepts exactly the specified outputs. -/ theorem spiralMatrix_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : spiralMatrix_check input result ↔ spiralMatrix_spec input result := by exact root_of_bridges ordering_bound input result h /-! ### Implementation helpers -/ /-- The spiral number at zero-based row `r`, column `c` of the `n × n` grid, by closed-form layer arithmetic. -/ def spiralValue (n r c : Nat) : Nat := let layer := min (min r c) (min (n - 1 - r) (n - 1 - c)) let side := n - 2 * layer let before := 4 * layer * (n - layer) if r = layer then before + 1 + (c - layer) else if c = layer + side - 1 then before + side + (r - layer) else if r = layer + side - 1 then before + 2 * side - 1 + (layer + side - 1 - c) else before + 3 * side - 2 + (layer + side - 1 - r) /-! ### Main algorithm (impl) -/ /-- Builds the spiral matrix by computing each cell's closed-form layer value over the `input × input` grid. -/ def generateSpiralMatrix (input : Input) : Output := (List.range input).map fun r => (List.range input).map fun c => spiralValue input r c /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem generateSpiralMatrix_correct (input : Input) (h : isValidInput input) : spiralMatrix_spec input (generateSpiralMatrix input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 3 #guard isValidInput 1 #guard isValidInput 2 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 0) #guard !(isValidInput 21) #guard !(isValidInput 100) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard spiralMatrix_check 3 [[1, 2, 3], [8, 9, 4], [7, 6, 5]] #guard spiralMatrix_check 1 [[1]] #guard spiralMatrix_check 2 [[1, 2], [4, 3]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(spiralMatrix_check 3 [[1, 2, 3], [4, 5, 6], [7, 8, 9]]) #guard !(spiralMatrix_check 1 [[0]]) #guard !(spiralMatrix_check 2 [[0, 1], [3, 2]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard generateSpiralMatrix 3 == [[1, 2, 3], [8, 9, 4], [7, 6, 5]] #guard generateSpiralMatrix 1 == [[1]] #guard generateSpiralMatrix 2 == [[1, 2], [4, 3]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard spiralMatrix_check 3 (generateSpiralMatrix 3) #guard spiralMatrix_check 1 (generateSpiralMatrix 1) #guard spiralMatrix_check 2 (generateSpiralMatrix 2) end PSpiralMatrixIi