import Mathlib /-! # Zigzag Conversion The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string s, int numRows); ## Constraints - 1 <= s.length <= 1000 - s consists of English letters (lower-case and upper-case), ',' and '.'. - 1 <= numRows <= 1000 ## Provided examples - `s = "PAYPALISHIRING", numRows = 3` → `"PAHNAPLSIIGYIR"` - `s = "PAYPALISHIRING", numRows = 4` → `"PINALSIGYAHRPI"` - `s = "A", numRows = 1` → `"A"` ## Synthesized negative examples - invalid input: `s = "", numRows = 1` ([structural] a predicate that admits 1 <= s.length <= 1000. empty string where at least one character is required) - invalid input: `s = "A", numRows = 0` ([structural] a predicate that admits 1 <= numRows <= 1000. one below the stated minimum rows) - invalid input: `s = "A?", numRows = 1` ([structural] a predicate that admits s consists of English letters (lower-case and upper-case), ',' and '.'.. question mark; a predicate that allows any punctuation accepts it) - `s = "PAYPALISHIRING", numRows = 3` → `"PAYPALISHIRING"` is wrong ([structural] no requirement that the output differs from the input. echoes input; no conversion performed) - `s = "PAYPALISHIRING", numRows = 4` → `"PAHNAPLSIIGYIR"` is wrong ([structural] row count off by one: uses numRows-1 rows. valid conversion for 3 rows, not the given 4) - `s = "A", numRows = 1` → `"a"` is wrong ([structural] case preservation is not required. same character with different case) -/ namespace PZigzagConversion abbrev Input := (String) × (Nat) abbrev Output := String /-! ### Specification helpers -/ /-- The zigzag row the `i`-th character falls in with `numRows` rows: the sequence 0,1,...,numRows−1,numRows−2,...,1 repeats with period `2 * (numRows - 1)`, and is the constant 0 when `numRows ≤ 1`. -/ def zigzagRowIndex (numRows i : Nat) : Nat := if numRows ≤ 1 then 0 else let pos := i % (2 * (numRows - 1)) if pos < numRows then pos else 2 * (numRows - 1) - pos /-- The characters of `s` assigned to row `k` by the zigzag pattern, in their original order. -/ def charsInRow (s : String) (numRows k : Nat) : List Char := s.toList.zipIdx.filterMap fun (c, i) => if zigzagRowIndex numRows i = k then some c else none /-- `rows` is the row-by-row decomposition of `s` under the zigzag pattern with `numRows` rows: it has `numRows` rows and row `k` holds exactly the characters of `s` whose zigzag row index is `k`, in order. -/ def IsZigzagRowAssignment (s : String) (numRows : Nat) (rows : List String) : Prop := rows.length = numRows ∧ ∀ k, k < numRows → rows[k]? = some (String.ofList (charsInRow s numRows k)) /-! ### Validity predicate (V) -/ /-- Valid input: `s` has between 1 and 1000 characters, each an English letter, a comma, or a period, and `numRows` is between 1 and 1000. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 1000 && input.1.toList.all (fun c => ('a' ≤ c && c ≤ 'z') || ('A' ≤ c && c ≤ 'Z') || c = ',' || c = '.') && 1 ≤ input.2 && input.2 ≤ 1000 /-! ### Ideal specification (P_spec) -/ /-- `result` is the zigzag conversion of `input.1` into `input.2` rows: some list of `input.2` row strings concatenates to `result` and is the zigzag row assignment of `input.1`. -/ def zigzagConversion_spec (input : Input) (result : Output) : Prop := ∃ rows : List String, (rows.length = input.2 ∧ String.join rows = result) ∧ IsZigzagRowAssignment input.1 input.2 rows /-! ### Decidable specification (P_check) -/ /-- The unique row list that can witness `zigzagConversion_spec`: row `k` holds exactly the characters `charsInRow` assigns to it. -/ def zigzagRows (s : String) (numRows : Nat) : List String := (List.range numRows).map fun k => String.ofList (charsInRow s numRows k) /-- Executable checker for `zigzagConversion_spec`: the unique witness list joins to `result`. -/ def zigzagConversion_check (input : Input) (result : Output) : Bool := decide (String.join (zigzagRows input.1 input.2) = result) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem zigzagConversion_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : zigzagConversion_check input result ↔ zigzagConversion_spec input result := by simp only [zigzagConversion_check, decide_eq_true_eq] constructor · intro heq refine ⟨zigzagRows input.1 input.2, ⟨?_, heq⟩, ?_, ?_⟩ · simp [zigzagRows] · simp [zigzagRows] · intro k hk simp [zigzagRows, List.getElem?_map, List.getElem?_range hk] · rintro ⟨rows, ⟨hlen, hjoin⟩, hrows⟩ have heq : rows = zigzagRows input.1 input.2 := by apply List.ext_getElem? intro k by_cases hk : k < input.2 · rw [hrows.2 k hk] simp [zigzagRows, List.getElem?_map, List.getElem?_range hk] · have hr : rows[k]? = none := by simp [List.getElem?_eq_none, hlen, Nat.le_of_not_gt hk] rw [hr] simp [zigzagRows, List.getElem?_map, List.getElem?_eq_none, Nat.le_of_not_gt hk] simpa only [heq] using hjoin /-! ### Main algorithm (impl) -/ /-- Zigzag conversion by joining the checker's row-by-row decomposition `zigzagRows`. -/ def convertZigzag (input : Input) : Output := String.join (zigzagRows input.1 input.2) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem convertZigzag_correct (input : Input) (h : isValidInput input) : zigzagConversion_spec input (convertZigzag input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("PAYPALISHIRING", 3) #guard isValidInput ("PAYPALISHIRING", 4) #guard isValidInput ("A", 1) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("", 1)) #guard !(isValidInput ("A", 0)) #guard !(isValidInput ("A?", 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard zigzagConversion_check ("PAYPALISHIRING", 3) "PAHNAPLSIIGYIR" #guard zigzagConversion_check ("PAYPALISHIRING", 4) "PINALSIGYAHRPI" #guard zigzagConversion_check ("A", 1) "A" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(zigzagConversion_check ("PAYPALISHIRING", 3) "PAYPALISHIRING") #guard !(zigzagConversion_check ("PAYPALISHIRING", 4) "PAHNAPLSIIGYIR") #guard !(zigzagConversion_check ("A", 1) "a") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard convertZigzag ("PAYPALISHIRING", 3) == "PAHNAPLSIIGYIR" #guard convertZigzag ("PAYPALISHIRING", 4) == "PINALSIGYAHRPI" #guard convertZigzag ("A", 1) == "A" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard zigzagConversion_check ("PAYPALISHIRING", 3) (convertZigzag ("PAYPALISHIRING", 3)) #guard zigzagConversion_check ("PAYPALISHIRING", 4) (convertZigzag ("PAYPALISHIRING", 4)) #guard zigzagConversion_check ("A", 1) (convertZigzag ("A", 1)) end PZigzagConversion