import Mathlib /-! # Reverse Words In A String Iii Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order. ## Constraints - 1 <= s.length <= 5 * 10^4 - s contains printable ASCII characters. - s does not contain any leading or trailing spaces. - There is at least one word in s. - All the words in s are separated by a single space. ## Provided examples - `s = "Let's take LeetCode contest"` → `"s'teL ekat edoCteeL tsetnoc"` - `s = "Mr Ding"` → `"rM gniD"` - `s = "a"` → `"a"` ## Synthesized negative examples - invalid input: `s = ""` ([structural] a predicate that admits 1 <= s.length <= 5 * 10^4. empty string below minimum length) - invalid input: `s = " a"` ([structural] a predicate that admits s does not contain any leading or trailing spaces.. leading space; a strip()-based validator accepts it) - invalid input: `s = "a b"` ([structural] a predicate that admits All the words in s are separated by a single space.. two spaces between words; whitespace-splitting validator accepts it) - `s = "Let's take LeetCode contest"` → `"s'teL ekat LeetCode contest"` is wrong ([structural] missing requirement that every word is reversed. Reverses first two words only; still a valid partial transformation.) - `s = "Mr Ding"` → `"gniD rM"` is wrong ([structural] No requirement to preserve initial word order. reverses whole sentence, breaking word order but keeping per-word reversal) - `s = "a"` → `"a "` is wrong ([structural] output length may be one more than input. word reversed correctly, one extra trailing space) -/ namespace PReverseWordsInAStringIii abbrev Input := String abbrev Output := String /-! ### Specification helpers -/ /-- `[a, b)` is a maximal contiguous block of non-space characters of `s`. -/ def IsWordSegment (s : String) (a b : Nat) : Prop := a < b ∧ b ≤ s.length ∧ (∀ i, a ≤ i → i < b → s.toList[i]? ≠ some ' ') ∧ (a = 0 ∨ s.toList[a - 1]? = some ' ') ∧ (b = s.length ∨ s.toList[b]? = some ' ') /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 50000 printable ASCII characters, no leading or trailing space, at least one word, words separated by single spaces. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 50000 && input.toList.all (fun c => 32 ≤ c.toNat && c.toNat ≤ 126) && input.toList.head? != some ' ' && input.toList.getLast? != some ' ' && input.toList.any (fun c => c != ' ') && !(input.toList.zip input.toList.tail).any (fun p => p.1 == ' ' && p.2 == ' ') /-! ### Ideal specification (P_spec) -/ /-- `result` is `input` with each word reversed in place: same length, spaces at the same positions, and every word segment `[a, b)` reads backwards. -/ def reverseWords_spec (input : Input) (result : Output) : Prop := (result.length = input.length ∧ ∀ i, i < input.length → ((input.toList[i]? = some ' ') ↔ (result.toList[i]? = some ' '))) ∧ (∀ a b, IsWordSegment input a b → ∀ k, k < b - a → result.toList[a + k]? = input.toList[b - 1 - k]?) /-! ### Decidable specification (P_check) -/ /-- Bounded executable test for the frozen maximal non-space segment predicate. -/ def wordSegmentOk (s : String) (a b : Nat) : Bool := decide (a < b ∧ b ≤ s.length ∧ (∀ i : Fin b, a ≤ i.val → s.toList[i.val]? ≠ some ' ') ∧ (a = 0 ∨ s.toList[a - 1]? = some ' ') ∧ (b = s.length ∨ s.toList[b]? = some ' ')) /-- Executable checker for `reverseWords_spec` over bounded positions and segments. -/ def reverseWords_check (input : Input) (result : Output) : Bool := decide ((result.length = input.length ∧ ∀ i : Fin input.length, (input.toList[i.val]? = some ' ') ↔ (result.toList[i.val]? = some ' ')) ∧ (∀ a : Fin input.length, ∀ b : Fin (input.length + 1), wordSegmentOk input a.val b.val = true → ∀ k : Fin (b.val - a.val), result.toList[a.val + k.val]? = input.toList[b.val - 1 - k.val]?)) theorem wordSegmentOk_iff (s : String) (a b : Nat) : wordSegmentOk s a b = true ↔ IsWordSegment s a b := by unfold wordSegmentOk IsWordSegment rw [decide_eq_true_iff] constructor · rintro ⟨h1, h2, h3, h4, h5⟩ exact ⟨h1, h2, fun i hi hib => h3 ⟨i, hib⟩ hi, h4, h5⟩ · rintro ⟨h1, h2, h3, h4, h5⟩ exact ⟨h1, h2, fun i hi => h3 i.val hi i.isLt, h4, h5⟩ /-- 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 ⟨⟨hl, hsp⟩, hw⟩ refine ⟨⟨hl, fun i hi => hsp ⟨i, hi⟩⟩, ?_⟩ intro a b hab k hk have ha : a < b := hab.1 have hb : b ≤ input.length := hab.2.1 exact hw ⟨a, by omega⟩ ⟨b, by omega⟩ ((wordSegmentOk_iff _ _ _).mpr hab) ⟨k, hk⟩ · rintro ⟨⟨hl, hsp⟩, hw⟩ refine ⟨⟨hl, fun i => hsp i.val i.isLt⟩, ?_⟩ intro a b hab k exact hw a.val b.val ((wordSegmentOk_iff _ _ _).mp hab) k.val k.isLt /-! ### Main algorithm (impl) -/ /-- Reverses each word in place by splitting the character list at spaces, reversing each piece, and rejoining with single spaces, in O(n). -/ def reverseWordsInString (input : Input) : Output := String.mk (List.intercalate [' '] ((input.toList.splitOn ' ').map List.reverse)) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem reverseWordsInString_correct (input : Input) (h : isValidInput input) : reverseWords_spec input (reverseWordsInString input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "Let's take LeetCode contest" #guard isValidInput "Mr Ding" #guard isValidInput "a" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "") #guard !(isValidInput " a") #guard !(isValidInput "a b") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard reverseWords_check "Let's take LeetCode contest" "s'teL ekat edoCteeL tsetnoc" #guard reverseWords_check "Mr Ding" "rM gniD" #guard reverseWords_check "a" "a" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(reverseWords_check "Let's take LeetCode contest" "s'teL ekat LeetCode contest") #guard !(reverseWords_check "Mr Ding" "gniD rM") #guard !(reverseWords_check "a" "a ") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard reverseWordsInString "Let's take LeetCode contest" == "s'teL ekat edoCteeL tsetnoc" #guard reverseWordsInString "Mr Ding" == "rM gniD" #guard reverseWordsInString "a" == "a" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard reverseWords_check "Let's take LeetCode contest" (reverseWordsInString "Let's take LeetCode contest") #guard reverseWords_check "Mr Ding" (reverseWordsInString "Mr Ding") #guard reverseWords_check "a" (reverseWordsInString "a") end PReverseWordsInAStringIii