import Mathlib /-! # Longest Common Prefix Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". ## Constraints - 1 <= strs.length <= 200 - 0 <= strs[i].length <= 200 - strs[i] consists of only lowercase English letters if it is non-empty. ## Provided examples - `strs = ["flower", "flow", "flight"]` → `"fl"` - `strs = ["dog", "racecar", "car"]` → `""` - `strs = ["a"]` → `"a"` ## Synthesized negative examples - invalid input: `strs = []` ([structural] a predicate that admits 1 <= strs.length <= 200. empty below minimum; a predicate checking only string contents accepts it vacuously.) - invalid input: `strs = ["", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", ""]` ([structural] a predicate that admits 1 <= strs.length <= 200. 201 strings, one past the maximum; predicate ignoring array length accepts it.) - invalid input: `strs = ["ABC"]` ([structural] a predicate that admits strs[i] consists of only lowercase English letters if it is non-empty.. uppercase letter outside stated lowercase alphabet; predicate checking only lengths accepts it.) - `strs = ["flower", "flow", "flight"]` → `"f"` is wrong ([structural] the result is a common prefix but not the longest. f is common to all but shorter than fl) - `strs = ["dog", "racecar", "car"]` → `"d"` is wrong ([structural] soundness clause missing: answer need not be a common prefix of all strings. d is longer than the true empty prefix but not a common prefix) - `strs = ["a"]` → `""` is wrong ([structural] maximality stated as achievability alone. empty string is a common prefix but not longest) -/ namespace PLongestCommonPrefix abbrev Input := List String abbrev Output := String /-! ### Specification helpers -/ /-- `p` is a prefix of every string in `strs`. -/ def IsCommonPrefix (strs : List String) (p : String) : Prop := ∀ s ∈ strs, p.IsPrefix s /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 200 strings, each of length at most 200 and lowercase. -/ def isValidInput (input : Input) : Bool := decide (1 ≤ input.length) && decide (input.length ≤ 200) && input.all (fun s => decide (s.length ≤ 200)) && input.all (fun s => s.toList.all (fun c => decide ('a' ≤ c ∧ c ≤ 'z'))) /-! ### Ideal specification (P_spec) -/ /-- `result` is a common prefix of all strings in `input`, and every common prefix is a prefix of `result`. -/ def longestCommonPrefix_spec (input : Input) (result : Output) : Prop := IsCommonPrefix input result ∧ ∀ p : String, IsCommonPrefix input p → p.IsPrefix result /-! ### Decidable specification (P_check) -/ /-- Prefix of strings is decidable via its unfolding to list prefix. -/ instance stringIsPrefixDecidable (a b : String) : Decidable (a.IsPrefix b) := inferInstanceAs (Decidable (a.toList <+: b.toList)) /-- Common-prefixhood is decidable by checking each member of `strs`. -/ instance isCommonPrefixDecidable (strs : List String) (p : String) : Decidable (IsCommonPrefix strs p) := inferInstanceAs (Decidable (∀ s ∈ strs, p.IsPrefix s)) /-- All prefixes of `s`, from the empty string to `s` itself; the finite range of candidates. -/ def allPrefixes (s : String) : List String := s.toList.inits.map String.ofList /-- Executable checker for `longestCommonPrefix_spec` over the prefixes of the first string. -/ def longestCommonPrefix_check (input : Input) (result : Output) : Bool := decide (IsCommonPrefix input result) && match input with | [] => false | first :: _ => decide (∀ p ∈ allPrefixes first, IsCommonPrefix input p → p.IsPrefix result) lemma mem_allPrefixes_iff (p s : String) : p ∈ allPrefixes s ↔ p.IsPrefix s := by simp only [allPrefixes, List.mem_map, List.mem_inits, String.IsPrefix] constructor · rintro ⟨a, ha, rfl⟩ simpa only [String.toList_ofList] using ha · intro hp exact ⟨p.toList, hp, String.ofList_toList⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem longestCommonPrefix_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : longestCommonPrefix_check input result ↔ longestCommonPrefix_spec input result := by cases input with | nil => simp [isValidInput] at h | cons first rest => simp [longestCommonPrefix_check, longestCommonPrefix_spec, IsCommonPrefix, mem_allPrefixes_iff] /-! ### Implementation helpers -/ /-- Keeps the head character of the first list only when every remaining list shares that head, then recurses on all tails; the longest common prefix as a `List Char`. -/ def commonPrefixChars : List Char → List (List Char) → List Char | [], _ => [] | c :: cs, rest => if rest.all (fun l => l.head? == some c) then c :: commonPrefixChars cs (rest.map List.tail) else [] /-! ### Main algorithm (impl) -/ /-- Longest common prefix by a vertical character scan over the converted character lists, keeping characters while all strings agree. -/ def findLongestCommonPrefix (input : Input) : Output := match input with | [] => "" | first :: rest => String.ofList (commonPrefixChars first.toList (rest.map String.toList)) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findLongestCommonPrefix_correct (input : Input) (h : isValidInput input) : longestCommonPrefix_spec input (findLongestCommonPrefix input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ["flower", "flow", "flight"] #guard isValidInput ["dog", "racecar", "car"] #guard isValidInput ["a"] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput ["", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", ""]) #guard !(isValidInput ["ABC"]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard longestCommonPrefix_check ["flower", "flow", "flight"] "fl" #guard longestCommonPrefix_check ["dog", "racecar", "car"] "" #guard longestCommonPrefix_check ["a"] "a" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(longestCommonPrefix_check ["flower", "flow", "flight"] "f") #guard !(longestCommonPrefix_check ["dog", "racecar", "car"] "d") #guard !(longestCommonPrefix_check ["a"] "") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findLongestCommonPrefix ["flower", "flow", "flight"] == "fl" #guard findLongestCommonPrefix ["dog", "racecar", "car"] == "" #guard findLongestCommonPrefix ["a"] == "a" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard longestCommonPrefix_check ["flower", "flow", "flight"] (findLongestCommonPrefix ["flower", "flow", "flight"]) #guard longestCommonPrefix_check ["dog", "racecar", "car"] (findLongestCommonPrefix ["dog", "racecar", "car"]) #guard longestCommonPrefix_check ["a"] (findLongestCommonPrefix ["a"]) end PLongestCommonPrefix