import Mathlib /-! # Wildcard Matching Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where: '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). ## Constraints - 0 <= s.length, p.length <= 2000 - s contains only lowercase English letters. - p contains only lowercase English letters, '?' or '*'. ## Provided examples - `s = "aa", p = "a"` → `false` - `s = "aa", p = "*"` → `true` - `s = "cb", p = "?a"` → `false` ## Synthesized negative examples - invalid input: `s = "A", p = "?"` ([structural] a predicate that admits s contains only lowercase English letters.. uppercase in s; catches a predicate that validates p but not s) - invalid input: `s = "a", p = "A"` ([structural] a predicate that admits p contains only lowercase English letters, '?' or '*'.. uppercase in p; catches a predicate that validates s but not p) - invalid input: `s = "1", p = "?"` ([structural] a predicate that admits s contains only lowercase English letters.. digit in s; a predicate checking only p's alphabet accepts it) - `s = "aa", p = "a"` → `true` is wrong ([structural] matching is not required to cover the entire input string. a matches the first character, so a prefix reading accepts) - `s = "aa", p = "*"` → `false` is wrong ([structural] the '*' wildcard is not required to match a multi-character sequence. false is correct if '*' matches only the empty sequence) - `s = "cb", p = "?a"` → `true` is wrong ([structural] literal characters in pattern are not required to match the same letter. 'a' is allowed to match 'b' because non-'*' chars are treated as '?') -/ namespace PWildcardMatching abbrev Input := (String) × (String) abbrev Output := Bool /-! ### Specification helpers -/ /-- Concatenation of two string languages: splits of a member into a left and a right part. -/ def langConcat (L M : Set String) : Set String := {s | ∃ a ∈ L, ∃ b ∈ M, s = a ++ b} /-- Kleene star of a string language: all joins of finitely many members, empty join included. -/ def langStar (L : Set String) : Set String := {s | ∃ parts : List String, (∀ q ∈ parts, q ∈ L) ∧ s = String.join parts} /-- The one-character strings over the lowercase English alphabet. -/ def lowerSingles : Set String := {s | ∃ c : Char, 'a' ≤ c ∧ c ≤ 'z' ∧ s = String.singleton c} /-- The language denoted by a pattern seen as a list of tokens, by recursion on the tokens. -/ def patternLanguage : List Char → Set String | [] => {""} | '*' :: cs => langConcat (langStar lowerSingles) (patternLanguage cs) | '?' :: cs => langConcat lowerSingles (patternLanguage cs) | c :: cs => langConcat {String.singleton c} (patternLanguage cs) /-- The set of strings matched by pattern `p` under wildcard semantics. -/ def WildcardLanguage (p : String) : Set String := patternLanguage p.toList /-! ### Validity predicate (V) -/ /-- Valid input: both strings have length at most 2000, `s` is lowercase letters, and `p` is lowercase letters, '?' or '*'. -/ def isValidInput (input : Input) : Bool := input.1.length ≤ 2000 && input.2.length ≤ 2000 && input.1.toList.all (fun c => 'a' ≤ c && c ≤ 'z') && input.2.toList.all (fun c => ('a' ≤ c && c ≤ 'z') || c = '?' || c = '*') /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when `s` belongs to the wildcard language of `p`. -/ def isMatch_spec (input : Input) (result : Output) : Prop := result ↔ input.1 ∈ WildcardLanguage input.2 /-! ### Decidable specification (P_check) -/ /-- Whether `c` is a lowercase English letter, the spec's own range test as a Bool. -/ def isLowerChar (c : Char) : Bool := 'a' ≤ c && c ≤ 'z' /-- Whether the token list of a pattern matches the whole character list `s`, mirroring `patternLanguage` with the `langConcat` split enumerated as a cut position and `langStar lowerSingles` read as an all-lowercase check. -/ def matchTokens : List Char → List Char → Bool | [], s => s.isEmpty | '*' :: cs, s => (List.range (s.length + 1)).any fun k => (s.take k).all isLowerChar && matchTokens cs (s.drop k) | '?' :: cs, s => match s with | c :: rest => isLowerChar c && matchTokens cs rest | [] => false | c :: cs, s => match s with | d :: rest => d == c && matchTokens cs rest | [] => false /-- Executable checker for `isMatch_spec`: `result` must equal the enumerated match verdict. -/ def isMatch_check (input : Input) (result : Output) : Bool := result == matchTokens input.2.toList input.1.toList lemma join_singletons (xs : List Char) : String.join (xs.map String.singleton) = String.ofList xs := by induction xs with | nil => simp [String.join] | cons c xs ih => simp [String.join_cons, ih] lemma star_bridge (s : String) : s ∈ langStar lowerSingles ↔ s.toList.all isLowerChar = true := by constructor · rintro ⟨parts, hparts, rfl⟩ induction parts with | nil => simp [String.join] | cons q parts ih => have hq := hparts q (by simp) have hrest : ∀ r ∈ parts, r ∈ lowerSingles := by intro r hr exact hparts r (by simp [hr]) rcases hq with ⟨c, hca, hcz, rfl⟩ rw [String.join_cons, String.toList_append, List.all_append, Bool.and_eq_true] exact ⟨by simp [isLowerChar, hca, hcz], ih hrest⟩ · intro hs refine ⟨s.toList.map String.singleton, ?_, ?_⟩ · intro q hq simp only [List.mem_map] at hq rcases hq with ⟨c, hc, rfl⟩ have hc' : isLowerChar c = true := List.all_eq_true.mp hs c hc simp only [isLowerChar, Bool.and_eq_true] at hc' exact ⟨c, of_decide_eq_true hc'.1, of_decide_eq_true hc'.2, rfl⟩ · rw [join_singletons, String.ofList_toList] theorem root_of_bridges (bridge : ∀ (p : List Char) (s : String), matchTokens p s.toList = true ↔ s ∈ patternLanguage p) (input : Input) (result : Output) : isMatch_check input result ↔ isMatch_spec input result := by simp only [isMatch_check, isMatch_spec, WildcardLanguage, beq_iff_eq] rw [← bridge] cases result <;> cases matchTokens input.2.toList input.1.toList <;> simp theorem concat_lists (L M : Set String) (s : List Char) : String.ofList s ∈ langConcat L M ↔ ∃ a b : List Char, String.ofList a ∈ L ∧ String.ofList b ∈ M ∧ s = a ++ b := by constructor · rintro ⟨a, ha, b, hb, he⟩ refine ⟨a.toList, b.toList, ?_, ?_, ?_⟩ · simpa using ha · simpa using hb · simpa using congrArg String.toList he · rintro ⟨a, b, ha, hb, he⟩ refine ⟨String.ofList a, ha, String.ofList b, hb, ?_⟩ simp [he] theorem singleton_concat (c : Char) (M : Set String) (s : List Char) : String.ofList s ∈ langConcat {String.singleton c} M ↔ ∃ rest, s = c :: rest ∧ String.ofList rest ∈ M := by rw [concat_lists] simp only [Set.mem_singleton_iff, String.singleton_eq_ofList, String.ofList_inj] constructor · rintro ⟨a, b, rfl, hb, hs⟩ exact ⟨b, hs, hb⟩ · rintro ⟨b, hs, hb⟩ exact ⟨[c], b, rfl, hb, hs⟩ theorem lower_concat (M : Set String) (s : List Char) : String.ofList s ∈ langConcat lowerSingles M ↔ ∃ c rest, isLowerChar c = true ∧ s = c :: rest ∧ String.ofList rest ∈ M := by rw [concat_lists] constructor · rintro ⟨a, b, ⟨c, hc, hc', he⟩, hb, hs⟩ have he' : a = [c] := by simpa using congrArg String.toList he subst a exact ⟨c, b, by simpa [isLowerChar] using And.intro hc hc', hs, hb⟩ · rintro ⟨c, b, hc, hs, hb⟩ have hc' : 'a' ≤ c ∧ c ≤ 'z' := by simpa [isLowerChar] using hc exact ⟨[c], b, ⟨c, hc'.1, hc'.2, String.singleton_eq_ofList.symm⟩, hb, hs⟩ theorem split_cut (P Q : List Char → Prop) (s : List Char) : (∃ a b, P a ∧ Q b ∧ s = a ++ b) ↔ ∃ k, k < s.length + 1 ∧ P (s.take k) ∧ Q (s.drop k) := by constructor · rintro ⟨a, b, ha, hb, rfl⟩ exact ⟨a.length, by simp, by simpa using ha, by simpa using hb⟩ · rintro ⟨k, hk, ha, hb⟩ exact ⟨s.take k, s.drop k, ha, hb, (List.take_append_drop k s).symm⟩ theorem star_concat_of_bridge (sb : ∀ (s : String), s ∈ langStar lowerSingles ↔ s.toList.all isLowerChar = true) (M : Set String) (s : List Char) : String.ofList s ∈ langConcat (langStar lowerSingles) M ↔ ∃ k, k < s.length + 1 ∧ (s.take k).all isLowerChar = true ∧ String.ofList (s.drop k) ∈ M := by rw [concat_lists] simp only [sb, String.toList_ofList] exact split_cut _ _ s theorem match_lists_of_star (sb : ∀ (s : String), s ∈ langStar lowerSingles ↔ s.toList.all isLowerChar = true) (p s : List Char) : matchTokens p s = true ↔ String.ofList s ∈ patternLanguage p := by induction p generalizing s with | nil => simp [matchTokens, patternLanguage] | cons c cs ih => by_cases hs : c = '*' · subst c simp only [matchTokens, patternLanguage, star_concat_of_bridge sb, List.any_eq_true, List.mem_range, Bool.and_eq_true, ih] · by_cases hq : c = '?' · subst c cases s with | nil => simp only [matchTokens, patternLanguage, lower_concat] simp | cons d ds => simp only [matchTokens, patternLanguage, lower_concat, Bool.and_eq_true, ih] simp · cases s with | nil => simp only [matchTokens, patternLanguage, hs, hq, singleton_concat] simp | cons d ds => simp only [matchTokens, patternLanguage, hs, hq, singleton_concat, Bool.and_eq_true, ih] simp theorem root_of_star (sb : ∀ (s : String), s ∈ langStar lowerSingles ↔ s.toList.all isLowerChar = true) (input : Input) (result : Output) : isMatch_check input result ↔ isMatch_spec input result := by apply root_of_bridges intro p s simpa using match_lists_of_star sb p s.toList theorem match_bridge (p : List Char) (s : String) : matchTokens p s.toList = true ↔ s ∈ patternLanguage p := by simpa using match_lists_of_star star_bridge p s.toList /-- On valid input the checker accepts exactly the specified outputs. -/ theorem isMatch_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : isMatch_check input result ↔ isMatch_spec input result := by exact root_of_bridges match_bridge input result /-! ### Implementation helpers -/ /-- Whether one DP cell holds, given the last string character, the pattern token, and the left, up, and diagonal neighbour cells. -/ def matchStep (sc token : Char) (left up diag : Bool) : Bool := if token = '*' then left || (isLowerChar sc && up) else if token = '?' then isLowerChar sc && diag else if isLowerChar token then (sc == token) && diag else false /-- The (|s|+1) by (|p|+1) table whose (i, j) cell says whether the first i characters of `sArr` match the first j characters of `pArr`. -/ def buildMatchTable (sArr pArr : Array Char) : Array (Array Bool) := let m := pArr.size let row0 := (List.range (m + 1)).foldl (fun row j => if j = 0 then row.push true else row.push (pArr[j - 1]! == '*' && row[j - 1]!)) #[] (List.range sArr.size).foldl (fun table k => let prevRow := table[k]! let curRow := (List.range (m + 1)).foldl (fun row j => if j = 0 then row.push false else row.push (matchStep sArr[k]! pArr[j - 1]! row[j - 1]! prevRow[j]! prevRow[j - 1]!)) #[] table.push curRow) #[row0] /-! ### Main algorithm (impl) -/ /-- Wildcard match by dynamic programming over prefix lengths, filling an O(|s|·|p|) boolean table and reading its last cell. -/ def wildcardMatch (input : Input) : Output := let sArr := input.1.toList.toArray let pArr := input.2.toList.toArray let table := buildMatchTable sArr pArr (table[sArr.size]!)[pArr.size]! /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem wildcardMatch_correct (input : Input) (h : isValidInput input) : isMatch_spec input (wildcardMatch input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("aa", "a") #guard isValidInput ("aa", "*") #guard isValidInput ("cb", "?a") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("A", "?")) #guard !(isValidInput ("a", "A")) #guard !(isValidInput ("1", "?")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard isMatch_check ("aa", "a") false #guard isMatch_check ("aa", "*") true #guard isMatch_check ("cb", "?a") false /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(isMatch_check ("aa", "a") true) #guard !(isMatch_check ("aa", "*") false) #guard !(isMatch_check ("cb", "?a") true) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard wildcardMatch ("aa", "a") == false #guard wildcardMatch ("aa", "*") == true #guard wildcardMatch ("cb", "?a") == false /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard isMatch_check ("aa", "a") (wildcardMatch ("aa", "a")) #guard isMatch_check ("aa", "*") (wildcardMatch ("aa", "*")) #guard isMatch_check ("cb", "?a") (wildcardMatch ("cb", "?a")) end PWildcardMatching