import Mathlib /-! # String Transforms Into Another String Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conversions. In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character. Return true if and only if you can transform str1 into str2. ## Constraints - 1 <= str1.length == str2.length <= 10^4 - str1 and str2 contain only lowercase English letters. ## Provided examples - `str1 = "aabcc", str2 = "ccdee"` → `true` - `str1 = "aaa", str2 = "aaa"` → `true` - `str1 = "abc", str2 = "abc"` → `true` ## Synthesized negative examples - invalid input: `str1 = "", str2 = ""` ([structural] a predicate that admits 1 <= str1.length == str2.length <= 10^4. empty strings; defeats a predicate forgetting the lower length bound) - invalid input: `str1 = "a", str2 = "aa"` ([structural] a predicate that admits 1 <= str1.length == str2.length <= 10^4. lengths differ but each legal; defeats equality check omitted) - invalid input: `str1 = "a", str2 = "A"` ([structural] a predicate that admits str1 and str2 contain only lowercase English letters.. uppercase in str2; defeats predicate checking only str1's alphabet) - `str1 = "aabcc", str2 = "ccdee"` → `false` is wrong ([structural] spec forgot conversions may introduce letters not in str1. d and e absent from str1 but allowed) - `str1 = "aaa", str2 = "aaa"` → `false` is wrong ([structural] unattainable does not fit a decision problem; a reading that keeps only the only-if half accepts false. false although zero conversions reach str2) - `str1 = "abc", str2 = "abc"` → `false` is wrong ([structural] zero conversions are not allowed; exactly one conversion is required. equal strings need zero; one conversion changes the string) -/ namespace PStringTransformsIntoAnotherString abbrev Input := (String) × (String) abbrev Output := Bool /-! ### Specification helpers -/ /-- One conversion step: `t` is `s` with every occurrence of the lowercase letter `c` replaced by the distinct lowercase letter `d`. -/ def step (s t : String) : Prop := ∃ c d : Char, 'a' ≤ c ∧ c ≤ 'z' ∧ 'a' ≤ d ∧ d ≤ 'z' ∧ c ≠ d ∧ t.toList = s.toList.map (fun x => if x = c then d else x) /-- `CanTransform s t`: `t` is reachable from `s` by zero or more conversion steps. -/ def CanTransform (s t : String) : Prop := Relation.ReflTransGen step s t /-! ### Validity predicate (V) -/ /-- Valid input: nonempty equal-length strings of at most 10^4 lowercase English letters. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length == input.2.length && input.2.length ≤ 10^4 && input.1.toList.all (fun c => 'a' ≤ c && c ≤ 'z') && input.2.toList.all (fun c => 'a' ≤ c && c ≤ 'z') /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when `str1` can be transformed into `str2` by zero or more conversions. -/ def canTransform_spec (input : Input) (result : Output) : Prop := result ↔ CanTransform input.1 input.2 /-! ### Decidable specification (P_check) -/ /-- Equal source characters pair with equal target characters under the position pairing of `s` and `t`. -/ def consistentPairing (s t : String) : Bool := let pairs := s.toList.zip t.toList pairs.all fun p => pairs.all fun q => !(p.1 == q.1) || (p.2 == q.2) /-- The strings are already equal, or `t` leaves at least one of the 26 lowercase letters unused. -/ def hasSpareOrEqual (s t : String) : Bool := s == t || decide (t.toList.toFinset.card < 26) /-- Executable checker for `canTransform_spec` via the reshaped feasibility criterion. -/ def canTransform_check (input : Input) (result : Output) : Bool := result == (consistentPairing input.1 input.2 && hasSpareOrEqual input.1 input.2) theorem st_char_iff (c : Char) : ('a' ≤ c ∧ c ≤ 'z') ↔ (97 ≤ c.toNat ∧ c.toNat ≤ 122) := by simp only [Char.le_def, UInt32.le_iff_toNat_le, Char.toNat_val] exact Iff.rfl def stLtr (r : Nat) : Char := ("abcdefghijklmnopqrstuvwxyz".toList[r]?).getD 'a' theorem st_ltr_toNat : ∀ r, r < 26 → (stLtr r).toNat = 97 + r := by unfold stLtr decide def stLower (u : List Char) : Prop := ∀ c ∈ u, 'a' ≤ c ∧ c ≤ 'z' def stConv (x d : Char) (u : List Char) : List Char := u.map (fun z => if z = x then d else z) def stCons (u t : List Char) : Prop := ∀ i j, i < t.length → j < t.length → u.getD i 'a' = u.getD j 'a' → t.getD i 'a' = t.getD j 'a' def stBad (u t : List Char) : Finset Char := ((Finset.range t.length).filter (fun i => u.getD i 'a' ≠ t.getD i 'a')).image (fun i => u.getD i 'a') def stF (u t : List Char) (z : Char) : Char := t.getD (u.idxOf z) 'a' theorem st_valid (s t : String) (h : isValidInput (s, t) = true) : s.toList.length = t.toList.length ∧ stLower s.toList ∧ stLower t.toList := by unfold isValidInput at h simp only [Bool.and_eq_true, decide_eq_true_eq, beq_iff_eq, List.all_eq_true] at h obtain ⟨⟨⟨⟨-, hlen⟩, -⟩, hs⟩, ht⟩ := h refine ⟨?_, hs, ht⟩ rw [String.length_toList, String.length_toList] exact hlen theorem st_getD_idxOf (w : List Char) (c : Char) (hc : c ∈ w) : w.getD (w.idxOf c) 'a' = c := by have hl : w.idxOf c < w.length := List.idxOf_lt_length_iff.mpr hc rw [List.getD_eq_getElem _ _ hl] exact List.getElem_idxOf hl theorem st_getD_mem (w : List Char) (i : Nat) (hi : i < w.length) : w.getD i 'a' ∈ w := by rw [List.getD_eq_getElem _ _ hi] exact List.getElem_mem hi theorem st_conv_getD (u : List Char) (x d : Char) (i : Nat) (hi : i < u.length) : (stConv x d u).getD i 'a' = if u.getD i 'a' = x then d else u.getD i 'a' := by unfold stConv rw [List.getD_eq_getElem _ _ (by simpa using hi), List.getD_eq_getElem _ _ hi, List.getElem_map] theorem st_mem_bad (u t : List Char) (z : Char) : z ∈ stBad u t ↔ ∃ i, i < t.length ∧ u.getD i 'a' ≠ t.getD i 'a' ∧ u.getD i 'a' = z := by unfold stBad simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_range] constructor · rintro ⟨i, ⟨hi, hne⟩, hz⟩ exact ⟨i, hi, hne, hz⟩ · rintro ⟨i, hi, hne, hz⟩ exact ⟨i, ⟨hi, hne⟩, hz⟩ theorem st_F_getD (u t : List Char) (hlen : u.length = t.length) (hcons : stCons u t) (i : Nat) (hi : i < t.length) : stF u t (u.getD i 'a') = t.getD i 'a' := by have hm := st_getD_mem u i (by omega) have hj : u.idxOf (u.getD i 'a') < u.length := List.idxOf_lt_length_iff.mpr hm exact hcons _ _ (by omega) hi (st_getD_idxOf u _ hm) theorem st_F_mem (u t : List Char) (hlen : u.length = t.length) (z : Char) (hz : z ∈ u) : stF u t z ∈ t := by have hj : u.idxOf z < u.length := List.idxOf_lt_length_iff.mpr hz exact st_getD_mem t _ (by omega) theorem st_bad_mem (u t : List Char) (hlen : u.length = t.length) (z : Char) (hz : z ∈ stBad u t) : z ∈ u := by rw [st_mem_bad] at hz obtain ⟨i, hi, -, rfl⟩ := hz exact st_getD_mem u i (by omega) theorem st_good (u t : List Char) (hlen : u.length = t.length) (z : Char) (hz : z ∈ u) (hnb : z ∉ stBad u t) : stF u t z = z := by have hj : u.idxOf z < u.length := List.idxOf_lt_length_iff.mpr hz by_contra hne apply hnb rw [st_mem_bad] refine ⟨u.idxOf z, by omega, ?_, st_getD_idxOf u z hz⟩ rw [st_getD_idxOf u z hz] exact fun h => hne h.symm theorem st_bad_F_ne (u t : List Char) (hlen : u.length = t.length) (hcons : stCons u t) (x : Char) (hx : x ∈ stBad u t) : stF u t x ≠ x := by rw [st_mem_bad] at hx obtain ⟨i, hi, hne, rfl⟩ := hx rw [st_F_getD u t hlen hcons i hi] exact fun h => hne h.symm theorem st_eq_of_bad_empty (u t : List Char) (hlen : u.length = t.length) (h : stBad u t = ∅) : u = t := by apply List.ext_getElem hlen intro i h1 h2 by_contra hne have hm : u.getD i 'a' ∈ stBad u t := by rw [st_mem_bad] refine ⟨i, h2, ?_, rfl⟩ rw [List.getD_eq_getElem _ _ h1, List.getD_eq_getElem _ _ h2] exact hne rw [h] at hm simp at hm theorem st_conv (u t : List Char) (hlen : u.length = t.length) (hlow : stLower u) (hcons : stCons u t) (x d : Char) (hxu : x ∈ u) (hd : 'a' ≤ d ∧ d ≤ 'z') (hxd : x ≠ d) (hpos : ∀ i j, i < t.length → j < t.length → u.getD i 'a' = x → u.getD j 'a' = d → t.getD i 'a' = t.getD j 'a') : step (String.ofList u) (String.ofList (stConv x d u)) ∧ (stConv x d u).length = t.length ∧ stLower (stConv x d u) ∧ stCons (stConv x d u) t ∧ ∀ z ∈ stBad (stConv x d u) t, (z ∈ stBad u t ∧ z ≠ x) ∨ (z = d ∧ ∃ i, i < t.length ∧ u.getD i 'a' = x ∧ t.getD i 'a' ≠ d) := by have hx := hlow x hxu refine ⟨⟨x, d, hx.1, hx.2, hd.1, hd.2, hxd, ?_⟩, ?_, ?_, ?_, ?_⟩ · rw [String.toList_ofList, String.toList_ofList] all_goals rfl · unfold stConv rw [List.length_map, hlen] · intro c hc unfold stConv at hc rw [List.mem_map] at hc obtain ⟨z, hz, rfl⟩ := hc split_ifs · exact hd · exact hlow z hz · intro i j hi hj hij rw [st_conv_getD u x d i (by omega), st_conv_getD u x d j (by omega)] at hij by_cases hix : u.getD i 'a' = x <;> by_cases hjx : u.getD j 'a' = x · exact hcons i j hi hj (hix.trans hjx.symm) · rw [if_pos hix, if_neg hjx] at hij exact hpos i j hi hj hix hij.symm · rw [if_neg hix, if_pos hjx] at hij exact (hpos j i hj hi hjx hij).symm · rw [if_neg hix, if_neg hjx] at hij exact hcons i j hi hj hij · intro z hz rw [st_mem_bad] at hz obtain ⟨i, hi, hne, hzi⟩ := hz rw [st_conv_getD u x d i (by omega)] at hne hzi by_cases hix : u.getD i 'a' = x · rw [if_pos hix] at hne hzi right exact ⟨hzi.symm, i, hi, hix, fun h => hne h.symm⟩ · rw [if_neg hix] at hne hzi left refine ⟨(st_mem_bad u t z).mpr ⟨i, hi, hne, hzi⟩, ?_⟩ rw [← hzi] exact hix theorem st_spare (S : Finset Char) (hS : S.card < 26) : ∃ e, 'a' ≤ e ∧ e ≤ 'z' ∧ e ∉ S := by have hinj : Function.Injective Char.toNat := fun a b h => Char.toNat_inj.mp h have hc : (S.image Char.toNat).card < (Finset.Icc 97 122).card := by rw [Finset.card_image_of_injective _ hinj, Nat.card_Icc] omega obtain ⟨k, hk, hkn⟩ := Finset.exists_mem_notMem_of_card_lt_card hc rw [Finset.mem_Icc] at hk have hr : k - 97 < 26 := by omega have ht := st_ltr_toNat (k - 97) hr have hlow : 'a' ≤ stLtr (k - 97) ∧ stLtr (k - 97) ≤ 'z' := by rw [st_char_iff, ht] omega refine ⟨stLtr (k - 97), hlow.1, hlow.2, fun hm => hkn ?_⟩ rw [Finset.mem_image] exact ⟨_, hm, by rw [ht]; omega⟩ theorem st_card_missing (t : List Char) (hlt : stLower t) (c : Char) (hc : 'a' ≤ c ∧ c ≤ 'z') (hct : c ∉ t) : t.toFinset.card < 26 := by have hinj : Function.Injective Char.toNat := fun a b h => Char.toNat_inj.mp h have hcI : c.toNat ∈ Finset.Icc 97 122 := Finset.mem_Icc.mpr ((st_char_iff c).mp hc) have hsub : t.toFinset.image Char.toNat ⊆ (Finset.Icc 97 122).erase c.toNat := by intro k hk rw [Finset.mem_image] at hk obtain ⟨z, hz, rfl⟩ := hk rw [List.mem_toFinset] at hz rw [Finset.mem_erase, Finset.mem_Icc] refine ⟨fun h => hct ?_, (st_char_iff z).mp (hlt z hz)⟩ rw [← hinj h] exact hz have hcard := Finset.card_le_card hsub rw [Finset.card_image_of_injective _ hinj, Finset.card_erase_of_mem hcI, Nat.card_Icc] at hcard omega theorem st_complete (s t : String) (h : CanTransform s t) : (∃ g : Char → Char, t.toList = s.toList.map g) ∧ (s = t ∨ ∃ c, ('a' ≤ c ∧ c ≤ 'z') ∧ c ∉ t.toList) := by unfold CanTransform at h induction h with | refl => exact ⟨⟨id, by simp⟩, Or.inl rfl⟩ | tail _ hst ih => obtain ⟨⟨g, hg⟩, -⟩ := ih obtain ⟨c, d, hc1, hc2, -, -, hcd, heq⟩ := hst refine ⟨⟨(fun x => if x = c then d else x) ∘ g, by rw [heq, hg, List.map_map]⟩, Or.inr ⟨c, ⟨hc1, hc2⟩, ?_⟩⟩ rw [heq, List.mem_map] rintro ⟨x, -, hx⟩ by_cases hxc : x = c · rw [if_pos hxc] at hx exact hcd hx.symm · rw [if_neg hxc] at hx exact hxc hx theorem st_sound_step (t : List Char) (hlt : stLower t) (hsp : t.toFinset.card < 26) (k : Nat) (ih : ∀ m, m < k → ∀ u : List Char, (stBad u t).card = m → u.length = t.length → stLower u → stCons u t → Relation.ReflTransGen step (String.ofList u) (String.ofList t)) (u : List Char) (hk : (stBad u t).card = k) (hlen : u.length = t.length) (hlow : stLower u) (hcons : stCons u t) : Relation.ReflTransGen step (String.ofList u) (String.ofList t) := by by_cases hemp : stBad u t = ∅ · have hut := st_eq_of_bad_empty u t hlen hemp subst hut exact Relation.ReflTransGen.refl obtain ⟨x0, hx0⟩ := Finset.nonempty_iff_ne_empty.mpr hemp have hpos0 := Finset.card_pos.mpr ⟨x0, hx0⟩ by_cases hT : ∃ x ∈ stBad u t, ∀ j, j < t.length → u.getD j 'a' = stF u t x → t.getD j 'a' = stF u t x · obtain ⟨x, hx, hxT⟩ := hT have hxu := st_bad_mem u t hlen x hx have hdt := st_F_mem u t hlen x hxu obtain ⟨hstep, hlen', hlow', hcons', hbad'⟩ := st_conv u t hlen hlow hcons x (stF u t x) hxu (hlt _ hdt) (fun h => st_bad_F_ne u t hlen hcons x hx h.symm) (fun i j hi hj hix hjd => by have e1 := st_F_getD u t hlen hcons i hi rw [hix] at e1 rw [← e1, hxT j hj hjd]) have hsub : stBad (stConv x (stF u t x) u) t ⊆ (stBad u t).erase x := by intro z hz rcases hbad' z hz with ⟨hzb, hzx⟩ | ⟨-, i, hi, hix, hne⟩ · exact Finset.mem_erase.mpr ⟨hzx, hzb⟩ · exfalso apply hne rw [← hix, st_F_getD u t hlen hcons i hi] have hlt' : (stBad (stConv x (stF u t x) u) t).card < k := by have h1 := Finset.card_le_card hsub rw [Finset.card_erase_of_mem hx] at h1 omega exact Relation.ReflTransGen.head hstep (ih _ hlt' _ rfl hlen' hlow' hcons') by_cases hM : ∃ x ∈ stBad u t, ∃ y ∈ u, y ≠ x ∧ stF u t y = stF u t x · obtain ⟨x, hx, y, hy, hyx, hFyx⟩ := hM have hxu := st_bad_mem u t hlen x hx obtain ⟨hstep, hlen', hlow', hcons', hbad'⟩ := st_conv u t hlen hlow hcons x y hxu (hlow y hy) (fun h => hyx h.symm) (fun i j hi hj hix hjy => by rw [← st_F_getD u t hlen hcons i hi, ← st_F_getD u t hlen hcons j hj, hix, hjy, hFyx]) have hsub : stBad (stConv x y u) t ⊆ (stBad u t).erase x := by intro z hz rcases hbad' z hz with ⟨hzb, hzx⟩ | ⟨hzy, i, hi, hix, hne⟩ · exact Finset.mem_erase.mpr ⟨hzx, hzb⟩ · rw [hzy] refine Finset.mem_erase.mpr ⟨hyx, ?_⟩ by_contra hyb have hgood := st_good u t hlen y hy hyb apply hne rw [← st_F_getD u t hlen hcons i hi, hix, ← hFyx, hgood] have hlt' : (stBad (stConv x y u) t).card < k := by have h1 := Finset.card_le_card hsub rw [Finset.card_erase_of_mem hx] at h1 omega exact Relation.ReflTransGen.head hstep (ih _ hlt' _ rfl hlen' hlow' hcons') have hFB : ∀ z ∈ stBad u t, stF u t z ∈ stBad u t := by intro z hz by_contra hc apply hT refine ⟨z, hz, fun j hj hju => ?_⟩ by_contra hne apply hc rw [st_mem_bad] exact ⟨j, hj, by rw [hju]; exact fun h => hne h.symm, hju⟩ have hinj : Set.InjOn (stF u t) ↑u.toFinset := by intro a ha b hb hab simp only [Finset.mem_coe, List.mem_toFinset] at ha hb by_contra hne by_cases ha' : a ∈ stBad u t · exact hM ⟨a, ha', b, hb, fun h => hne h.symm, hab.symm⟩ · by_cases hb' : b ∈ stBad u t · exact hM ⟨b, hb', a, ha, hne, hab⟩ · rw [st_good u t hlen a ha ha', st_good u t hlen b hb hb'] at hab exact hne hab have hBsub : (↑(stBad u t) : Set Char) ⊆ ↑u.toFinset := by intro z hz simp only [Finset.mem_coe, List.mem_toFinset] at hz ⊢ exact st_bad_mem u t hlen z hz have hBimg : (stBad u t).image (stF u t) = stBad u t := by apply Finset.eq_of_subset_of_card_le · intro z hz rw [Finset.mem_image] at hz obtain ⟨w, hw, rfl⟩ := hz exact hFB w hw · exact (Finset.card_image_of_injOn (hinj.mono hBsub)).ge have hTimg : t.toFinset = u.toFinset.image (stF u t) := by ext c rw [List.mem_toFinset, Finset.mem_image] constructor · intro hc obtain ⟨i, hi, rfl⟩ := List.mem_iff_getElem.mp hc refine ⟨u.getD i 'a', List.mem_toFinset.mpr (st_getD_mem u i (by omega)), ?_⟩ rw [st_F_getD u t hlen hcons i hi, List.getD_eq_getElem t 'a' hi] · rintro ⟨z, hz, rfl⟩ exact st_F_mem u t hlen z (List.mem_toFinset.mp hz) have hScard : u.toFinset.card < 26 := by rw [hTimg, Finset.card_image_of_injOn hinj] at hsp exact hsp obtain ⟨e, he1, he2, heS⟩ := st_spare u.toFinset hScard have heu : e ∉ u := fun h => heS (List.mem_toFinset.mpr h) have hx0img : x0 ∈ (stBad u t).image (stF u t) := by rw [hBimg] exact hx0 rw [Finset.mem_image] at hx0img obtain ⟨y, hyB, hyx⟩ := hx0img have hx0u := st_bad_mem u t hlen x0 hx0 have hyu := st_bad_mem u t hlen y hyB have hyx0 : y ≠ x0 := by intro h rw [h] at hyx exact st_bad_F_ne u t hlen hcons x0 hx0 hyx have hx0e : x0 ≠ e := fun h => heu (h ▸ hx0u) have hye : y ≠ e := fun h => heu (h ▸ hyu) obtain ⟨hstep1, hlen1, hlow1, hcons1, hbad1⟩ := st_conv u t hlen hlow hcons x0 e hx0u ⟨he1, he2⟩ hx0e (fun i j hi hj _ hje => absurd (hje ▸ st_getD_mem u j (by omega)) heu) have hyu1 : y ∈ stConv x0 e u := by unfold stConv rw [List.mem_map] exact ⟨y, hyu, if_neg hyx0⟩ have hx0u1 : ∀ j, j < t.length → (stConv x0 e u).getD j 'a' ≠ x0 := by intro j hj rw [st_conv_getD u x0 e j (by omega)] split_ifs with h · exact fun h' => hx0e h'.symm · exact h obtain ⟨hstep2, hlen2, hlow2, hcons2, hbad2⟩ := st_conv (stConv x0 e u) t hlen1 hlow1 hcons1 y x0 hyu1 (hlow x0 hx0u) hyx0 (fun i j hi hj _ hjx => absurd hjx (hx0u1 j hj)) have hsub : stBad (stConv y x0 (stConv x0 e u)) t ⊆ (insert e ((stBad u t).erase x0)).erase y := by intro z hz rcases hbad2 z hz with ⟨hz1, hzy⟩ | ⟨-, i, hi, hiy, hne⟩ · refine Finset.mem_erase.mpr ⟨hzy, ?_⟩ rcases hbad1 z hz1 with ⟨hzb, hzx⟩ | ⟨hze, -⟩ · exact Finset.mem_insert_of_mem (Finset.mem_erase.mpr ⟨hzx, hzb⟩) · rw [hze] exact Finset.mem_insert_self e _ · exfalso apply hne rw [st_conv_getD u x0 e i (by omega)] at hiy by_cases hix : u.getD i 'a' = x0 · rw [if_pos hix] at hiy exact absurd hiy.symm hye · rw [if_neg hix] at hiy rw [← st_F_getD u t hlen hcons i hi, hiy, hyx] have hlt2 : (stBad (stConv y x0 (stConv x0 e u)) t).card < k := by have h1 := Finset.card_le_card hsub have hyin : y ∈ insert e ((stBad u t).erase x0) := Finset.mem_insert_of_mem (Finset.mem_erase.mpr ⟨hyx0, hyB⟩) have henot : e ∉ (stBad u t).erase x0 := fun h => heu (st_bad_mem u t hlen e (Finset.mem_of_mem_erase h)) rw [Finset.card_erase_of_mem hyin, Finset.card_insert_of_notMem henot, Finset.card_erase_of_mem hx0] at h1 omega exact Relation.ReflTransGen.head hstep1 (Relation.ReflTransGen.head hstep2 (ih _ hlt2 _ rfl hlen2 hlow2 hcons2)) theorem st_sound (t : List Char) (hlt : stLower t) (hsp : t.toFinset.card < 26) : ∀ k (u : List Char), (stBad u t).card = k → u.length = t.length → stLower u → stCons u t → Relation.ReflTransGen step (String.ofList u) (String.ofList t) := by intro k induction k using Nat.strong_induction_on with | _ k ih => exact st_sound_step t hlt hsp k ih theorem st_cons_of_pairing (s t : String) (hlen : s.toList.length = t.toList.length) (h : consistentPairing s t = true) : stCons s.toList t.toList := by unfold consistentPairing at h simp only [List.all_eq_true, Bool.or_eq_true, Bool.not_eq_true', beq_eq_false_iff_ne, beq_iff_eq] at h have hz : ∀ k, k < t.toList.length → (s.toList.getD k 'a', t.toList.getD k 'a') ∈ s.toList.zip t.toList := by intro k hk have hk' : k < (s.toList.zip t.toList).length := by rw [List.length_zip] omega refine List.mem_iff_getElem.mpr ⟨k, hk', ?_⟩ rw [List.getElem_zip, List.getD_eq_getElem s.toList 'a' (show k < s.toList.length by omega), List.getD_eq_getElem t.toList 'a' hk] intro i j hi hj hij rcases h _ (hz i hi) _ (hz j hj) with hne | heq · exact absurd hij hne · exact heq theorem st_zip_map (g : Char → Char) : ∀ (l : List Char) (p : Char × Char), p ∈ l.zip (l.map g) → p.2 = g p.1 := by intro l induction l with | nil => intro p hp simp at hp | cons a l ih => intro p hp rw [List.map_cons, List.zip_cons_cons, List.mem_cons] at hp rcases hp with rfl | hp · rfl · exact ih p hp theorem st_pairing_of_map (s t : String) (g : Char → Char) (hg : t.toList = s.toList.map g) : consistentPairing s t = true := by unfold consistentPairing simp only [List.all_eq_true, Bool.or_eq_true, Bool.not_eq_true', beq_eq_false_iff_ne, beq_iff_eq] intro p hp q hq rw [hg] at hp hq by_cases h1 : p.1 = q.1 · right rw [st_zip_map g _ p hp, st_zip_map g _ q hq, h1] · left exact h1 theorem st_bridge (s t : String) (h : isValidInput (s, t) = true) : (consistentPairing s t && hasSpareOrEqual s t) = true ↔ CanTransform s t := by obtain ⟨hlen, hls, hlt⟩ := st_valid s t h rw [Bool.and_eq_true] constructor · rintro ⟨hcp, hsp⟩ unfold hasSpareOrEqual at hsp rw [Bool.or_eq_true, beq_iff_eq, decide_eq_true_iff] at hsp rcases hsp with heq | hcard · rw [heq] exact Relation.ReflTransGen.refl · have hr := st_sound t.toList hlt hcard _ s.toList rfl hlen hls (st_cons_of_pairing s t hlen hcp) rw [String.ofList_toList, String.ofList_toList] at hr exact hr · intro hct obtain ⟨⟨g, hg⟩, hor⟩ := st_complete s t hct refine ⟨st_pairing_of_map s t g hg, ?_⟩ unfold hasSpareOrEqual rw [Bool.or_eq_true, beq_iff_eq, decide_eq_true_iff] rcases hor with heq | ⟨c, hc, hct'⟩ · exact Or.inl heq · exact Or.inr (st_card_missing t.toList hlt c hc hct') /-- On valid input the checker accepts exactly the specified outputs. -/ theorem canTransform_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : canTransform_check input result ↔ canTransform_spec input result := by obtain ⟨s, t⟩ := input unfold canTransform_check canTransform_spec rw [beq_iff_eq, Bool.eq_iff_iff] exact iff_congr Iff.rfl (st_bridge s t h) /-! ### Implementation helpers -/ /-- One pass over the position pairs: each source character must always map to the same target character, with the mapping kept as an association list of at most 26 entries. -/ def linearConsistent (pairs : List (Char × Char)) (map : List (Char × Char)) : Bool := match pairs with | [] => true | (c, d) :: rest => match map.find? (fun p => p.1 == c) with | some (_, d') => if d' == d then linearConsistent rest map else false | none => linearConsistent rest ((c, d) :: map) /-! ### Main algorithm (impl) -/ /-- Single left-to-right pass building a source-to-target character mapping, rejecting on conflict, then the checker's spare-letter-or-equal condition. -/ def canTransformString (input : Input) : Bool := linearConsistent (input.1.toList.zip input.2.toList) [] && hasSpareOrEqual input.1 input.2 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem canTransformString_correct (input : Input) (h : isValidInput input) : canTransform_spec input (canTransformString input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("aabcc", "ccdee") #guard isValidInput ("aaa", "aaa") #guard isValidInput ("abc", "abc") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("", "")) #guard !(isValidInput ("a", "aa")) #guard !(isValidInput ("a", "A")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard canTransform_check ("aabcc", "ccdee") true #guard canTransform_check ("aaa", "aaa") true #guard canTransform_check ("abc", "abc") true /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(canTransform_check ("aabcc", "ccdee") false) #guard !(canTransform_check ("aaa", "aaa") false) #guard !(canTransform_check ("abc", "abc") false) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard canTransformString ("aabcc", "ccdee") == true #guard canTransformString ("aaa", "aaa") == true #guard canTransformString ("abc", "abc") == true /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard canTransform_check ("aabcc", "ccdee") (canTransformString ("aabcc", "ccdee")) #guard canTransform_check ("aaa", "aaa") (canTransformString ("aaa", "aaa")) #guard canTransform_check ("abc", "abc") (canTransformString ("abc", "abc")) end PStringTransformsIntoAnotherString