import Mathlib /-! # Group Anagrams Given an array of strings strs, group the anagrams together. You can return the answer in any order. ## Constraints - 1 <= strs.length <= 10^4 - 0 <= strs[i].length <= 100 - strs[i] consists of lowercase English letters. ## Provided examples - `strs = ["eat", "tea", "tan", "ate", "nat", "bat"]` → `[["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]` - `strs = [""]` → `[[""]]` - `strs = ["a"]` → `[["a"]]` ## Synthesized negative examples - invalid input: `strs = []` ([structural] a predicate that admits 1 <= strs.length <= 10^4. empty array below the stated minimum) - invalid input: `strs = ["aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"]` ([structural] a predicate that admits 0 <= strs[i].length <= 100. string length exceeds the stated maximum) - invalid input: `strs = ["A"]` ([structural] a predicate that admits strs[i] consists of lowercase English letters.. uppercase letter passes predicates that accept any letter) - `strs = ["eat", "tea", "tan", "ate", "nat", "bat"]` → `[["eat"], ["tea"], ["tan"], ["ate"], ["nat"], ["bat"]]` is wrong ([structural] does not require anagram classes to be merged. singleton groups split anagram classes) - `strs = [""]` → `[[], [""]]` is wrong ([structural] empty groups are not rejected. includes an empty group; coverage and anagrams still hold) - `strs = ["a"]` → `[]` is wrong ([structural] nothing requires every input string to appear in some group. empty output excludes 'a'; no group contains it) -/ namespace PGroupAnagrams abbrev Input := List String abbrev Output := List (List String) /-! ### Specification helpers -/ /-- Two strings are anagrams when their character lists are permutations. -/ def IsAnagram (s t : String) : Prop := s.toList.Perm t.toList /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty list of at most 10000 strings, each of length at most 100 and containing only lowercase English letters. -/ def isValidInput (input : Input) : Bool := decide (1 ≤ input.length) && decide (input.length ≤ 10 ^ 4) && input.all (fun s => decide (0 ≤ s.length) && decide (s.length ≤ 100) && s.toList.all (fun c => decide ('a' ≤ c ∧ c ≤ 'z'))) /-! ### Ideal specification (P_spec) -/ /-- `result` partitions `input` into nonempty maximal anagram classes, with group order irrelevant. -/ def groupAnagrams_spec (input : Input) (result : Output) : Prop := (result.flatten.Perm input ∧ ∀ group ∈ result, group ≠ []) ∧ ((∀ group ∈ result, ∀ s ∈ group, ∀ t ∈ group, IsAnagram s t) ∧ result.Pairwise (fun left right => ∀ s ∈ left, ∀ t ∈ right, ¬ IsAnagram s t)) /-! ### Decidable specification (P_check) -/ /-- Anagrams are decided as permutations of the character lists. -/ instance instDecidableIsAnagram (s t : String) : Decidable (IsAnagram s t) := inferInstanceAs (Decidable (s.toList.Perm t.toList)) /-- Every earlier group is anagram-separated from every later group. -/ def separatedAnagramGroups : Output → Bool | [] => true | left :: rest => rest.all (fun right => left.all (fun s => right.all (fun t => decide (¬ IsAnagram s t)))) && separatedAnagramGroups rest /-- Executable checker for `groupAnagrams_spec`: the specification itself, decided. -/ def groupAnagrams_check (input : Input) (result : Output) : Bool := decide (result.flatten.Perm input) && result.all (fun group => decide (group ≠ [])) && result.all (fun group => group.all (fun s => group.all (fun t => decide (IsAnagram s t)))) && separatedAnagramGroups result theorem separatedAnagramGroups_iff_pairwise (result : Output) : separatedAnagramGroups result = true ↔ result.Pairwise (fun left right => ∀ s ∈ left, ∀ t ∈ right, ¬ IsAnagram s t) := by induction result with | nil => simp [separatedAnagramGroups] | cons left rest ih => simp [separatedAnagramGroups, List.pairwise_cons, ih] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem groupAnagrams_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : groupAnagrams_check input result ↔ groupAnagrams_spec input result := by unfold groupAnagrams_check groupAnagrams_spec simp only [Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, separatedAnagramGroups_iff_pairwise, and_assoc] /-! ### Implementation helpers -/ /-- Increments the `idx`-th counter of a count vector. -/ def bumpCount : List Nat → Nat → List Nat | [], _ => [] | x :: xs, 0 => (x + 1) :: xs | x :: xs, n + 1 => x :: bumpCount xs n /-- Lexicographic order on character lists. -/ def charListLe : List Char → List Char → Bool | [], _ => true | _ :: _, [] => false | x :: xs, y :: ys => if x.toNat < y.toNat then true else if y.toNat < x.toNat then false else charListLe xs ys /-- Lexicographic order on strings. -/ def stringLe (a b : String) : Bool := charListLe a.toList b.toList /-- Inserts a string into a group kept in lexicographic order. -/ def insertSorted (s : String) : List String → List String | [] => [s] | h :: t => if stringLe s h then s :: h :: t else h :: insertSorted s t /-- Returns the canonical 26-entry lowercase count vector for a string. -/ def countKey (s : String) : List Nat := s.toList.foldl (fun counts c => if decide (97 ≤ c.toNat ∧ c.toNat ≤ 122) then bumpCount counts (c.toNat - 97) else counts) (List.replicate 26 0) /-- Adds one string under its count key, creating a new front group when absent. -/ def insertByKey (key : List Nat) (s : String) (entries : List (List Nat × List String)) : List (List Nat × List String) := if entries.any (fun entry => entry.1 == key) then entries.map (fun entry => if entry.1 == key then (entry.1, insertSorted s entry.2) else entry) else (key, [s]) :: entries /-! ### Main algorithm (impl) -/ /-- Groups anagrams by canonical lowercase count keys. -/ def collectAnagramGroups (input : Input) : Output := (input.foldl (fun entries s => insertByKey (countKey s) s entries) []).map Prod.snd /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem collectAnagramGroups_correct (input : Input) (h : isValidInput input) : groupAnagrams_spec input (collectAnagramGroups input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ["eat", "tea", "tan", "ate", "nat", "bat"] #guard isValidInput [""] #guard isValidInput ["a"] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput ["aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"]) #guard !(isValidInput ["A"]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard groupAnagrams_check ["eat", "tea", "tan", "ate", "nat", "bat"] [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]] #guard groupAnagrams_check [""] [[""]] #guard groupAnagrams_check ["a"] [["a"]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(groupAnagrams_check ["eat", "tea", "tan", "ate", "nat", "bat"] [["eat"], ["tea"], ["tan"], ["ate"], ["nat"], ["bat"]]) #guard !(groupAnagrams_check [""] [[], [""]]) #guard !(groupAnagrams_check ["a"] []) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard collectAnagramGroups ["eat", "tea", "tan", "ate", "nat", "bat"] == [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]] #guard collectAnagramGroups [""] == [[""]] #guard collectAnagramGroups ["a"] == [["a"]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard groupAnagrams_check ["eat", "tea", "tan", "ate", "nat", "bat"] (collectAnagramGroups ["eat", "tea", "tan", "ate", "nat", "bat"]) #guard groupAnagrams_check [""] (collectAnagramGroups [""]) #guard groupAnagrams_check ["a"] (collectAnagramGroups ["a"]) end PGroupAnagrams