import Mathlib /-! # Reverse Words In A String Ii Given a character array 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 a single space. Your code must solve the problem in-place, i.e. without allocating extra space. ## Constraints - 1 <= s.length <= 10^5 - s[i] is an English letter (uppercase or lowercase), digit, or space ' '. - There is at least one word in s. - s does not contain leading or trailing spaces. - All the words in s are guaranteed to be separated by a single space. ## Provided examples - `s = ["t", "h", "e", " ", "s", "k", "y", " ", "i", "s", " ", "b", "l", "u", "e"]` → `["b", "l", "u", "e", " ", "i", "s", " ", "s", "k", "y", " ", "t", "h", "e"]` - `s = ["a"]` → `["a"]` - `s = ["l", "e", "t", "s", " ", "c", "o", "d", "e"]` → `["c", "o", "d", "e", " ", "l", "e", "t", "s"]` ## Synthesized negative examples - invalid input: `s = ["!"]` ([structural] a predicate that admits s[i] is an English letter (uppercase or lowercase), digit, or space ' '.. punctuation outside the allowed alphabet) - invalid input: `s = [" ", "a"]` ([structural] a predicate that admits s does not contain leading or trailing spaces.. leading space) - invalid input: `s = ["a", " ", " ", "b"]` ([structural] a predicate that admits All the words in s are guaranteed to be separated by a single space.. two consecutive spaces between words) - `s = ["t", "h", "e", " ", "s", "k", "y", " ", "i", "s", " ", "b", "l", "u", "e"]` → `["t", "h", "e", " ", "b", "l", "u", "e", " ", "i", "s", " ", "s", "k", "y"]` is wrong ([structural] the first word need not be moved; reversal may be off by one position. reverses all but the first word) - `s = ["a"]` → `["b"]` is wrong ([structural] unattainable not applicable; reversal of words not required. any single character passes if reversal is unstated) - `s = ["l", "e", "t", "s", " ", "c", "o", "d", "e"]` → `["l", "e", "t", "s", " ", "c", "o", "d", "e"]` is wrong ([structural] output not required to be the reversed word order. amended 2026-08-18 alongside its base positive) -/ namespace PReverseWordsInAStringIi abbrev Input := String abbrev Output := String /-! ### Specification helpers -/ /-- The serialized array of one-character strings read as a `String` by concatenation. -/ def charArrayToString (parts : List String) : String := String.join parts /-- `ws` is the left-to-right sequence of nonempty space-free blocks of `s`; leading, trailing and repeated spaces are ignored. -/ def IsWordSequence (s : String) (ws : List String) : Prop := (s.toList.splitOn ' ').filter (fun l => !l.isEmpty) = ws.map (·.toList) /-- `s` is exactly the nonempty words of `ws` joined by single spaces, so it carries no leading or trailing space. -/ def SpellsCanonically (ws : List String) (s : String) : Prop := (∀ w ∈ ws, w ≠ "") ∧ String.intercalate " " ws = s /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 10^5 letters, digits or spaces, with at least one word, no leading or trailing space and single spaces between words. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10 ^ 5 && input.toList.all (fun c => ('a' ≤ c && c ≤ 'z') || ('A' ≤ c && c ≤ 'Z') || ('0' ≤ c && c ≤ '9') || c == ' ') && input.toList.any (· != ' ') && input.toList.head? != some ' ' && input.toList.getLast? != some ' ' && (input.toList.zip input.toList.tail).all (fun p => !(p.1 == ' ' && p.2 == ' ')) /-! ### Ideal specification (P_spec) -/ /-- `result` is `input` with its word order reversed: some list `ws` of nonempty words is the word sequence of `input`, `ws.reverse` is that of `result`, and `result` spells `ws.reverse` canonically. -/ def reverseWords_spec (input : Input) (result : Output) : Prop := ∃ ws : List String, (∀ w ∈ ws, w ≠ "") ∧ IsWordSequence input ws ∧ IsWordSequence result ws.reverse ∧ SpellsCanonically ws.reverse result /-! ### Decidable specification (P_check) -/ /-- Decides `IsWordSequence s ws` by unfolding it to an equality of lists of character lists, which Lean decides by `DecidableEq`. -/ instance decIsWordSequence (s : String) (ws : List String) : Decidable (IsWordSequence s ws) := inferInstanceAs (Decidable ((s.toList.splitOn ' ').filter (fun l => !l.isEmpty) = ws.map (·.toList))) /-- Decides `SpellsCanonically ws s` by unfolding it to a bounded list quantifier over nonempty words conjoined with a string equality, both of which Lean decides. -/ instance decSpellsCanonically (ws : List String) (s : String) : Decidable (SpellsCanonically ws s) := inferInstanceAs (Decidable ((∀ w ∈ ws, w ≠ "") ∧ String.intercalate " " ws = s)) /-- Decides the existential in `reverseWords_spec`: `IsWordSequence input ws` determines `ws` uniquely as the nonempty space-separated blocks of `input` read back as strings, so the quantifier collapses to that one computed list, whose four components are decidable by `List.decidableBAll` and the two instances above. The filter binder is annotated with its type so the lambda cannot elaborate to a stalled metavariable while the instance is synthesized. -/ instance decReverseWordsSpec (input result : String) : Decidable (∃ ws : List String, (∀ w ∈ ws, w ≠ "") ∧ IsWordSequence input ws ∧ IsWordSequence result ws.reverse ∧ SpellsCanonically ws.reverse result) := decidable_of_iff ((∀ w ∈ ((input.toList.splitOn ' ').filter (fun l : List Char => !l.isEmpty)).map String.ofList, w ≠ "") ∧ IsWordSequence input (((input.toList.splitOn ' ').filter (fun l : List Char => !l.isEmpty)).map String.ofList) ∧ IsWordSequence result (((input.toList.splitOn ' ').filter (fun l : List Char => !l.isEmpty)).map String.ofList).reverse ∧ SpellsCanonically (((input.toList.splitOn ' ').filter (fun l : List Char => !l.isEmpty)).map String.ofList).reverse result) (by constructor · intro h exact ⟨_, h⟩ · rintro ⟨ws, hne, hin, hout, hspell⟩ have hws : ws = ((input.toList.splitOn ' ').filter (fun l : List Char => !l.isEmpty)).map String.ofList := by have hin' : (input.toList.splitOn ' ').filter (fun l : List Char => !l.isEmpty) = ws.map (·.toList) := hin rw [hin'] induction ws with | nil => rfl | cons w t ih => simp [String.ofList_toList, ← ih] subst hws exact ⟨hne, hin, hout, hspell⟩) /-- Executable checker obtained mechanically from the specification. -/ def reverseWords_check (input : Input) (result : Output) : Bool := @decide (reverseWords_spec input result) (by unfold reverseWords_spec; infer_instance) /-- 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 simp [reverseWords_check] /-! ### Implementation helpers -/ /-- The nonempty space-separated blocks of `s` read back as strings, in left-to-right order. -/ def wordsOf (s : String) : List String := (s.splitOn " ").filter (fun w : String => !w.isEmpty) /-! ### Main algorithm (impl) -/ /-- Reverses the word order of `input` by splitting into words, reversing the list, and joining with single spaces. -/ def reverseWordOrder (input : Input) : Output := String.intercalate " " (wordsOf input).reverse /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem reverseWordOrder_correct (input : Input) (h : isValidInput input) : reverseWords_spec input (reverseWordOrder input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (charArrayToString ["t", "h", "e", " ", "s", "k", "y", " ", "i", "s", " ", "b", "l", "u", "e"]) #guard isValidInput (charArrayToString ["a"]) #guard isValidInput (charArrayToString ["l", "e", "t", "s", " ", "c", "o", "d", "e"]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (charArrayToString ["!"])) #guard !(isValidInput (charArrayToString [" ", "a"])) #guard !(isValidInput (charArrayToString ["a", " ", " ", "b"])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard reverseWords_check (charArrayToString ["t", "h", "e", " ", "s", "k", "y", " ", "i", "s", " ", "b", "l", "u", "e"]) (charArrayToString ["b", "l", "u", "e", " ", "i", "s", " ", "s", "k", "y", " ", "t", "h", "e"]) #guard reverseWords_check (charArrayToString ["a"]) (charArrayToString ["a"]) #guard reverseWords_check (charArrayToString ["l", "e", "t", "s", " ", "c", "o", "d", "e"]) (charArrayToString ["c", "o", "d", "e", " ", "l", "e", "t", "s"]) /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(reverseWords_check (charArrayToString ["t", "h", "e", " ", "s", "k", "y", " ", "i", "s", " ", "b", "l", "u", "e"]) (charArrayToString ["t", "h", "e", " ", "b", "l", "u", "e", " ", "i", "s", " ", "s", "k", "y"])) #guard !(reverseWords_check (charArrayToString ["a"]) (charArrayToString ["b"])) #guard !(reverseWords_check (charArrayToString ["l", "e", "t", "s", " ", "c", "o", "d", "e"]) (charArrayToString ["l", "e", "t", "s", " ", "c", "o", "d", "e"])) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard reverseWordOrder (charArrayToString ["t", "h", "e", " ", "s", "k", "y", " ", "i", "s", " ", "b", "l", "u", "e"]) == charArrayToString ["b", "l", "u", "e", " ", "i", "s", " ", "s", "k", "y", " ", "t", "h", "e"] #guard reverseWordOrder (charArrayToString ["a"]) == charArrayToString ["a"] #guard reverseWordOrder (charArrayToString ["l", "e", "t", "s", " ", "c", "o", "d", "e"]) == charArrayToString ["c", "o", "d", "e", " ", "l", "e", "t", "s"] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard reverseWords_check (charArrayToString ["t", "h", "e", " ", "s", "k", "y", " ", "i", "s", " ", "b", "l", "u", "e"]) (reverseWordOrder (charArrayToString ["t", "h", "e", " ", "s", "k", "y", " ", "i", "s", " ", "b", "l", "u", "e"])) #guard reverseWords_check (charArrayToString ["a"]) (reverseWordOrder (charArrayToString ["a"])) #guard reverseWords_check (charArrayToString ["l", "e", "t", "s", " ", "c", "o", "d", "e"]) (reverseWordOrder (charArrayToString ["l", "e", "t", "s", " ", "c", "o", "d", "e"])) end PReverseWordsInAStringIi