import Mathlib /-! # Uncommon Words From Two Sentences A sentence is a string of single-space separated words where each word consists only of lowercase letters. A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence. Given two sentences s1 and s2, return a list of all the uncommon words. You may return the answer in any order. ## Constraints - 1 <= s1.length, s2.length <= 200 - s1 and s2 consist of lowercase English letters and spaces. - s1 and s2 do not have leading or trailing spaces. - All the words in s1 and s2 are separated by a single space. ## Provided examples - `s1 = "this apple is sweet", s2 = "this apple is sour"` → `["sweet", "sour"]` - `s1 = "apple apple", s2 = "banana"` → `["banana"]` - `s1 = "apple", s2 = "apple"` → `[]` ## Synthesized negative examples - invalid input: `s1 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", s2 = "banana"` ([structural] a predicate that admits 1 <= s1.length, s2.length <= 200. one past the stated maximum) - invalid input: `s1 = "Apple apple", s2 = "banana"` ([structural] a predicate that admits s1 and s2 consist of lowercase English letters and spaces.. uppercase letter outside the stated alphabet) - invalid input: `s1 = " apple", s2 = "banana"` ([structural] a predicate that admits s1 and s2 do not have leading or trailing spaces.. leading space; a predicate that trims before tokenizing accepts it) - `s1 = "this apple is sweet", s2 = "this apple is sour"` → `[]` is wrong ([structural] completeness is not required; every returned word need only be uncommon. empty list satisfies a soundness-only reading) - `s1 = "apple apple", s2 = "banana"` → `["banana", "apple"]` is wrong ([structural] exactly-once frequency is not enforced. apple appears in s1 only, so dropping frequency admits it) - `s1 = "apple", s2 = "apple"` → `["a"]` is wrong ([structural] requires every uncommon word to appear, but does not forbid extras. apple appears in both sentences so no uncommon words exist; extra a passes a superset reading) -/ namespace PUncommonWordsFromTwoSentences abbrev Input := (String) × (String) abbrev Output := List String /-! ### Specification helpers -/ /-- The words of the sentence `s`, obtained by splitting on single spaces. -/ def words (s : String) : List String := s.splitOn " " /-- `w` is uncommon for `s1` and `s2`: it occurs exactly once in total among the words of the two sentences. -/ def IsUncommonWord (w s1 s2 : String) : Prop := (words s1).count w + (words s2).count w = 1 /-- `s` is a well-formed sentence: 1 to 200 characters of lowercase letters and spaces, with single spaces between nonempty words and none at the edges. -/ def validSentence (s : String) : Bool := 1 ≤ s.length && s.length ≤ 200 && s.toList.all (fun c => ('a' ≤ c && c ≤ 'z') || c = ' ') && (s.splitOn " ").all (fun w => w != "") /-! ### Validity predicate (V) -/ /-- Valid input: both sentences are well-formed per the stated constraints. -/ def isValidInput (input : Input) : Bool := validSentence input.1 && validSentence input.2 /-! ### Ideal specification (P_spec) -/ /-- `result` lists exactly the uncommon words of the two sentences, without repetition and in any order. -/ def uncommonWords_spec (input : Input) (result : Output) : Prop := result.Nodup ∧ ∀ w, w ∈ result ↔ IsUncommonWord w input.1 input.2 /-! ### Decidable specification (P_check) -/ /-- Decides the conjunction in `uncommonWords_spec` by reducing the unbounded quantifier over all strings to bounded quantifiers over `result` and over the words of the two sentences (any uncommon word must occur among them). -/ instance decUncommonWordsSpec (input : Input) (result : Output) : Decidable (result.Nodup ∧ ∀ w, w ∈ result ↔ IsUncommonWord w input.1 input.2) := decidable_of_iff (result.Nodup ∧ (∀ w ∈ result, (words input.1).count w + (words input.2).count w = 1) ∧ (∀ w ∈ words input.1 ++ words input.2, (words input.1).count w + (words input.2).count w = 1 → w ∈ result)) (by constructor · rintro ⟨hnodup, hfwd, hbwd⟩ refine ⟨hnodup, fun w => ⟨fun hw => hfwd w hw, fun hun => ?_⟩⟩ have hun' : (words input.1).count w + (words input.2).count w = 1 := hun apply hbwd w _ hun' rw [← List.count_pos_iff, List.count_append] omega · rintro ⟨hnodup, hall⟩ exact ⟨hnodup, fun w hw => (hall w).1 hw, fun w _ hun => (hall w).2 hun⟩) /-- Executable checker obtained mechanically from the specification. -/ def uncommonWords_check (input : Input) (result : Output) : Bool := @decide (uncommonWords_spec input result) (by unfold uncommonWords_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem uncommonWords_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : uncommonWords_check input result ↔ uncommonWords_spec input result := by simp [uncommonWords_check] /-! ### Implementation helpers -/ /-- The distinct words in `xs`, without repeated entries. -/ def distinctWords : List String → List String | [] => [] | x :: xs => let rest := distinctWords xs if x ∈ rest then rest else x :: rest /-! ### Main algorithm (impl) -/ /-- Finds uncommon words by filtering the distinct words of both sentences with the uncommon-word predicate. -/ def findUncommonWords (input : Input) : Output := (distinctWords (words input.1 ++ words input.2)).filter fun w => decide ((words input.1).count w + (words input.2).count w = 1) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findUncommonWords_correct (input : Input) (h : isValidInput input) : uncommonWords_spec input (findUncommonWords input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("this apple is sweet", "this apple is sour") #guard isValidInput ("apple apple", "banana") #guard isValidInput ("apple", "apple") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "banana")) #guard !(isValidInput ("Apple apple", "banana")) #guard !(isValidInput (" apple", "banana")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard uncommonWords_check ("this apple is sweet", "this apple is sour") ["sweet", "sour"] #guard uncommonWords_check ("apple apple", "banana") ["banana"] #guard uncommonWords_check ("apple", "apple") [] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(uncommonWords_check ("this apple is sweet", "this apple is sour") []) #guard !(uncommonWords_check ("apple apple", "banana") ["banana", "apple"]) #guard !(uncommonWords_check ("apple", "apple") ["a"]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findUncommonWords ("this apple is sweet", "this apple is sour") == ["sweet", "sour"] #guard findUncommonWords ("apple apple", "banana") == ["banana"] #guard findUncommonWords ("apple", "apple") == [] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard uncommonWords_check ("this apple is sweet", "this apple is sour") (findUncommonWords ("this apple is sweet", "this apple is sour")) #guard uncommonWords_check ("apple apple", "banana") (findUncommonWords ("apple apple", "banana")) #guard uncommonWords_check ("apple", "apple") (findUncommonWords ("apple", "apple")) end PUncommonWordsFromTwoSentences