import Mathlib /-! # Length Of Last Word Given a string s consisting of words and spaces, return the length of the last word in the string. A word is a maximal substring consisting of non-space characters only. ## Constraints - 1 <= s.length <= 10^4 - s consists of only English letters and spaces ' '. - There will be at least one word in s. ## Provided examples - `s = "Hello World"` → `5` - `s = " fly me to the moon "` → `4` - `s = "luffy is still joyboy"` → `6` ## Synthesized negative examples - invalid input: `s = " "` ([structural] a predicate that admits There will be at least one word in s.. spaces only, so no word exists) - invalid input: `s = "hello!"` ([structural] a predicate that admits s consists of only English letters and spaces ' '.. exclamation mark outside stated alphabet) - invalid input: `s = "hello123"` ([structural] a predicate that admits s consists of only English letters and spaces ' '.. digit; predicate using isalnum() accepts it) - `s = "Hello World"` → `6` is wrong ([structural] length counted from the last space to the end, including the space. includes the space before World) - `s = " fly me to the moon "` → `5` is wrong ([structural] off-by-one error when counting the last word. last word 'moon' has length 4; returns 5) - `s = "luffy is still joyboy"` → `7` is wrong ([structural] tightness omitted: any value at least the last-word length is accepted. 7 satisfies a lower-bound-only reading) -/ namespace PLengthOfLastWord abbrev Input := String abbrev Output := Nat /-! ### Specification helpers -/ /-- `i` lies in the last word of `s`, the maximal block of non-space characters after which only spaces remain. -/ def IsLastWordPos (s : String) (i : Nat) : Prop := ∃ start len : Nat, start + len ≤ s.toList.length ∧ (∀ j, start ≤ j → j < start + len → s.toList[j]? ≠ some ' ') ∧ (∀ j, start + len ≤ j → j < s.toList.length → s.toList[j]? = some ' ') ∧ (start = 0 ∨ s.toList[start - 1]? = some ' ') ∧ start ≤ i ∧ i < start + len /-! ### Validity predicate (V) -/ /-- Valid input: a string of length 1 to 10^4 over English letters and spaces containing at least one word. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10^4 && input.toList.all (fun c => c == ' ' || ('a' ≤ c && c ≤ 'z') || ('A' ≤ c && c ≤ 'Z')) && input.toList.any (fun c => c != ' ') /-! ### Ideal specification (P_spec) -/ /-- `result` is the length of the last word of `input`: some finite set of positions of `input` has cardinality `result` and contains exactly the last-word positions. -/ def lastWordLength_spec (input : Input) (result : Output) : Prop := ∃ c : Finset Nat, c.card = result ∧ (∀ i ∈ c, i < input.toList.length) ∧ ∀ i, i ∈ c ↔ IsLastWordPos input i /-! ### Decidable specification (P_check) -/ /-- Decides the "no spaces inside the candidate word" clause of `IsLastWordPos` by bounding `j` at `start + len`. -/ instance decNonSpaceRun (s : String) (start len : Nat) : Decidable (∀ j, start ≤ j → j < start + len → s.toList[j]? ≠ some ' ') := decidable_of_iff (∀ j < start + len, start ≤ j → s.toList[j]? ≠ some ' ') (by constructor · intro h j h1 h2 exact h j h2 h1 · intro h j h2 h1 exact h j h1 h2) /-- Decides the "only spaces after the candidate word" clause of `IsLastWordPos` by bounding `j` at the string length. -/ instance decSpaceTail (s : String) (start len : Nat) : Decidable (∀ j, start + len ≤ j → j < s.toList.length → s.toList[j]? = some ' ') := decidable_of_iff (∀ j < s.toList.length, start + len ≤ j → s.toList[j]? = some ' ') (by constructor · intro h j h1 h2 exact h j h2 h1 · intro h j h2 h1 exact h j h1 h2) /-- Decides `IsLastWordPos s i` by bounding `start` and `len` at the string length plus one, which the `start + len ≤ length` constraint justifies. -/ instance decIsLastWordPos (s : String) (i : Nat) : Decidable (IsLastWordPos s i) := by unfold IsLastWordPos exact decidable_of_iff (∃ start < s.toList.length + 1, ∃ len < s.toList.length + 1, start + len ≤ s.toList.length ∧ (∀ j, start ≤ j → j < start + len → s.toList[j]? ≠ some ' ') ∧ (∀ j, start + len ≤ j → j < s.toList.length → s.toList[j]? = some ' ') ∧ (start = 0 ∨ s.toList[start - 1]? = some ' ') ∧ start ≤ i ∧ i < start + len) (by constructor · rintro ⟨start, -, len, -, h⟩ exact ⟨start, len, h⟩ · rintro ⟨start, len, h⟩ have hle := h.1 exact ⟨start, by omega, len, by omega, h⟩) /-- Decides the unfolded `lastWordLength_spec`: any witnessing finset is exactly the last-word positions below `input.toList.length`, so the specification is equivalent to that finset's cardinality being `result`. -/ instance decLastWordLengthSpec (input : Input) (result : Output) : Decidable (∃ c : Finset Nat, c.card = result ∧ (∀ i ∈ c, i < input.toList.length) ∧ ∀ i, i ∈ c ↔ IsLastWordPos input i) := decidable_of_iff (((Finset.range input.toList.length).filter fun i => IsLastWordPos input i).card = result) (by constructor · intro h refine ⟨_, h, ?_, ?_⟩ · intro i hi exact Finset.mem_range.mp (Finset.mem_filter.mp hi).1 · intro i constructor · intro hi exact (Finset.mem_filter.mp hi).2 · intro hp apply Finset.mem_filter.mpr refine ⟨Finset.mem_range.mpr ?_, hp⟩ obtain ⟨start, len, hle, -, -, -, -, hlt⟩ := hp omega · rintro ⟨c, hcard, hb, hiff⟩ have hc : c = (Finset.range input.toList.length).filter fun i => IsLastWordPos input i := by ext i simp only [Finset.mem_filter, Finset.mem_range] constructor · intro hi exact ⟨hb i hi, (hiff i).mp hi⟩ · rintro ⟨-, hp⟩ exact (hiff i).mpr hp rw [← hc] exact hcard) /-- Executable checker obtained mechanically from the specification. -/ def lastWordLength_check (input : Input) (result : Output) : Bool := @decide (lastWordLength_spec input result) (by unfold lastWordLength_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem lastWordLength_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : lastWordLength_check input result ↔ lastWordLength_spec input result := by simp [lastWordLength_check] /-! ### Implementation helpers -/ /-- Skips the leading spaces of `cs` (the trailing spaces of the original string), then counts the consecutive non-space characters up to the next space or the end of the list. -/ def scanLastWord (cs : List Char) (counting : Bool) : Nat := match cs with | [] => 0 | c :: rest => if counting then if c == ' ' then 0 else 1 + scanLastWord rest true else if c == ' ' then scanLastWord rest false else 1 + scanLastWord rest true /-! ### Main algorithm (impl) -/ /-- Length of the last word by a single backward scan: reverse the character list, skip the trailing spaces, and count the final run of non-space characters. -/ def lengthOfLastWord (input : Input) : Output := scanLastWord input.toList.reverse false /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem lengthOfLastWord_correct (input : Input) (h : isValidInput input) : lastWordLength_spec input (lengthOfLastWord input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "Hello World" #guard isValidInput " fly me to the moon " #guard isValidInput "luffy is still joyboy" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput " ") #guard !(isValidInput "hello!") #guard !(isValidInput "hello123") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard lastWordLength_check "Hello World" 5 #guard lastWordLength_check " fly me to the moon " 4 #guard lastWordLength_check "luffy is still joyboy" 6 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(lastWordLength_check "Hello World" 6) #guard !(lastWordLength_check " fly me to the moon " 5) #guard !(lastWordLength_check "luffy is still joyboy" 7) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard lengthOfLastWord "Hello World" == 5 #guard lengthOfLastWord " fly me to the moon " == 4 #guard lengthOfLastWord "luffy is still joyboy" == 6 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard lastWordLength_check "Hello World" (lengthOfLastWord "Hello World") #guard lastWordLength_check " fly me to the moon " (lengthOfLastWord " fly me to the moon ") #guard lastWordLength_check "luffy is still joyboy" (lengthOfLastWord "luffy is still joyboy") end PLengthOfLastWord