import Mathlib /-! # Count And Say The count-and-say sequence is a sequence of digit strings defined by the recursive formula: countAndSay(1) = "1" countAndSay(n) is the run-length encoding of countAndSay(n - 1). Run-length encoding (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "3322251" we replace "33" with "23", replace "222" with "32", replace "5" with "15" and replace "1" with "11". Thus the compressed string becomes "23321511". Given a positive integer n, return the nth element of the count-and-say sequence. ## Constraints - 1 <= n <= 30 ## Provided examples - `n = 4` → `"1211"` - `n = 1` → `"1"` - `n = 23` → `"111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123112221221321132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221"` ## Synthesized negative examples - invalid input: `n = 0` ([structural] a predicate that admits 1 <= n <= 30. one below the stated minimum; catches a predicate that forgot the floor) - invalid input: `n = 31` ([structural] a predicate that admits 1 <= n <= 30. one above the stated maximum; catches a predicate that forgot the ceiling) - invalid input: `n = 100` ([structural] a predicate that admits 1 <= n <= 30. an order of magnitude past the ceiling; a different shape of wrong) - `n = 4` → `"14"` is wrong ([structural] drops the recursive definition and compresses the input number. Returns RLE of n rather than of the previous term.) - `n = 1` → `"11"` is wrong ([structural] sequence index shifted by one. returns countAndSay(2) instead of countAndSay(1)) - `n = 23` → `"1"` is wrong ([structural] no constraint forces applying the recurrence to reach n. returns the base case without work) -/ namespace PCountAndSay abbrev Input := Nat abbrev Output := String /-! ### Specification helpers -/ /-- `enc` is the run-length encoding of the list `s`: each maximal run of `k` copies of `c` becomes the decimal digits of `k` followed by `c`. -/ inductive IsRleList : List Char → List Char → Prop where | nil : IsRleList [] [] | cons (c : Char) (k : Nat) (rest enc : List Char) (hk : 0 < k) (hmax : rest.head? ≠ some c) (h : IsRleList rest enc) : IsRleList (List.replicate k c ++ rest) ((toString k).toList ++ [c] ++ enc) /-- `enc` is the run-length encoding of the string `s`, with singleton runs encoded as well. -/ def IsRunLengthEncoding (enc s : String) : Prop := IsRleList s.toList enc.toList /-- `seq` is a count-and-say sequence: `seq 1 = "1"`, each later term is the run-length encoding of its predecessor, and index 0 is unconstrained. -/ def IsCountAndSaySequence (seq : Nat → String) : Prop := seq 1 = "1" ∧ ∀ k, 2 ≤ k → IsRunLengthEncoding (seq k) (seq (k - 1)) /-! ### Validity predicate (V) -/ /-- Valid input: an index `n` with `1 ≤ n ≤ 30`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input && input ≤ 30 /-! ### Ideal specification (P_spec) -/ /-- `result` is the `input`-th count-and-say term: some count-and-say sequence has `result` at index `input`, and every count-and-say sequence agrees with it there. -/ def countAndSay_spec (input : Input) (result : Output) : Prop := (∃ seq : Nat → String, IsCountAndSaySequence seq ∧ seq input = result) ∧ ∀ seq : Nat → String, IsCountAndSaySequence seq → seq input = result /-! ### Decidable specification (P_check) -/ /-- The encoding of one maximal run: the decimal digits of `k` followed by the character `c`, as in `IsRleList.cons`. -/ def encodeRun (k : Nat) (c : Char) : List Char := (toString k).toList ++ [c] /-- Finish the run-length encoding of a digit list whose current run already holds `k` copies of `cur`. -/ def rleGo (cur : Char) (k : Nat) : List Char → List Char | [] => encodeRun k cur | c :: rest => if c == cur then rleGo cur (k + 1) rest else encodeRun k cur ++ rleGo c 1 rest /-- The run-length encoding of a digit list, emitting each maximal run as its decimal length and digit. -/ def rleList : List Char → List Char | [] => [] | c :: rest => rleGo c 1 rest /-- The `n`-th count-and-say term, obtained by iterating run-length encoding `n - 1` times from `"1"`. -/ def nthTerm (n : Nat) : String := Nat.iterate (fun s => String.ofList (rleList s.toList)) (n - 1) "1" /-- Executable checker for `countAndSay_spec`: the recurrence determines the sequence, so the `input`-th iterated term must equal `result`. -/ def countAndSay_check (input : Input) (result : Output) : Bool := decide (nthTerm input = result) theorem rleGo_replicate (c : Char) (rest : List Char) : ∀ (j m : Nat), rleGo c m (List.replicate j c ++ rest) = rleGo c (m + j) rest := by intro j induction j with | zero => intro m; simp | succ j ih => intro m rw [List.replicate_succ, List.cons_append, rleGo, if_pos (by simp), ih] congr 1; omega theorem rleGo_stop (c : Char) (m : Nat) (rest : List Char) (hmax : rest.head? ≠ some c) : rleGo c m rest = encodeRun m c ++ rleList rest := by cases rest with | nil => simp [rleGo, rleList] | cons d r => have hd : d ≠ c := by simpa using hmax rw [rleGo, if_neg (by simpa using hd), rleList] theorem rleList_of_IsRleList {A B : List Char} (hr : IsRleList A B) : B = rleList A := by induction hr with | nil => rfl | cons c k rest enc hk hmax _ ih => obtain ⟨j, rfl⟩ : ∃ j, k = j + 1 := ⟨k - 1, by omega⟩ rw [List.replicate_succ, List.cons_append, rleList, rleGo_replicate, rleGo_stop c _ rest hmax, ih, encodeRun, Nat.add_comm] theorem IsRleList_rleGo : ∀ (rest : List Char) (c : Char) (m : Nat), 0 < m → IsRleList (List.replicate m c ++ rest) (rleGo c m rest) := by intro rest induction rest with | nil => intro c m hm have h := IsRleList.cons c m [] [] hm (by simp) IsRleList.nil simpa [rleGo, encodeRun] using h | cons d r ih => intro c m hm by_cases hdc : d = c · subst hdc have h := ih d (m + 1) (by omega) rw [rleGo, if_pos (by simp)] rwa [List.replicate_succ', List.append_assoc] at h · rw [rleGo, if_neg (by simpa using hdc)] have h := IsRleList.cons c m (d :: r) (rleGo d 1 r) hm (by simpa using hdc) (by simpa using ih d 1 (by omega)) simpa [encodeRun] using h theorem IsRleList_iff (A B : List Char) : IsRleList A B ↔ B = rleList A := by constructor · exact rleList_of_IsRleList · rintro rfl cases A with | nil => exact IsRleList.nil | cons c rest => simpa [rleList] using IsRleList_rleGo rest c 1 (by omega) theorem nthTerm_succ (n : Nat) (hn : 1 ≤ n) : nthTerm (n + 1) = String.ofList (rleList (nthTerm n).toList) := by obtain ⟨j, rfl⟩ : ∃ j, n = j + 1 := ⟨n - 1, by omega⟩ simp only [nthTerm, Nat.add_sub_cancel] exact Function.iterate_succ_apply' _ _ _ theorem seq_eq_nthTerm (seq : Nat → String) (hs : IsCountAndSaySequence seq) : ∀ n, 1 ≤ n → seq n = nthTerm n := by intro n hn induction n, hn using Nat.le_induction with | base => exact hs.1 | succ n hn ih => have h := hs.2 (n + 1) (by omega) unfold IsRunLengthEncoding at h rw [IsRleList_iff, Nat.add_sub_cancel, ih] at h rw [nthTerm_succ n hn, ← h, String.ofList_toList] theorem nthTerm_isSeq : IsCountAndSaySequence nthTerm := by refine ⟨rfl, fun k hk => ?_⟩ obtain ⟨n, rfl⟩ : ∃ n, k = n + 1 := ⟨k - 1, by omega⟩ unfold IsRunLengthEncoding rw [IsRleList_iff, Nat.add_sub_cancel] rcases Nat.eq_zero_or_pos n with rfl | hn · omega · rw [nthTerm_succ n hn, String.toList_ofList] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem countAndSay_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : countAndSay_check input result ↔ countAndSay_spec input result := by have h1 : 1 ≤ input := by simp [isValidInput] at h; exact h.1 unfold countAndSay_check countAndSay_spec rw [decide_eq_true_iff] constructor · rintro rfl exact ⟨⟨nthTerm, nthTerm_isSeq, rfl⟩, fun seq hs => seq_eq_nthTerm seq hs input h1⟩ · rintro ⟨⟨seq, hs, rfl⟩, -⟩ exact (seq_eq_nthTerm seq hs input h1).symm /-! ### Main algorithm (impl) -/ /-- The nth count-and-say term, computed by the checker's iterated run-length encoding from "1". -/ def nthCountAndSay (input : Input) : Output := nthTerm input /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem nthCountAndSay_correct (input : Input) (h : isValidInput input) : countAndSay_spec input (nthCountAndSay input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 4 #guard isValidInput 1 #guard isValidInput 23 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 0) #guard !(isValidInput 31) #guard !(isValidInput 100) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard countAndSay_check 4 "1211" #guard countAndSay_check 1 "1" #guard countAndSay_check 23 "111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123112221221321132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(countAndSay_check 4 "14") #guard !(countAndSay_check 1 "11") #guard !(countAndSay_check 23 "1") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard nthCountAndSay 4 == "1211" #guard nthCountAndSay 1 == "1" #guard nthCountAndSay 23 == "111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123112221221321132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard countAndSay_check 4 (nthCountAndSay 4) #guard countAndSay_check 1 (nthCountAndSay 1) #guard countAndSay_check 23 (nthCountAndSay 23) end PCountAndSay