import Mathlib /-! # Reverse Words In A String Given an input string s, reverse the order of the words. A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space. Return a string of the words in reverse order concatenated by a single space. Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces. ## Constraints - 1 <= s.length <= 10^4 - s contains English letters (upper-case and lower-case), digits, and spaces ' '. - There is at least one word in s. ## Provided examples - `s = "the sky is blue"` → `"blue is sky the"` - `s = " hello world "` → `"world hello"` - `s = "a good example"` → `"example good a"` ## Synthesized negative examples - invalid input: `s = "hello!"` ([structural] a predicate that admits s contains English letters (upper-case and lower-case), digits, and spaces ' '.. punctuation outside the stated alphabet; predicate checking only length and word presence accepts it) - invalid input: `s = " "` ([structural] a predicate that admits There is at least one word in s.. no non-space characters; predicate checking length but not word presence accepts it) - invalid input: `s = "hello world"` ([structural] a predicate that admits s contains English letters (upper-case and lower-case), digits, and spaces ' '.. non-breaking space is not an ASCII space; a predicate using isspace accepts it) - `s = "the sky is blue"` → `"blue is sky the"` is wrong ([structural] drops the single-space separator requirement. words reversed; extra space between blue and is) - `s = " hello world "` → `"hello"` is wrong ([structural] nothing requires every word to appear in the output. returns only the first word, doing no reversal) - `s = "a good example"` → `"example a good"` is wrong ([structural] reverse-order requirement omitted. all words, single spaces, wrong order) -/ namespace PReverseWordsInAString abbrev Input := String abbrev Output := String /-! ### Specification helpers -/ /-- Joins words with the separator that follows each one. -/ def joinWithSeparators : List String → List String → String | [], _ => "" | [w], [] => w | w :: ws, sep :: seps => w ++ sep ++ joinWithSeparators ws seps | _ :: _, [] => "" /-- `ws` is the ordered list of maximal nonempty non-space words in `s`. -/ def IsWordList (s : String) (ws : List String) : Prop := (∀ w ∈ ws, w ≠ "" ∧ ∀ c ∈ w.toList, c ≠ ' ') ∧ ∃ leading trailing : String, ∃ separators : List String, (∀ c ∈ leading.toList, c = ' ') ∧ (∀ c ∈ trailing.toList, c = ' ') ∧ separators.length = ws.length - 1 ∧ (∀ sep ∈ separators, sep ≠ "" ∧ ∀ c ∈ sep.toList, c = ' ') ∧ leading ++ joinWithSeparators ws separators ++ trailing = s /-! ### Validity predicate (V) -/ /-- Valid input has bounded length, uses only ASCII letters, digits, and spaces, and contains a word. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10^4 && input.toList.all (fun c => ('a' ≤ c && c ≤ 'z') || ('A' ≤ c && c ≤ 'Z') || ('0' ≤ c && c ≤ '9') || c == ' ') && input.toList.any (fun c => c != ' ') /-! ### Ideal specification (P_spec) -/ /-- `result` is formed by reversing the words of `input` and joining them with single spaces. -/ def reverseWords_spec (input : Input) (result : Output) : Prop := ∃ ws : List String, (∀ w ∈ ws, w ≠ "") ∧ " ".intercalate ws.reverse = result ∧ IsWordList input ws /-! ### Decidable specification (P_check) -/ /-- The ordered list of maximal nonempty space-free words of `s`. -/ def wordsOf (s : String) : List String := (s.splitToList (· == ' ')).filter (· != "") /-- Executable checker for `reverseWords_spec` over the unique word list of `input`. -/ def reverseWords_check (input : Input) (result : Output) : Bool := decide ((∀ w ∈ wordsOf input, w ≠ "") ∧ " ".intercalate (wordsOf input).reverse = result) /-- The nonempty maximal space-free runs of a character list. -/ noncomputable def wordsC (L : List Char) : List (List Char) := (List.splitOnP (· == ' ') L).filter (fun w => !w.isEmpty) theorem wordsOf_eq (s : String) : wordsOf s = (wordsC s.toList).map String.ofList := by have hp : ((fun (x : String) => x != "") ∘ String.ofList) = (fun w : List Char => !w.isEmpty) := by funext w cases w <;> simp [Function.comp, ← String.toList_inj] unfold wordsOf wordsC rw [String.splitToList_of_valid, List.filter_map, hp] theorem wordsC_nil : wordsC [] = [] := by simp [wordsC] theorem toList_ne_nil {w : String} (h : w ≠ "") : w.toList ≠ [] := fun hc => h (String.toList_inj.mp (by rw [hc, String.toList_empty])) theorem wordsC_cons_space (t : List Char) : wordsC (' ' :: t) = wordsC t := by have h := List.splitOnP_append_cons_of_forall_mem (p := (· == ' ')) (xs := ([] : List Char)) (by simp) ' ' (by simp) t simp only [List.nil_append] at h simp [wordsC, h] theorem wordsC_spaces_append {lead : List Char} (h : ∀ c ∈ lead, c = ' ') (L : List Char) : wordsC (lead ++ L) = wordsC L := by induction lead with | nil => simp | cons c t ih => have hc : c = ' ' := h c (by simp) subst hc rw [List.cons_append, wordsC_cons_space, ih (fun x hx => h x (by simp [hx]))] theorem wordsC_of_all_space {lead : List Char} (h : ∀ c ∈ lead, c = ' ') : wordsC lead = [] := by have h2 := wordsC_spaces_append h ([] : List Char) rw [List.append_nil, wordsC_nil] at h2 exact h2 theorem wordsC_word_cons_space {w : List Char} (hw : w ≠ []) (hfree : ∀ c ∈ w, c ≠ ' ') (t : List Char) : wordsC (w ++ ' ' :: t) = w :: wordsC t := by have h := List.splitOnP_append_cons_of_forall_mem (p := (· == ' ')) (xs := w) (by intro x hx; simpa using hfree x hx) ' ' (by simp) t simp [wordsC, h, List.filter_cons, List.isEmpty_iff, hw] theorem wordsC_word_append_spaces {w trail : List Char} (hw : w ≠ []) (hfree : ∀ c ∈ w, c ≠ ' ') (htr : ∀ c ∈ trail, c = ' ') : wordsC (w ++ trail) = [w] := by cases trail with | nil => rw [List.append_nil, wordsC, List.splitOnP_eq_singleton (by intro x hx; simpa using hfree x hx)] simp [List.filter_cons, List.isEmpty_iff, hw] | cons c t => have hc : c = ' ' := htr c (by simp) subst hc rw [wordsC_word_cons_space hw hfree t, wordsC_of_all_space (fun x hx => htr x (by simp [hx]))] theorem joinWithSeparators_cons_append (x w : String) (ws seps : List String) (h : seps.length = ws.length) : joinWithSeparators ((x ++ w) :: ws) seps = x ++ joinWithSeparators (w :: ws) seps := by cases ws with | nil => cases seps with | nil => simp [joinWithSeparators] | cons s ss => simp at h | cons w2 ws' => cases seps with | nil => simp at h | cons s ss => simp [joinWithSeparators, String.append_assoc] theorem wordsC_join : ∀ (ws seps : List String) (trail : List Char), (∀ w ∈ ws, w ≠ "" ∧ ∀ c ∈ w.toList, c ≠ ' ') → (∀ p ∈ seps, p ≠ "" ∧ ∀ c ∈ p.toList, c = ' ') → seps.length = ws.length - 1 → (∀ c ∈ trail, c = ' ') → wordsC ((joinWithSeparators ws seps).toList ++ trail) = ws.map String.toList := by intro ws induction ws with | nil => intro seps trail _ _ _ htrail rw [show joinWithSeparators ([] : List String) seps = "" from rfl] simp only [String.toList_empty, List.nil_append, List.map_nil] exact wordsC_of_all_space htrail | cons w ws' ih => intro seps trail hws hseps hlen htrail cases ws' with | nil => have hs : seps = [] := List.length_eq_zero_iff.mp (by simpa using hlen) subst hs obtain ⟨hw1, hw2⟩ := hws w (by simp) rw [show joinWithSeparators [w] ([] : List String) = w from rfl] rw [wordsC_word_append_spaces (toList_ne_nil hw1) hw2 htrail] simp | cons w2 ws'' => obtain ⟨sep, seps', rfl⟩ : ∃ a l, seps = a :: l := by cases seps with | nil => simp at hlen | cons a l => exact ⟨a, l, rfl⟩ obtain ⟨hsep1, hsep2⟩ := hseps sep (by simp) obtain ⟨hw1, hw2⟩ := hws w (by simp) obtain ⟨c, rest, hcr⟩ : ∃ c rest, sep.toList = c :: rest := by cases hs : sep.toList with | nil => exact absurd (String.toList_inj.mp (by simp [hs])) hsep1 | cons c r => exact ⟨c, r, rfl⟩ have hc : c = ' ' := hsep2 c (by rw [hcr]; simp) subst hc have hrest : ∀ x ∈ rest, x = ' ' := fun x hx => hsep2 x (by rw [hcr]; simp [hx]) have harg : (joinWithSeparators (w :: w2 :: ws'') (sep :: seps')).toList ++ trail = w.toList ++ ' ' :: (rest ++ ((joinWithSeparators (w2 :: ws'') seps').toList ++ trail)) := by rw [show joinWithSeparators (w :: w2 :: ws'') (sep :: seps') = w ++ sep ++ joinWithSeparators (w2 :: ws'') seps' from rfl] simp only [String.toList_append, hcr] simp [List.append_assoc] rw [harg, wordsC_word_cons_space (toList_ne_nil hw1) hw2, wordsC_spaces_append hrest] rw [ih seps' trail (fun x hx => hws x (by simp [hx])) (fun x hx => hseps x (by simp [hx])) (by simpa using hlen) htrail] simp theorem isWordList_unique {s : String} {ws : List String} (h : IsWordList s ws) : ws = wordsOf s := by unfold IsWordList at h obtain ⟨hws, lead, trail, seps, hlead, htrail, hlen, hseps, heq⟩ := h have hkey : wordsC s.toList = ws.map String.toList := by rw [← heq] rw [show (lead ++ joinWithSeparators ws seps ++ trail).toList = lead.toList ++ ((joinWithSeparators ws seps).toList ++ trail.toList) by simp [String.toList_append, List.append_assoc]] rw [wordsC_spaces_append hlead] exact wordsC_join ws seps trail.toList hws hseps hlen htrail rw [wordsOf_eq, hkey] simp [List.map_map, Function.comp] theorem exists_isWordList (L : List Char) : ∃ ws, IsWordList (String.ofList L) ws := by induction L with | nil => refine ⟨[], ?_⟩ unfold IsWordList refine ⟨by simp, "", "", [], by simp, by simp, by simp, by simp, ?_⟩ rw [show joinWithSeparators ([] : List String) ([] : List String) = "" from rfl] rw [← String.toList_inj] simp | cons c L' ih => obtain ⟨ws, hw⟩ := ih by_cases hc : c = ' ' · subst hc unfold IsWordList at hw obtain ⟨hws, lead, trail, seps, hlead, htrail, hlen, hseps, heq⟩ := hw have heqL := congrArg String.toList heq simp only [String.toList_append, String.toList_ofList] at heqL refine ⟨ws, ?_⟩ unfold IsWordList refine ⟨hws, String.ofList [' '] ++ lead, trail, seps, ?_, htrail, hlen, hseps, ?_⟩ · intro x hx simp only [String.toList_append, String.toList_ofList, List.mem_append, List.mem_singleton] at hx rcases hx with h1 | h1 · exact h1 · exact hlead x h1 · rw [← String.toList_inj] simp only [String.toList_append, String.toList_ofList] rw [← heqL] simp [List.append_assoc] · have hcne : String.ofList [c] ≠ "" := by simp [← String.toList_inj] have hcfree : ∀ x ∈ (String.ofList [c]).toList, x ≠ ' ' := by intro x hx simp only [String.toList_ofList, List.mem_singleton] at hx subst hx; exact hc cases ws with | nil => unfold IsWordList at hw obtain ⟨hws, lead, trail, seps, hlead, htrail, hlen, hseps, heq⟩ := hw have heqL := congrArg String.toList heq simp only [String.toList_append, String.toList_ofList, show joinWithSeparators ([] : List String) seps = "" from rfl, String.toList_empty, List.nil_append, List.append_nil] at heqL refine ⟨[String.ofList [c]], ?_⟩ unfold IsWordList refine ⟨?_, "", lead ++ trail, [], by simp, ?_, by simp, by simp, ?_⟩ · intro x hx simp only [List.mem_singleton] at hx subst hx exact ⟨hcne, hcfree⟩ · intro x hx simp only [String.toList_append, List.mem_append] at hx rcases hx with h1 | h1 · exact hlead x h1 · exact htrail x h1 · rw [show joinWithSeparators [String.ofList [c]] ([] : List String) = String.ofList [c] from rfl] rw [← String.toList_inj] simp only [String.toList_append, String.toList_ofList, String.toList_empty] rw [← heqL] simp [List.append_assoc] | cons w ws' => unfold IsWordList at hw obtain ⟨hws, lead, trail, seps, hlead, htrail, hlen, hseps, heq⟩ := hw have heqL := congrArg String.toList heq simp only [String.toList_append, String.toList_ofList] at heqL obtain ⟨hw1, hw2⟩ := hws w (by simp) by_cases hl : lead = "" · subst hl refine ⟨(String.ofList [c] ++ w) :: ws', ?_⟩ unfold IsWordList refine ⟨?_, "", trail, seps, by simp, htrail, by simpa using hlen, hseps, ?_⟩ · intro x hx simp only [List.mem_cons] at hx rcases hx with rfl | hx · refine ⟨?_, ?_⟩ · intro hcon have hnil : (String.ofList [c] ++ w).toList = ([] : List Char) := by rw [hcon, String.toList_empty] simp [String.toList_append, String.toList_ofList] at hnil · intro y hy simp only [String.toList_append, String.toList_ofList, List.mem_append, List.mem_singleton] at hy rcases hy with rfl | hy · exact hc · exact hw2 y hy · exact hws x (by simp [hx]) · rw [joinWithSeparators_cons_append _ _ _ _ (by simpa using hlen)] rw [← String.toList_inj] simp only [String.toList_append, String.toList_ofList] rw [← heqL] simp [List.append_assoc] · refine ⟨String.ofList [c] :: w :: ws', ?_⟩ unfold IsWordList refine ⟨?_, "", trail, lead :: seps, by simp, htrail, by simp only [List.length_cons] at hlen ⊢; omega, ?_, ?_⟩ · intro x hx simp only [List.mem_cons] at hx rcases hx with rfl | hx · exact ⟨hcne, hcfree⟩ · exact hws x (by simp [hx]) · intro x hx simp only [List.mem_cons] at hx rcases hx with rfl | hx · exact ⟨hl, hlead⟩ · exact hseps x hx · rw [show joinWithSeparators (String.ofList [c] :: w :: ws') (lead :: seps) = String.ofList [c] ++ lead ++ joinWithSeparators (w :: ws') seps from rfl] rw [← String.toList_inj] simp only [String.toList_append, String.toList_ofList, String.toList_empty] rw [← heqL] simp [List.append_assoc] theorem wordsOf_isWordList (s : String) : IsWordList s (wordsOf s) := by obtain ⟨ws, hws⟩ := exists_isWordList s.toList rw [String.ofList_toList] at hws rw [← isWordList_unique hws] exact hws /-- On valid input the checker accepts exactly the specified outputs. -/ theorem reverseWords_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : reverseWords_check input result ↔ reverseWords_spec input result := by unfold reverseWords_check reverseWords_spec rw [decide_eq_true_iff] constructor · rintro ⟨h1, h2⟩ exact ⟨wordsOf input, h1, h2, wordsOf_isWordList input⟩ · rintro ⟨ws, hne, hjoin, hiw⟩ have hws : ws = wordsOf input := isWordList_unique hiw subst hws exact ⟨hne, hjoin⟩ /-! ### Main algorithm (impl) -/ /-- Reverses word order by splitting into words, reversing the list, and rejoining with single spaces. -/ def reverseWordsImpl (input : Input) : Output := " ".intercalate (wordsOf input).reverse /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem reverseWordsImpl_correct (input : Input) (h : isValidInput input) : reverseWords_spec input (reverseWordsImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "the sky is blue" #guard isValidInput " hello world " #guard isValidInput "a good example" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "hello!") #guard !(isValidInput " ") #guard !(isValidInput "hello world") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard reverseWords_check "the sky is blue" "blue is sky the" #guard reverseWords_check " hello world " "world hello" #guard reverseWords_check "a good example" "example good a" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(reverseWords_check "the sky is blue" "blue is sky the") #guard !(reverseWords_check " hello world " "hello") #guard !(reverseWords_check "a good example" "example a good") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard reverseWordsImpl "the sky is blue" == "blue is sky the" #guard reverseWordsImpl " hello world " == "world hello" #guard reverseWordsImpl "a good example" == "example good a" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard reverseWords_check "the sky is blue" (reverseWordsImpl "the sky is blue") #guard reverseWords_check " hello world " (reverseWordsImpl " hello world ") #guard reverseWords_check "a good example" (reverseWordsImpl "a good example") end PReverseWordsInAString