import Mathlib /-! # Rotate Image You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. ## Constraints - n == matrix.length == matrix[i].length - 1 <= n <= 20 - -1000 <= matrix[i][j] <= 1000 ## Provided examples - `matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]` → `[[7, 4, 1], [8, 5, 2], [9, 6, 3]]` - `matrix = [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]` → `[[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]` - `matrix = [[1]]` → `[[1]]` ## Synthesized negative examples - invalid input: `matrix = []` ([structural] a predicate that admits 1 <= n <= 20. empty matrix below minimum n) - invalid input: `matrix = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]` ([structural] a predicate that admits 1 <= n <= 20. one past maximum n) - invalid input: `matrix = [[1, 2, 3], [4, 5, 6]]` ([structural] a predicate that admits n == matrix.length == matrix[i].length. rows uniform but not square; row-length-only check accepts) - `matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]` → `[[3, 6, 9], [2, 5, 8], [1, 4, 7]]` is wrong ([structural] specification omits the clockwise direction. counter-clockwise rotation is still a 90-degree rotation) - `matrix = [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]` → `[[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]` is wrong ([structural] rotation condition is omitted; the input itself is accepted as the output. Input echoed, satisfying no-work degenerate answer) - `matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]` → `[[8, 5, 2], [7, 4, 1], [9, 6, 3]]` 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 PRotateImage abbrev Input := List (List Int) abbrev Output := List (List Int) /-! ### Validity predicate (V) -/ /-- Valid input: a square matrix of dimension 1 to 20 with entries in [-1000, 1000]. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 20 && input.all fun row => row.length == input.length && row.all fun x => -1000 ≤ x && x ≤ 1000 /-! ### Ideal specification (P_spec) -/ /-- `result` is `input` rotated 90 degrees clockwise: it is n×n with n = input.length, and its (i, j) entry is the (r, i) entry of `input` for the row r with r + j + 1 = n. -/ def rotateImage_spec (input : Input) (result : Output) : Prop := let n := input.length (result.length = n ∧ ∀ row ∈ result, row.length = n) ∧ ∀ i j : Nat, i < n → j < n → ∀ r : Nat, r + j + 1 = n → (result[i]?).bind (fun row => row[j]?) = (input[r]?).bind (fun row => row[i]?) /-! ### Decidable specification (P_check) -/ /-- Executable checker for `rotateImage_spec`: the `Nat` quantifiers bounded by the specification's own hypotheses are reshaped to `Fin n`, and the row `r` forced by `r + j + 1 = n` is computed as `n - 1 - j`. -/ def rotateImage_check (input : Input) (result : Output) : Bool := let n := input.length decide ((result.length = n ∧ ∀ row ∈ result, row.length = n) ∧ ∀ i j : Fin n, (result[i.val]?).bind (fun row => row[j.val]?) = (input[n - 1 - j.val]?).bind (fun row => row[i.val]?)) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem rotateImage_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : rotateImage_check input result ↔ rotateImage_spec input result := by simp only [rotateImage_check, decide_eq_true_eq, rotateImage_spec] constructor · rintro ⟨hs, hp⟩ refine ⟨hs, ?_⟩ intro i j hi hj r hr have he : input.length - 1 - j = r := by omega simpa only [he] using hp ⟨i, hi⟩ ⟨j, hj⟩ · rintro ⟨hs, hp⟩ refine ⟨hs, ?_⟩ intro i j exact hp i.val j.val i.isLt j.isLt (input.length - 1 - j.val) (by omega) /-! ### Implementation helpers -/ /-- Prepend each element of `xs` onto the corresponding row, padding with singleton rows when the rows run out. -/ def zipCons : List Int → List (List Int) → List (List Int) | [], rows => rows | x :: xs, [] => [x] :: zipCons xs [] | x :: xs, row :: rows => (x :: row) :: zipCons xs rows /-- Transpose the list-of-rows into the list-of-columns by structural recursion on the rows. -/ def transpose : List (List Int) → List (List Int) | [] => [] | row :: rows => zipCons row (transpose rows) /-! ### Main algorithm (impl) -/ /-- 90-degree clockwise rotation as transpose followed by reversing each row, O(n^2). -/ def rotateMatrixClockwise (input : Input) : Output := (transpose input).map List.reverse /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem rotateMatrixClockwise_correct (input : Input) (h : isValidInput input) : rotateImage_spec input (rotateMatrixClockwise 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 [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]] #guard isValidInput [[1]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]) #guard !(isValidInput [[1, 2, 3], [4, 5, 6]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard rotateImage_check [[1, 2, 3], [4, 5, 6], [7, 8, 9]] [[7, 4, 1], [8, 5, 2], [9, 6, 3]] #guard rotateImage_check [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]] [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]] #guard rotateImage_check [[1]] [[1]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(rotateImage_check [[1, 2, 3], [4, 5, 6], [7, 8, 9]] [[3, 6, 9], [2, 5, 8], [1, 4, 7]]) #guard !(rotateImage_check [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]] [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]) #guard !(rotateImage_check [[1, 2, 3], [4, 5, 6], [7, 8, 9]] [[8, 5, 2], [7, 4, 1], [9, 6, 3]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard rotateMatrixClockwise [[1, 2, 3], [4, 5, 6], [7, 8, 9]] == [[7, 4, 1], [8, 5, 2], [9, 6, 3]] #guard rotateMatrixClockwise [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]] == [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]] #guard rotateMatrixClockwise [[1]] == [[1]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard rotateImage_check [[1, 2, 3], [4, 5, 6], [7, 8, 9]] (rotateMatrixClockwise [[1, 2, 3], [4, 5, 6], [7, 8, 9]]) #guard rotateImage_check [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]] (rotateMatrixClockwise [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]) #guard rotateImage_check [[1]] (rotateMatrixClockwise [[1]]) end PRotateImage