import Mathlib /-! # Alien Dictionary There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you. You are given a list of strings words from the alien language's dictionary. Now it is claimed that the strings in words are sorted lexicographically by the rules of this new language. If this claim is incorrect, and the given arrangement of string in words cannot correspond to any order of letters, return "". Otherwise, return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there are multiple solutions, return any of them. ## Constraints - 1 <= words.length <= 100 - 1 <= words[i].length <= 100 - words[i] consists of only lowercase English letters. ## Provided examples - `words = ["wrt", "wrf", "er", "ett", "rftt"]` → `"wertf"` - `words = ["z", "x"]` → `"zx"` - `words = ["z", "x", "z"]` → `""` ## Synthesized negative examples - invalid input: `words = []` ([structural] a predicate that admits 1 <= words.length <= 100. empty dictionary where at least one word is required) - invalid input: `words = ["A"]` ([structural] a predicate that admits words[i] consists of only lowercase English letters.. uppercase letter defeats a predicate that checks only alphabetic) - invalid input: `words = ["abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghija"]` ([structural] a predicate that admits 1 <= words[i].length <= 100. one character past the maximum word length) - `words = ["wrt", "wrf", "er", "ett", "rftt"]` → `"ewrtf"` is wrong ([structural] letter order need not respect precedence from sorted words. All unique letters appear, but w must precede e.) - `words = ["z", "x"]` → `"xz"` is wrong ([structural] assumed English alphabetical order instead of order inferred from words. standard order x 1 ≤ w.length && w.length ≤ 100 && w.toList.all (fun c => 'a' ≤ c && c ≤ 'z')) /-! ### Ideal specification (P_spec) -/ /-- When `input` admits an alien order, `result` lists each occurring letter exactly once and places `x` before `y` for every precedence constraint; otherwise `result` is the empty string. -/ def alienOrder_spec (input : Input) (result : Output) : Prop := (AdmitsAlienOrder input → result.toList.Nodup ∧ (∀ c : Char, c ∈ result.toList ↔ OccursInWords c input) ∧ (∀ x y : Char, LetterPrecedes input x y → PlacesBefore result x y)) ∧ (¬ AdmitsAlienOrder input → result = "") /-! ### Decidable specification (P_check) -/ /-- Adjacent pairs of a list, `[a, b, c] ↦ [(a, b), (b, c)]`. -/ def adjacentPairs : List String → List (String × String) | a :: b :: xs => (a, b) :: adjacentPairs (b :: xs) | _ => [] /-- The letters at the first position where the two words differ, if any. -/ def firstDiffPair : List Char → List Char → Option (Char × Char) | x :: xs, y :: ys => if x = y then firstDiffPair xs ys else some (x, y) | _, _ => none /-- The precedence constraints forced by adjacent words at their first differing positions. -/ def constraintsOf (words : List String) : List (Char × Char) := (adjacentPairs words).filterMap (fun (a, b) => firstDiffPair a.toList b.toList) /-- The letters occurring in `words`, each listed once. -/ def lettersOf (words : List String) : List Char := ((words.map String.toList).flatten).dedup /-- Some adjacent pair has the next word a proper prefix of the current one. -/ def prefixViolation (words : List String) : Bool := (adjacentPairs words).any (fun (a, b) => (firstDiffPair a.toList b.toList).isNone && b.length < a.length) /-- Kahn source-removal with the given fuel: succeeds iff every remaining letter can be removed. -/ def kahnStep (remaining : List Char) (edges : List (Char × Char)) : Nat → Bool | 0 => remaining.isEmpty | n + 1 => if remaining.isEmpty then true else match remaining.find? (fun c => !edges.any (fun e => e.2 == c)) with | none => false | some c => kahnStep (remaining.erase c) (edges.filter (fun e => !(e.1 == c))) n /-- Decidable form of `AdmitsAlienOrder`: no prefix violation and an acyclic constraint graph. -/ def admitsOrder (words : List String) : Bool := !prefixViolation words && kahnStep (lettersOf words) (constraintsOf words) (lettersOf words).length /-- `x` appears at an earlier position of `s` than `y`. -/ def placesBeforeBool (s : String) (x y : Char) : Bool := s.toList.idxOf x < s.toList.idxOf y /-- Executable checker for `alienOrder_spec`. -/ def alienOrder_check (input : Input) (result : Output) : Bool := let letters := lettersOf input let admits := admitsOrder input (!admits || (result.toList.dedup == result.toList && result.toList.all (fun c => letters.contains c) && letters.all (fun c => result.toList.contains c) && (constraintsOf input).all (fun (x, y) => placesBeforeBool result x y))) && (admits || result == "") theorem firstDiffPair_mem : ∀ (l1 l2 : List Char) (x y : Char), firstDiffPair l1 l2 = some (x, y) → x ∈ l1 ∧ y ∈ l2 | [], _, _, _, h => by simp [firstDiffPair] at h | _ :: _, [], _, _, h => by simp [firstDiffPair] at h | a :: as, b :: bs, x, y, h => by rw [firstDiffPair] at h by_cases hab : a = b · rw [if_pos hab] at h obtain ⟨h1, h2⟩ := firstDiffPair_mem as bs x y h exact ⟨List.mem_cons_of_mem _ h1, List.mem_cons_of_mem _ h2⟩ · rw [if_neg hab] at h obtain ⟨rfl, rfl⟩ := Prod.mk.injEq .. ▸ Option.some.inj h exact ⟨List.mem_cons_self, List.mem_cons_self⟩ theorem firstDiffPair_iff : ∀ (l1 l2 : List Char) (x y : Char), firstDiffPair l1 l2 = some (x, y) ↔ ∃ k : Nat, (∀ j : Nat, j < k → l1[j]? = l2[j]?) ∧ l1[k]? = some x ∧ l2[k]? = some y ∧ x ≠ y | [], l2, x, y => by simp only [firstDiffPair] constructor · intro h; cases l2 <;> simp at h · rintro ⟨k, -, hk, -⟩; simp at hk | a :: as, [], x, y => by simp only [firstDiffPair] constructor · intro h; simp at h · rintro ⟨k, -, -, hk, -⟩; simp at hk | a :: as, b :: bs, x, y => by rw [firstDiffPair] by_cases hab : a = b · subst hab rw [if_pos rfl] rw [firstDiffPair_iff as bs x y] constructor · rintro ⟨k, hj, h1, h2, hne⟩ refine ⟨k + 1, ?_, by simpa using h1, by simpa using h2, hne⟩ intro j hjk cases j with | zero => simp | succ j => simpa using hj j (by omega) · rintro ⟨k, hj, h1, h2, hne⟩ cases k with | zero => simp at h1 h2; exact absurd (h1.symm.trans h2) hne | succ k => refine ⟨k, ?_, by simpa using h1, by simpa using h2, hne⟩ intro j hjk simpa using hj (j + 1) (by omega) · rw [if_neg hab] constructor · intro h obtain ⟨rfl, rfl⟩ := Prod.mk.injEq .. ▸ Option.some.inj h exact ⟨0, by simp, by simp, by simp, hab⟩ · rintro ⟨k, hj, h1, h2, hne⟩ cases k with | zero => simp at h1 h2; subst h1; subst h2; rfl | succ k => exact absurd (by simpa using hj 0 (by omega)) hab theorem adjacentPairs_mem : ∀ (ws : List String) (a b : String), (a, b) ∈ adjacentPairs ws → a ∈ ws ∧ b ∈ ws | [], _, _, h => by simp [adjacentPairs] at h | [_], _, _, h => by simp [adjacentPairs] at h | w1 :: w2 :: ws, a, b, h => by rw [adjacentPairs, List.mem_cons] at h rcases h with h | h · obtain ⟨rfl, rfl⟩ := Prod.mk.injEq .. ▸ h exact ⟨List.mem_cons_self, List.mem_cons_of_mem _ List.mem_cons_self⟩ · obtain ⟨h1, h2⟩ := adjacentPairs_mem (w2 :: ws) a b h exact ⟨List.mem_cons_of_mem _ h1, List.mem_cons_of_mem _ h2⟩ theorem mem_adjacentPairs : ∀ (ws : List String) (a b : String), (a, b) ∈ adjacentPairs ws ↔ ∃ i : Nat, ws[i]? = some a ∧ ws[i + 1]? = some b | [], a, b => by simp only [adjacentPairs, List.not_mem_nil, false_iff] rintro ⟨i, h1, -⟩; simp at h1 | [w], a, b => by simp only [adjacentPairs, List.not_mem_nil, false_iff] rintro ⟨i, -, h2⟩; simp at h2 | w1 :: w2 :: ws, a, b => by rw [adjacentPairs, List.mem_cons, mem_adjacentPairs (w2 :: ws) a b] constructor · rintro (h | ⟨i, h1, h2⟩) · obtain ⟨rfl, rfl⟩ := Prod.mk.injEq .. ▸ h exact ⟨0, by simp, by simp⟩ · exact ⟨i + 1, by simpa using h1, by simpa using h2⟩ · rintro ⟨i, h1, h2⟩ cases i with | zero => simp at h1 h2; exact Or.inl (by rw [h1, h2]) | succ i => exact Or.inr ⟨i, by simpa using h1, by simpa using h2⟩ theorem letters_mem_iff (words : List String) (c : Char) : c ∈ lettersOf words ↔ OccursInWords c words := by simp [lettersOf, OccursInWords] theorem constraints_mem_iff (words : List String) (x y : Char) : (x, y) ∈ constraintsOf words ↔ LetterPrecedes words x y := by simp only [constraintsOf, List.mem_filterMap, LetterPrecedes, FirstDiff] constructor · rintro ⟨⟨a, b⟩, hab, hfd⟩ obtain ⟨i, h1, h2⟩ := (mem_adjacentPairs words a b).mp hab exact ⟨i, a, b, h1, h2, (firstDiffPair_iff a.toList b.toList x y).mp hfd⟩ · rintro ⟨i, a, b, h1, h2, hfd⟩ exact ⟨(a, b), (mem_adjacentPairs words a b).mpr ⟨i, h1, h2⟩, (firstDiffPair_iff a.toList b.toList x y).mpr hfd⟩ theorem constraint_mem_letters (words : List String) {x y : Char} (hp : (x, y) ∈ constraintsOf words) : x ∈ lettersOf words ∧ y ∈ lettersOf words := by simp only [constraintsOf, List.mem_filterMap] at hp obtain ⟨⟨a, b⟩, hab, hfd⟩ := hp obtain ⟨hx, hy⟩ := firstDiffPair_mem a.toList b.toList x y hfd obtain ⟨ha, hb⟩ := adjacentPairs_mem words a b hab exact ⟨(letters_mem_iff words x).mpr ⟨a, ha, hx⟩, (letters_mem_iff words y).mpr ⟨b, hb, hy⟩⟩ theorem idxOf_eq_of_getElem? {l : List Char} (hnd : l.Nodup) {i : Nat} {x : Char} (hx : x ∈ l) (hi : l[i]? = some x) : l.idxOf x = i := by have h1 : l[l.idxOf x]? = some x := List.getElem?_idxOf hx have hilen : i < l.length := by by_contra hc rw [List.getElem?_eq_none (by omega)] at hi simp at hi have hplen : l.idxOf x < l.length := List.idxOf_lt_length_of_mem hx rcases lt_trichotomy (l.idxOf x) i with hc | hc | hc · exact absurd (h1.trans hi.symm) (List.nodup_iff_getElem?_ne_getElem?.mp hnd _ _ hc hilen) · exact hc · exact absurd (hi.trans h1.symm) (List.nodup_iff_getElem?_ne_getElem?.mp hnd _ _ hc hplen) theorem placesBefore_iff (s : String) (x y : Char) (hnd : s.toList.Nodup) (hx : x ∈ s.toList) (hy : y ∈ s.toList) : placesBeforeBool s x y = true ↔ PlacesBefore s x y := by simp only [placesBeforeBool, PlacesBefore, decide_eq_true_eq] constructor · intro hlt exact ⟨s.toList.idxOf x, s.toList.idxOf y, hlt, List.getElem?_idxOf hx, List.getElem?_idxOf hy⟩ · rintro ⟨i, j, hij, hi, hj⟩ rw [idxOf_eq_of_getElem? hnd hx hi, idxOf_eq_of_getElem? hnd hy hj] exact hij theorem firstDiffPair_symm : ∀ (l1 l2 : List Char) (x y : Char), firstDiffPair l1 l2 = some (x, y) → firstDiffPair l2 l1 = some (y, x) | [], l2, _, _, h => by simp [firstDiffPair] at h | _ :: _, [], _, _, h => by simp [firstDiffPair] at h | a :: as, b :: bs, x, y, h => by rw [firstDiffPair] at h by_cases hab : a = b · rw [if_pos hab] at h rw [firstDiffPair, if_pos hab.symm] exact firstDiffPair_symm as bs x y h · rw [if_neg hab] at h obtain ⟨rfl, rfl⟩ := Prod.mk.injEq .. ▸ Option.some.inj h rw [firstDiffPair, if_neg (fun hc => hab hc.symm)] theorem lex_of_firstDiffPair_some (R : Char → Char → Prop) : ∀ (l1 l2 : List Char) (x y : Char), firstDiffPair l1 l2 = some (x, y) → R x y → List.Lex R l1 l2 | [], l2, _, _, h, _ => by simp [firstDiffPair] at h | _ :: _, [], _, _, h, _ => by simp [firstDiffPair] at h | a :: as, b :: bs, x, y, h, hR => by rw [firstDiffPair] at h by_cases hab : a = b · subst hab rw [if_pos rfl] at h exact List.Lex.cons (lex_of_firstDiffPair_some R as bs x y h hR) · rw [if_neg hab] at h obtain ⟨rfl, rfl⟩ := Prod.mk.injEq .. ▸ Option.some.inj h exact List.Lex.rel hR theorem lex_of_firstDiffPair_none (R : Char → Char → Prop) : ∀ (l1 l2 : List Char), firstDiffPair l1 l2 = none → l2.length < l1.length → List.Lex R l2 l1 | [], l2, _, hlen => by simp at hlen | a :: as, [], _, _ => List.Lex.nil | a :: as, b :: bs, h, hlen => by rw [firstDiffPair] at h by_cases hab : a = b · subst hab rw [if_pos rfl] at h exact List.Lex.cons (lex_of_firstDiffPair_none R as bs h (by simpa using hlen)) · rw [if_neg hab] at h; simp at h theorem le_lex_of_firstDiffPair_none (R : Char → Char → Prop) : ∀ (l1 l2 : List Char), firstDiffPair l1 l2 = none → l1.length ≤ l2.length → l1 = l2 ∨ List.Lex R l1 l2 | [], [], _, _ => Or.inl rfl | [], _ :: _, _, _ => Or.inr List.Lex.nil | a :: as, [], _, hlen => by simp at hlen | a :: as, b :: bs, h, hlen => by rw [firstDiffPair] at h by_cases hab : a = b · subst hab rw [if_pos rfl] at h rcases le_lex_of_firstDiffPair_none R as bs h (by simpa using hlen) with heq | hlex · exact Or.inl (by rw [heq]) · exact Or.inr (List.Lex.cons hlex) · rw [if_neg hab] at h; simp at h theorem isChain_map_of_adjacent (R : List Char → List Char → Prop) : ∀ (words : List String), (∀ a b, (a, b) ∈ adjacentPairs words → R a.toList b.toList) → List.IsChain R (words.map String.toList) | [], _ => by simp | [_], _ => by simp | w1 :: w2 :: ws, hadj => by simp only [List.map_cons, List.isChain_cons_cons] refine ⟨hadj w1 w2 (by rw [adjacentPairs]; exact List.mem_cons_self), ?_⟩ have hrec := isChain_map_of_adjacent R (w2 :: ws) (fun a b hab => hadj a b (by rw [adjacentPairs]; exact List.mem_cons_of_mem _ hab)) simpa using hrec theorem adjacent_of_isChain (R : List Char → List Char → Prop) : ∀ (words : List String), List.IsChain R (words.map String.toList) → ∀ a b, (a, b) ∈ adjacentPairs words → R a.toList b.toList | [], _, _, _, hab => by simp [adjacentPairs] at hab | [_], _, _, _, hab => by simp [adjacentPairs] at hab | w1 :: w2 :: ws, hc, a, b, hab => by rw [adjacentPairs, List.mem_cons] at hab simp only [List.map_cons, List.isChain_cons_cons] at hc rcases hab with hh | hh · obtain ⟨rfl, rfl⟩ := Prod.mk.injEq .. ▸ hh exact hc.1 · exact adjacent_of_isChain R (w2 :: ws) (by simpa using hc.2) a b hh /-- Kahn source removal, recording the order in which letters are removed. -/ def kahnTopoOrder (remaining : List Char) (edges : List (Char × Char)) : Nat → List Char | 0 => [] | n + 1 => if remaining.isEmpty then [] else match remaining.find? (fun c => !edges.any (fun e => e.2 == c)) with | none => [] | some c => c :: kahnTopoOrder (remaining.erase c) (edges.filter (fun e => !(e.1 == c))) n theorem kahnStep_true_of_min (R : Char → Char → Prop) (hmin : ∀ l : List Char, l ≠ [] → ∃ m ∈ l, ∀ b ∈ l, ¬ R b m) : ∀ (n : Nat) (rem : List Char) (edges : List (Char × Char)), rem.Nodup → rem.length ≤ n → (∀ e ∈ edges, e.1 ∈ rem) → (∀ e ∈ edges, R e.1 e.2) → kahnStep rem edges n = true := by intro n induction n with | zero => intro rem edges _ hlen _ _ have hrem : rem = [] := List.eq_nil_of_length_eq_zero (by omega) subst hrem rfl | succ n ih => intro rem edges hnd hlen hsrc hR rw [kahnStep] by_cases hemp : rem.isEmpty = true · rw [if_pos hemp] · rw [if_neg hemp] have hne : rem ≠ [] := by simpa using hemp obtain ⟨m, hm, hmmin⟩ := hmin rem hne have hpred : (fun c => !edges.any (fun e => e.2 == c)) m = true := by simp only [Bool.not_eq_true', List.any_eq_false] rintro e he hbe have h2 : e.2 = m := by simpa using hbe exact hmmin e.1 (hsrc e he) (h2 ▸ hR e he) have hfind : rem.find? (fun c => !edges.any (fun e => e.2 == c)) ≠ none := by intro hc exact absurd hpred (by simpa using List.find?_eq_none.mp hc m hm) cases hf : rem.find? (fun c => !edges.any (fun e => e.2 == c)) with | none => exact absurd hf hfind | some c => have hcm : c ∈ rem := List.mem_of_find?_eq_some hf refine ih (rem.erase c) (edges.filter (fun e => !(e.1 == c))) (hnd.erase c) ?_ ?_ ?_ · rw [List.length_erase_of_mem hcm] have : 0 < rem.length := List.length_pos_of_mem hcm omega · intro e he rw [List.mem_filter] at he have hne1 : e.1 ≠ c := by simpa using he.2 exact (List.mem_erase_of_ne hne1).mpr (hsrc e he.1) · intro e he rw [List.mem_filter] at he exact hR e he.1 theorem kahnOrder_spec : ∀ (n : Nat) (rem : List Char) (edges : List (Char × Char)), rem.Nodup → rem.length ≤ n → (∀ e ∈ edges, e.1 ∈ rem ∧ e.2 ∈ rem) → kahnStep rem edges n = true → (kahnTopoOrder rem edges n).Nodup ∧ (∀ c, c ∈ kahnTopoOrder rem edges n ↔ c ∈ rem) ∧ (∀ e ∈ edges, (kahnTopoOrder rem edges n).idxOf e.1 < (kahnTopoOrder rem edges n).idxOf e.2) := by intro n induction n with | zero => intro rem edges _ hlen hinv _ have hrem : rem = [] := List.eq_nil_of_length_eq_zero (by omega) subst hrem rw [kahnTopoOrder] exact ⟨List.nodup_nil, fun c => Iff.rfl, fun e he => absurd (hinv e he).1 (by simp)⟩ | succ n ih => intro rem edges hnd hlen hinv hk rw [kahnStep] at hk rw [kahnTopoOrder] by_cases hemp : rem.isEmpty = true · have hrem : rem = [] := by simpa using hemp subst hrem rw [if_pos hemp] exact ⟨List.nodup_nil, fun c => Iff.rfl, fun e he => absurd (hinv e he).1 (by simp)⟩ · rw [if_neg hemp] at hk ⊢ cases hf : rem.find? (fun c => !edges.any (fun e => e.2 == c)) with | none => rw [hf] at hk; simp at hk | some c => rw [hf] at hk dsimp only at hk ⊢ have hcm : c ∈ rem := List.mem_of_find?_eq_some hf have hcsrc : ∀ e ∈ edges, e.2 ≠ c := by have := List.find?_some hf simp only [Bool.not_eq_true', List.any_eq_false] at this intro e he hc2 exact this e he (by simp [hc2]) have hlen' : (rem.erase c).length ≤ n := by rw [List.length_erase_of_mem hcm] have : 0 < rem.length := List.length_pos_of_mem hcm omega have hinv' : ∀ e ∈ edges.filter (fun e => !(e.1 == c)), e.1 ∈ rem.erase c ∧ e.2 ∈ rem.erase c := by intro e he rw [List.mem_filter] at he have hne1 : e.1 ≠ c := by simpa using he.2 exact ⟨(List.mem_erase_of_ne hne1).mpr (hinv e he.1).1, (List.mem_erase_of_ne (hcsrc e he.1)).mpr (hinv e he.1).2⟩ obtain ⟨hnd', hmem', hord'⟩ := ih (rem.erase c) (edges.filter (fun e => !(e.1 == c))) (hnd.erase c) hlen' hinv' hk set O' := kahnTopoOrder (rem.erase c) (edges.filter (fun e => !(e.1 == c))) n with hO' have hcO' : c ∉ O' := fun hc => (hnd.not_mem_erase) ((hmem' c).mp hc) refine ⟨List.nodup_cons.mpr ⟨hcO', hnd'⟩, ?_, ?_⟩ · intro d rw [List.mem_cons, hmem' d] constructor · rintro (rfl | hd) · exact hcm · exact List.mem_of_mem_erase hd · intro hd by_cases hdc : d = c · exact Or.inl hdc · exact Or.inr ((List.mem_erase_of_ne hdc).mpr hd) · intro e he have h2 : e.2 ≠ c := hcsrc e he by_cases h1 : e.1 = c · rw [h1] rw [List.idxOf_cons, List.idxOf_cons] simp only [cond_eq_ite, beq_iff_eq, if_neg (fun hcc : c = e.2 => h2 hcc.symm)] simp · have hef : e ∈ edges.filter (fun e => !(e.1 == c)) := by rw [List.mem_filter] exact ⟨he, by simp [h1]⟩ have := hord' e hef rw [List.idxOf_cons, List.idxOf_cons] simp only [cond_eq_ite, beq_iff_eq, if_neg (fun hcc : c = e.1 => h1 hcc.symm), if_neg (fun hcc : c = e.2 => h2 hcc.symm)] omega /-- Position key of a letter in a topological ordering, paired with the letter itself. -/ def rankKey (O : List Char) (c : Char) : Lex (Nat × Char) := toLex (O.idxOf c, c) /-- The strict order on letters induced by a topological ordering. -/ def rankRel (O : List Char) (a b : Char) : Prop := rankKey O a < rankKey O b theorem admits_iff (words : List String) : admitsOrder words = true ↔ AdmitsAlienOrder words := by constructor · intro hadm rw [admitsOrder, Bool.and_eq_true, Bool.not_eq_true'] at hadm obtain ⟨hpv, hk⟩ := hadm have hLnd : (lettersOf words).Nodup := List.nodup_dedup _ have hinv : ∀ e ∈ constraintsOf words, e.1 ∈ lettersOf words ∧ e.2 ∈ lettersOf words := by intro e he exact constraint_mem_letters words (x := e.1) (y := e.2) (by simpa using he) obtain ⟨hOnd, hOmem, hOord⟩ := kahnOrder_spec (lettersOf words).length (lettersOf words) (constraintsOf words) hLnd le_rfl hinv hk set O := kahnTopoOrder (lettersOf words) (constraintsOf words) (lettersOf words).length with hOdef have hinj : Function.Injective (rankKey O) := by intro a b hab simpa [rankKey] using congrArg (fun p => (ofLex p).2) hab haveI : IsTrans Char (rankRel O) := ⟨fun a b c hab hbc => lt_trans hab hbc⟩ haveI : Std.Irrefl (rankRel O) := ⟨fun a => lt_irrefl (rankKey O a)⟩ haveI : Std.Trichotomous (rankRel O) := ⟨fun a b hab hba => by rcases lt_trichotomy (rankKey O a) (rankKey O b) with hh | hh | hh · exact absurd hh hab · exact hinj hh · exact absurd hh hba⟩ haveI : IsStrictTotalOrder Char (rankRel O) := { } letI : DecidableRel (rankRel O) := fun a b => Classical.dec _ letI instA : LinearOrder Char := linearOrderOfSTO (rankRel O) refine ⟨instA, ?_⟩ rw [List.sortedLE_iff_isChain] refine isChain_map_of_adjacent _ words ?_ intro a b hab obtain hfd | ⟨x, y, hfd⟩ : firstDiffPair a.toList b.toList = none ∨ ∃ x y, firstDiffPair a.toList b.toList = some (x, y) := by cases hh : firstDiffPair a.toList b.toList with | none => exact Or.inl rfl | some p => exact Or.inr ⟨p.1, p.2, rfl⟩ · have hlen : a.toList.length ≤ b.toList.length := by rw [prefixViolation, List.any_eq_false] at hpv have hx := hpv (a, b) hab simp only [Bool.and_eq_true, Option.isNone_iff_eq_none, decide_eq_true_eq, not_and] at hx have hy := hx (by simpa using hfd) rw [String.length_toList, String.length_toList] omega rcases le_lex_of_firstDiffPair_none (rankRel O) a.toList b.toList hfd hlen with heq | hlex · exact le_of_eq heq · exact le_of_lt hlex · have hmemE : (x, y) ∈ constraintsOf words := by simp only [constraintsOf, List.mem_filterMap] exact ⟨(a, b), hab, hfd⟩ have hxy : O.idxOf x < O.idxOf y := hOord (x, y) hmemE have hlt : rankRel O x y := Prod.Lex.toLex_lt_toLex.mpr (Or.inl hxy) refine le_of_lt ?_ exact lex_of_firstDiffPair_some (rankRel O) a.toList b.toList x y hfd hlt · rintro ⟨inst, hsorted⟩ letI ltB : LT Char := inst.toLT have hadj : ∀ a b, (a, b) ∈ adjacentPairs words → a.toList ≤ b.toList := adjacent_of_isChain (· ≤ ·) words (List.sortedLE_iff_isChain.mp hsorted) have hpv : prefixViolation words = false := by rw [prefixViolation, List.any_eq_false] rintro ⟨a, b⟩ hab simp only [Bool.and_eq_true, Option.isNone_iff_eq_none, decide_eq_true_eq, not_and] intro hnone hlt have hlex : List.Lex (· < ·) b.toList a.toList := lex_of_firstDiffPair_none (· < ·) a.toList b.toList hnone (by rw [String.length_toList, String.length_toList]; omega) exact absurd (hadj a b hab) (not_le.mpr hlex) have hRlt : ∀ e ∈ constraintsOf words, e.1 < e.2 := by rintro ⟨x, y⟩ he simp only [constraintsOf, List.mem_filterMap] at he obtain ⟨⟨a, b⟩, hab, hfd⟩ := he have hle := hadj a b hab by_contra hc obtain ⟨_, -, -, -, hne⟩ := (firstDiffPair_iff a.toList b.toList x y).mp hfd have hyx : y < x := lt_of_le_of_ne (not_lt.mp hc) (Ne.symm hne) exact absurd hle (not_le.mpr (lex_of_firstDiffPair_some (· < ·) b.toList a.toList y x (firstDiffPair_symm a.toList b.toList x y hfd) hyx)) rw [admitsOrder, Bool.and_eq_true, Bool.not_eq_true', hpv] refine ⟨rfl, kahnStep_true_of_min (· < ·) ?_ _ _ _ (List.nodup_dedup _) le_rfl (fun e he => (constraint_mem_letters words (x := e.1) (y := e.2) (by simpa using he)).1) hRlt⟩ intro l hl obtain ⟨m, hm, hmin⟩ := Finset.exists_min_image l.toFinset id (by rcases l with _ | ⟨a, t⟩ · exact absurd rfl hl · exact ⟨a, by simp⟩) exact ⟨m, by simpa using hm, fun b hb => not_lt.mpr (by simpa using hmin b (by simpa using hb))⟩ theorem check_true_eq (input : Input) (result : Output) (hadm : admitsOrder input = true) : alienOrder_check input result = true ↔ (result.toList.Nodup ∧ (∀ c : Char, c ∈ result.toList ↔ c ∈ lettersOf input) ∧ ∀ p ∈ constraintsOf input, placesBeforeBool result p.1 p.2 = true) := by simp only [alienOrder_check, hadm, Bool.not_true, Bool.false_or, Bool.true_or, Bool.and_true, Bool.and_eq_true, beq_iff_eq, List.all_eq_true, List.contains_iff_mem, List.dedup_eq_self] constructor · rintro ⟨⟨hnd, hsub⟩, hsup⟩ exact ⟨hnd.1, fun c => ⟨fun hm => hnd.2 c hm, fun hm => hsub c hm⟩, hsup⟩ · rintro ⟨hnd, hmem, hc⟩ exact ⟨⟨⟨hnd, fun c hm => (hmem c).mp hm⟩, fun c hm => (hmem c).mpr hm⟩, hc⟩ theorem check_false_eq (input : Input) (result : Output) (hadm : admitsOrder input = false) : alienOrder_check input result = true ↔ result = "" := by simp only [alienOrder_check, hadm, Bool.not_false, Bool.true_or, Bool.false_or, Bool.true_and, beq_iff_eq] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem alienOrder_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : alienOrder_check input result ↔ alienOrder_spec input result := by by_cases hadm : admitsOrder input = true · have hA : AdmitsAlienOrder input := (admits_iff input).mp hadm rw [check_true_eq input result hadm, alienOrder_spec] constructor · rintro ⟨hnd, hmem, hcons⟩ refine ⟨fun _ => ⟨hnd, fun c => (hmem c).trans (letters_mem_iff input c), ?_⟩, fun hna => absurd hA hna⟩ intro x y hlp have hxy : (x, y) ∈ constraintsOf input := (constraints_mem_iff input x y).mpr hlp obtain ⟨hlx, hly⟩ := constraint_mem_letters input hxy exact (placesBefore_iff result x y hnd ((hmem x).mpr hlx) ((hmem y).mpr hly)).mp (hcons (x, y) hxy) · rintro ⟨hgood, -⟩ obtain ⟨hnd, hmem, hpb⟩ := hgood hA refine ⟨hnd, fun c => (hmem c).trans (letters_mem_iff input c).symm, ?_⟩ rintro ⟨x, y⟩ hp obtain ⟨hlx, hly⟩ := constraint_mem_letters input hp exact (placesBefore_iff result x y hnd ((hmem x).mpr ((letters_mem_iff input x).mp hlx)) ((hmem y).mpr ((letters_mem_iff input y).mp hly))).mpr (hpb x y ((constraints_mem_iff input x y).mp hp)) · have hadmf : admitsOrder input = false := Bool.eq_false_iff.mpr hadm have hA : ¬ AdmitsAlienOrder input := fun hx => hadm ((admits_iff input).mpr hx) rw [check_false_eq input result hadmf, alienOrder_spec] constructor · intro hr exact ⟨fun hx => absurd hx hA, fun _ => hr⟩ · rintro ⟨-, h2⟩ exact h2 hA /-! ### Implementation helpers -/ /-- Kahn source-removal returning the removal order, or `none` if it stalls. -/ def kahnOrder (remaining : List Char) (edges : List (Char × Char)) : Nat → Option (List Char) | 0 => if remaining.isEmpty then some [] else none | n + 1 => if remaining.isEmpty then some [] else match remaining.find? (fun c => !edges.any (fun e => e.2 == c)) with | none => none | some c => match kahnOrder (remaining.erase c) (edges.filter (fun e => !(e.1 == c))) n with | none => none | some rest => some (c :: rest) /-! ### Main algorithm (impl) -/ /-- Kahn source-removal over the remaining letters, recursing on the shrinking letter list, or `none` if it stalls before every letter is placed. -/ def kahnLoop (remaining : List Char) (edges : List (Char × Char)) : Option (List Char) := if remaining.isEmpty then some [] else match h : remaining.find? (fun c => !edges.any (fun e => e.2 == c)) with | none => none | some c => match kahnLoop (remaining.erase c) (edges.filter (fun e => !(e.1 == c))) with | none => none | some rest => some (c :: rest) termination_by remaining.length decreasing_by have hmem : c ∈ remaining := List.mem_of_find?_eq_some h have hlen := List.length_erase_add_one hmem omega /-- Topological ordering by Kahn source-removal over first-difference constraints. -/ def findAlienOrder (input : Input) : Output := if prefixViolation input then "" else let letters := lettersOf input match kahnLoop letters (constraintsOf input) with | none => "" | some cs => String.mk cs /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findAlienOrder_correct (input : Input) (h : isValidInput input) : alienOrder_spec input (findAlienOrder input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ["wrt", "wrf", "er", "ett", "rftt"] #guard isValidInput ["z", "x"] #guard isValidInput ["z", "x", "z"] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput ["A"]) #guard !(isValidInput ["abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghija"]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard alienOrder_check ["wrt", "wrf", "er", "ett", "rftt"] "wertf" #guard alienOrder_check ["z", "x"] "zx" #guard alienOrder_check ["z", "x", "z"] "" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(alienOrder_check ["wrt", "wrf", "er", "ett", "rftt"] "ewrtf") #guard !(alienOrder_check ["z", "x"] "xz") #guard !(alienOrder_check ["z", "x", "z"] "zx") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findAlienOrder ["wrt", "wrf", "er", "ett", "rftt"] == "wertf" #guard findAlienOrder ["z", "x"] == "zx" #guard findAlienOrder ["z", "x", "z"] == "" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard alienOrder_check ["wrt", "wrf", "er", "ett", "rftt"] (findAlienOrder ["wrt", "wrf", "er", "ett", "rftt"]) #guard alienOrder_check ["z", "x"] (findAlienOrder ["z", "x"]) #guard alienOrder_check ["z", "x", "z"] (findAlienOrder ["z", "x", "z"]) end PAlienDictionary