import Mathlib /-! # Letter Combinations Of A Phone Number Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. ## Constraints - 0 <= digits.length <= 4 - digits[i] is a digit in the range ['2', '9']. ## Provided examples - `digits = "23"` → `["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]` - `digits = ""` → `[]` - `digits = "2"` → `["a", "b", "c"]` ## Synthesized negative examples - invalid input: `digits = "22222"` ([structural] a predicate that admits 0 <= digits.length <= 4. one past the length ceiling; catches a predicate that omits the length check) - invalid input: `digits = "0"` ([structural] a predicate that admits digits[i] is a digit in the range ['2', '9'].. a digit outside 2-9; a predicate checking isdigit() accepts it) - invalid input: `digits = " "` ([structural] a predicate that admits digits[i] is a digit in the range ['2', '9'].. whitespace is not a digit; a predicate only rejecting letters passes it) - `digits = "23"` → `["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf", "da"]` is wrong ([structural] digit order ignored; first character need not come from the first digit. da valid if digit order can be swapped) - `digits = ""` → `[""]` is wrong ([structural] nothing requires the output to be empty for empty input. returns the empty string as the only combination) - `digits = "2"` → `["a", "b", "c", "d"]` is wrong ([structural] letters are not restricted to the digit's mapped letters. d is not on button 2; all true combinations still appear) -/ namespace PLetterCombinationsOfAPhoneNumber abbrev Input := String abbrev Output := List String /-! ### Specification helpers -/ /-- The telephone keypad mapping: digits '2'–'9' to their letters, empty otherwise. -/ def digitToLetters (c : Char) : String := if c = '2' then "abc" else if c = '3' then "def" else if c = '4' then "ghi" else if c = '5' then "jkl" else if c = '6' then "mno" else if c = '7' then "pqrs" else if c = '8' then "tuv" else if c = '9' then "wxyz" else "" /-- `s` is a letter combination of `digits`: `digits` is non-empty, the lengths agree, and each character of `s` comes from the keypad image of the matching digit. -/ def IsPhoneCombination (digits s : String) : Prop := digits ≠ "" ∧ s.toList.length = digits.toList.length ∧ ∀ i : Nat, ∀ h₁ : i < digits.toList.length, ∀ h₂ : i < s.toList.length, s.toList[i]'h₂ ∈ (digitToLetters (digits.toList[i]'h₁)).toList /-! ### Validity predicate (V) -/ /-- Valid input: a string of at most four characters, each a digit from '2' to '9'. -/ def isValidInput (input : Input) : Bool := decide (input.length ≤ 4) && input.toList.all (fun c => decide ('2' ≤ c) && decide (c ≤ '9')) /-! ### Ideal specification (P_spec) -/ /-- `result` lists exactly the phone letter combinations of `input`: it has no duplicates, every element is a combination, and every combination appears. -/ def letterCombinations_spec (input : Input) (result : Output) : Prop := (result.Nodup ∧ ∀ s ∈ result, IsPhoneCombination input s) ∧ ∀ s : String, IsPhoneCombination input s → s ∈ result /-! ### Decidable specification (P_check) -/ /-- The letter combinations of a nonempty digit string: the sections of the per-digit keypad letter lists, as strings. -/ def allCombinations (digits : String) : List String := if digits = "" then [] else (digits.toList.map (fun c => (digitToLetters c).toList)).sections.map String.ofList /-- Bool form of `IsPhoneCombination`: non-empty digits, equal lengths, each character in its digit's keypad image. -/ def isPhoneCombinationBool (digits s : String) : Bool := !(digits == "") && (s.toList.length == digits.toList.length) && (digits.toList.zip s.toList).all (fun (d, c) => (digitToLetters d).toList.contains c) /-- Executable checker for `letterCombinations_spec` over the finite candidate list. -/ def letterCombinations_check (input : Input) (result : Output) : Bool := decide result.Nodup && result.all (fun s => isPhoneCombinationBool input s) && (allCombinations input).all (fun s => result.contains s) theorem root_of_bridges (hb : ∀ d s, isPhoneCombinationBool d s = true ↔ IsPhoneCombination d s) (hm : ∀ d s, s ∈ allCombinations d ↔ IsPhoneCombination d s) (input : Input) (result : Output) : letterCombinations_check input result ↔ letterCombinations_spec input result := by simp only [letterCombinations_check, letterCombinations_spec, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, List.contains_iff_mem, hb, hm] theorem spec_iff_rel (d s : String) : IsPhoneCombination d s ↔ d ≠ "" ∧ List.Forall₂ (fun c a => a ∈ (digitToLetters c).toList) d.toList s.toList := by simp only [IsPhoneCombination, List.forall₂_iff_get, List.get_eq_getElem] grind only [] theorem bool_bridge (d s : String) : isPhoneCombinationBool d s = true ↔ IsPhoneCombination d s := by rw [spec_iff_rel, List.forall₂_iff_zip] simp only [isPhoneCombinationBool, Bool.and_eq_true, Bool.not_eq_true', beq_iff_eq, beq_eq_false_iff_ne, List.all_eq_true, List.contains_iff_mem] simp only [Prod.forall] grind only [] theorem mem_bridge (d s : String) : s ∈ allCombinations d ↔ IsPhoneCombination d s := by by_cases hd : d = "" · simp [allCombinations, hd, IsPhoneCombination] · have hs : (∃ l ∈ (d.toList.map (fun c => (digitToLetters c).toList)).sections, String.ofList l = s) ↔ s.toList ∈ (d.toList.map (fun c => (digitToLetters c).toList)).sections := by constructor · rintro ⟨l, hl, rfl⟩ simpa using hl · intro hl exact ⟨s.toList, hl, by simp⟩ simp only [allCombinations, if_neg hd, List.mem_map] rw [hs, List.mem_sections, List.forall₂_map_right_iff, List.forall₂_iff_get] simp only [IsPhoneCombination, hd, not_false_eq_true, true_and, List.get_eq_getElem] grind only [] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem letterCombinations_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : letterCombinations_check input result ↔ letterCombinations_spec input result := by exact root_of_bridges bool_bridge mem_bridge input result /-! ### Main algorithm (impl) -/ /-- Recursive helper: the letter combinations of a list of digit characters, in the frozen order — the first digit varies slowest, its letters in keypad order. -/ def combosOfDigitList : List Char → List String | [] => [""] | c :: cs => (digitToLetters c).toList.flatMap fun ch => (combosOfDigitList cs).map fun s => String.ofList (ch :: s.toList) /-- All phone letter combinations by the frozen enumeration: per-digit keypad letters and list sections. -/ def phoneNumberLetterCombinations (input : Input) : Output := if input = "" then [] else combosOfDigitList input.toList /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem phoneNumberLetterCombinations_correct (input : Input) (h : isValidInput input) : letterCombinations_spec input (phoneNumberLetterCombinations input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "23" #guard isValidInput "" #guard isValidInput "2" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "22222") #guard !(isValidInput "0") #guard !(isValidInput " ") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard letterCombinations_check "23" ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] #guard letterCombinations_check "" [] #guard letterCombinations_check "2" ["a", "b", "c"] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(letterCombinations_check "23" ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf", "da"]) #guard !(letterCombinations_check "" [""]) #guard !(letterCombinations_check "2" ["a", "b", "c", "d"]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard phoneNumberLetterCombinations "23" == ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] #guard phoneNumberLetterCombinations "" == [] #guard phoneNumberLetterCombinations "2" == ["a", "b", "c"] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard letterCombinations_check "23" (phoneNumberLetterCombinations "23") #guard letterCombinations_check "" (phoneNumberLetterCombinations "") #guard letterCombinations_check "2" (phoneNumberLetterCombinations "2") end PLetterCombinationsOfAPhoneNumber