import Mathlib /-! # K Similar Strings Strings s1 and s2 are k-similar (for some non-negative integer k) if we can swap the positions of two letters in s1 exactly k times so that the resulting string equals s2. Given two anagrams s1 and s2, return the smallest k for which s1 and s2 are k-similar. ## Constraints - 1 <= s1.length <= 20 - s2.length == s1.length - s1 and s2 contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}. - s2 is an anagram of s1. ## Provided examples - `s1 = "ab", s2 = "ba"` → `1` - `s1 = "abc", s2 = "bca"` → `2` - `s1 = "abac", s2 = "baca"` → `2` ## Synthesized negative examples - invalid input: `s1 = "", s2 = ""` ([structural] a predicate that admits 1 <= s1.length <= 20. empty string below the length floor) - invalid input: `s1 = "g", s2 = "g"` ([structural] a predicate that admits s1 and s2 contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}.. lowercase g outside allowed alphabet; anagram-only predicate accepts it) - invalid input: `s1 = "a", s2 = "b"` ([structural] a predicate that admits s2 is an anagram of s1.. same length and alphabet, different letter; per-argument checks pass) - `s1 = "ab", s2 = "ba"` → `3` is wrong ([structural] minimality stated as achievability alone. 3 swaps are achievable (swap, swap back, swap) but not least) - `s1 = "abc", s2 = "bca"` → `4` is wrong ([structural] minimality stated as achievability alone. 4 swaps are possible; 2 is smaller.) - `s1 = "abac", s2 = "baca"` → `3` is wrong ([structural] minimality stated as achievability alone. 3 swaps are real but not least) -/ namespace PKSimilarStrings abbrev Input := (String) × (String) abbrev Output := Nat /-! ### Specification helpers -/ /-- `b` is `a` with the characters at positions `i` and `j` exchanged. -/ def swapStep (a b : List Char) : Prop := ∃ i j : Nat, ∃ x y : Char, a[i]? = some x ∧ a[j]? = some y ∧ b = (a.set i y).set j x /-- `s1` and `s2` are `k`-similar: exactly `k` swaps of two positions turn `s1` into `s2`. -/ def KSimilar (s1 s2 : String) (k : Nat) : Prop := ∃ l : List String, l.length = k + 1 ∧ l.head? = some s1 ∧ l.getLast? = some s2 ∧ l.Chain' (fun a b => swapStep a.toList b.toList) /-! ### Validity predicate (V) -/ /-- Valid input: equal-length anagrams of 1 to 20 letters drawn from `'a'` to `'f'`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 20 && input.2.length == input.1.length && input.1.toList.all (fun c => 'a' ≤ c && c ≤ 'f') && input.2.toList.all (fun c => 'a' ≤ c && c ≤ 'f') && input.1.toList.isPerm input.2.toList /-! ### Ideal specification (P_spec) -/ /-- `result` is the least `k` for which `s1` and `s2` are `k`-similar. -/ def kSimilarityDistance_spec (input : Input) (result : Output) : Prop := IsLeast {k | KSimilar input.1 input.2 k} result /-! ### Decidable specification (P_check) -/ /-- The list `a` with the characters at positions `i` and `j` exchanged, or `a` if either index is out of range. -/ def swapAt (a : List Char) (i j : Nat) : List Char := match a[i]?, a[j]? with | some x, some y => (a.set i y).set j x | _, _ => a /-- Every list one swap of two positions away from `a`, duplicates removed. -/ def swapNeighbors (a : List Char) : List (List Char) := ((List.range a.length).flatMap fun i => (List.range a.length).map fun j => swapAt a i j).dedup /-- The states one swap beyond `frontier` that have not been visited before. -/ def nextLayer (visited frontier : List (List Char)) : List (List Char) := ((frontier.flatMap swapNeighbors).filter fun b => !visited.contains b).dedup /-- The visited set and the outermost frontier after `d` breadth-first layers from `start`. -/ def reachAux (start : List Char) : Nat → List (List Char) × List (List Char) | 0 => ([start], [start]) | d + 1 => let (visited, frontier) := reachAux start d let nxt := nextLayer visited frontier (visited ++ nxt, nxt) /-- Every string reachable from `start` by at most `d` swaps of two positions. -/ def reachUpTo (start : List Char) (d : Nat) : List (List Char) := (reachAux start d).1 /-- Executable checker for `kSimilarityDistance_spec`: `result` is the least number of swaps reaching `s2`. -/ def kSimilarityDistance_check (input : Input) (result : Output) : Bool := let s1 := input.1.toList let s2 := input.2.toList (reachUpTo s1 result).contains s2 && (result == 0 || !(reachUpTo s1 (result - 1)).contains s2) theorem wx_neighbors (a b : List Char) : b ∈ swapNeighbors a ↔ swapStep a b := by constructor · intro hb rw [swapNeighbors, List.mem_dedup] at hb rcases List.mem_flatMap.mp hb with ⟨i, hi, hb⟩ rcases List.mem_map.mp hb with ⟨j, hj, hb⟩ have hi' : i < a.length := List.mem_range.mp hi have hj' : j < a.length := List.mem_range.mp hj have hai : a[i]? = some a[i] := List.getElem?_eq_getElem hi' have haj : a[j]? = some a[j] := List.getElem?_eq_getElem hj' refine ⟨i, j, a[i], a[j], hai, haj, ?_⟩ rw [swapAt, hai, haj] at hb exact hb.symm · rintro ⟨i, j, x, y, hi, hj, rfl⟩ have hil : i < a.length := by by_contra hn have hnone : a[i]? = none := List.getElem?_eq_none (Nat.le_of_not_gt hn) rw [hnone] at hi contradiction have hjl : j < a.length := by by_contra hn have hnone : a[j]? = none := List.getElem?_eq_none (Nat.le_of_not_gt hn) rw [hnone] at hj contradiction rw [swapNeighbors, List.mem_dedup] apply List.mem_flatMap.mpr refine ⟨i, List.mem_range.mpr hil, ?_⟩ apply List.mem_map.mpr refine ⟨j, List.mem_range.mpr hjl, ?_⟩ simp [swapAt, hi, hj] def wxPath (a b : List Char) : Nat → Prop | 0 => b = a | n + 1 => ∃ c, wxPath a c n ∧ swapStep c b lemma wx_nextLayer_mem {visited frontier : List (List Char)} {c b : List Char} (hc : c ∈ frontier) (hb : b ∈ swapNeighbors c) : b ∈ visited ∨ b ∈ nextLayer visited frontier := by by_cases hv : b ∈ visited · exact Or.inl hv · right simp only [nextLayer, List.mem_dedup, List.mem_filter, List.mem_flatMap] refine ⟨⟨c, hc, hb⟩, ?_⟩ simp [hv] lemma wx_reach_sound_aux (step : ∀ a b, b ∈ swapNeighbors a ↔ swapStep a b) (a : List Char) (d : Nat) : (∀ b, b ∈ (reachAux a d).1 → ∃ k, k ≤ d ∧ wxPath a b k) ∧ (∀ b, b ∈ (reachAux a d).2 → wxPath a b d) := by induction d with | zero => constructor · intro b hb simp only [reachAux, List.mem_singleton] at hb exact ⟨0, Nat.zero_le _, by simpa [wxPath] using hb⟩ · intro b hb simpa [reachAux, wxPath] using hb | succ d ih => rcases heq : reachAux a d with ⟨visited, frontier⟩ have ihV : ∀ b, b ∈ visited → ∃ k, k ≤ d ∧ wxPath a b k := by simpa [heq] using ih.1 have ihF : ∀ b, b ∈ frontier → wxPath a b d := by simpa [heq] using ih.2 have hn : ∀ b, b ∈ nextLayer visited frontier → wxPath a b (d + 1) := by intro b hb simp only [nextLayer, List.mem_dedup, List.mem_filter, List.mem_flatMap] at hb rcases hb.1 with ⟨c, hc, hcb⟩ exact ⟨c, ihF c hc, (step c b).mp hcb⟩ constructor · intro b hb have hb' : b ∈ visited ++ nextLayer visited frontier := by simpa [reachAux, heq] using hb rcases List.mem_append.mp hb' with hbV | hbN · rcases ihV b hbV with ⟨k, hk, hp⟩ exact ⟨k, Nat.le.step hk, hp⟩ · exact ⟨d + 1, Nat.le_refl _, hn b hbN⟩ · intro b hb apply hn b simpa [reachAux, heq] using hb lemma wx_reach_mono_one (a : List Char) (d : Nat) (b : List Char) : b ∈ reachUpTo a d → b ∈ reachUpTo a (d + 1) := by rcases heq : reachAux a d with ⟨visited, frontier⟩ intro hb have hbV : b ∈ visited := by simpa [reachUpTo, heq] using hb have hb' : b ∈ visited ++ nextLayer visited frontier := List.mem_append_left _ hbV simpa [reachUpTo, reachAux, heq] using hb' lemma wx_reach_expand (a : List Char) (d : Nat) (c b : List Char) (hc : c ∈ reachUpTo a d) (hb : b ∈ swapNeighbors c) : b ∈ reachUpTo a (d + 1) := by induction d generalizing c b with | zero => have hc' : c ∈ [a] := by simpa [reachUpTo, reachAux] using hc have hor := wx_nextLayer_mem (visited := [a]) (frontier := [a]) hc' hb have hall : b ∈ [a] ++ nextLayer [a] [a] := List.mem_append.mpr hor simpa [reachUpTo, reachAux] using hall | succ d ih => rcases heq : reachAux a d with ⟨visited, frontier⟩ have hc' : c ∈ visited ++ nextLayer visited frontier := by simpa [reachUpTo, reachAux, heq] using hc rcases List.mem_append.mp hc' with hcV | hcN · have hcOld : c ∈ reachUpTo a d := by simpa [reachUpTo, heq] using hcV have hbCur := ih c b hcOld hb have hbCur' : b ∈ visited ++ nextLayer visited frontier := by simpa [reachUpTo, reachAux, heq] using hbCur have hall : b ∈ (visited ++ nextLayer visited frontier) ++ nextLayer (visited ++ nextLayer visited frontier) (nextLayer visited frontier) := List.mem_append_left _ hbCur' simpa [reachUpTo, reachAux, heq] using hall · have hor := wx_nextLayer_mem (visited := visited ++ nextLayer visited frontier) (frontier := nextLayer visited frontier) hcN hb have hall : b ∈ (visited ++ nextLayer visited frontier) ++ nextLayer (visited ++ nextLayer visited frontier) (nextLayer visited frontier) := List.mem_append.mpr hor simpa [reachUpTo, reachAux, heq] using hall lemma wx_reach_mono (a : List Char) (k d : Nat) (b : List Char) (hkd : k ≤ d) (hb : b ∈ reachUpTo a k) : b ∈ reachUpTo a d := by induction d generalizing k with | zero => have hk : k = 0 := by omega subst k exact hb | succ d ih => by_cases hle : k ≤ d · exact wx_reach_mono_one a d b (ih k hle hb) · have hk : k = d + 1 := by omega subst k exact hb lemma wx_path_mem (step : ∀ a b, b ∈ swapNeighbors a ↔ swapStep a b) (a b : List Char) (k : Nat) (hp : wxPath a b k) : b ∈ reachUpTo a k := by induction k generalizing b with | zero => simp only [wxPath] at hp subst b simp [reachUpTo, reachAux] | succ k ih => rcases hp with ⟨c, hc, hcb⟩ exact wx_reach_expand a k c b (ih c hc) ((step c b).mpr hcb) lemma wx_reach (step : ∀ a b, b ∈ swapNeighbors a ↔ swapStep a b) (a b : List Char) (d : Nat) : b ∈ reachUpTo a d ↔ ∃ k, k ≤ d ∧ wxPath a b k := by constructor · intro hb exact (wx_reach_sound_aux step a d).1 b (by simpa [reachUpTo] using hb) · rintro ⟨k, hk, hp⟩ exact wx_reach_mono a k d b hk (wx_path_mem step a b k hp) def wxFPath (a b : List Char) : Nat → Prop | 0 => b = a | n + 1 => ∃ c, swapStep a c ∧ wxFPath c b n theorem wxFPath_iff_chain (a b : List Char) (n : Nat) : wxFPath a b n ↔ ∃ l : List (List Char), l.length = n + 1 ∧ l.head? = some a ∧ l.getLast? = some b ∧ l.IsChain swapStep := by induction n generalizing a b with | zero => simp [wxFPath, List.length_eq_one_iff, eq_comm] | succ n ih => constructor · rintro ⟨c, hac, hrest⟩ rw [ih] at hrest rcases hrest with ⟨l, hlen, hhead, hlast, hchain⟩ cases l with | nil => simp at hhead | cons x xs => simp only [List.head?_cons, Option.some.injEq] at hhead subst x refine ⟨a :: c :: xs, ?_, rfl, ?_, ?_⟩ · simp only [List.length_cons] at hlen ⊢ omega · simpa using hlast · exact .cons_cons hac hchain · rintro ⟨l, hlen, hhead, hlast, hchain⟩ cases l with | nil => simp at hhead | cons x xs => simp only [List.head?_cons, Option.some.injEq] at hhead subst x cases xs with | nil => simp at hlen | cons c cs => refine ⟨c, hchain.rel, ?_⟩ rw [ih] refine ⟨c :: cs, ?_, rfl, ?_, hchain.tail⟩ · simp only [List.length_cons] at hlen ⊢ omega · simpa using hlast theorem wxPath_succ_head (a b : List Char) (n : Nat) : wxPath a b (Nat.succ n) ↔ ∃ c, swapStep a c ∧ wxPath c b n := by induction n generalizing a b with | zero => change (∃ c, c = a ∧ swapStep c b) ↔ ∃ c, swapStep a c ∧ b = c constructor · rintro ⟨c, rfl, hab⟩ exact ⟨b, hab, rfl⟩ · rintro ⟨c, hac, rfl⟩ exact ⟨a, rfl, hac⟩ | succ n ih => change (∃ c, wxPath a c (Nat.succ n) ∧ swapStep c b) ↔ ∃ d, swapStep a d ∧ ∃ c, wxPath d c n ∧ swapStep c b constructor · rintro ⟨c, hac, hcb⟩ rw [ih] at hac rcases hac with ⟨d, had, hdc⟩ exact ⟨d, had, c, hdc, hcb⟩ · rintro ⟨d, had, c, hdc, hcb⟩ exact ⟨c, (ih a c).2 ⟨d, had, hdc⟩, hcb⟩ theorem wxFPath_iff_wxPath (a b : List Char) (n : Nat) : wxFPath a b n ↔ wxPath a b n := by induction n generalizing a b with | zero => rfl | succ n ih => rw [wxFPath, wxPath_succ_head] simp only [ih] theorem wx_similar (s t : String) (k : Nat) : KSimilar s t k ↔ wxPath s.toList t.toList k := by rw [← wxFPath_iff_wxPath, wxFPath_iff_chain] constructor · rintro ⟨l, hlen, hhead, hlast, hchain⟩ refine ⟨l.map String.toList, ?_, ?_, ?_, ?_⟩ · simpa using hlen · simpa using congrArg (Option.map String.toList) hhead · simpa using congrArg (Option.map String.toList) hlast · rw [List.isChain_map] exact hchain · rintro ⟨l, hlen, hhead, hlast, hchain⟩ refine ⟨l.map String.ofList, ?_, ?_, ?_, ?_⟩ · simpa using hlen · simpa using congrArg (Option.map String.ofList) hhead · simpa using congrArg (Option.map String.ofList) hlast · change (l.map String.ofList).IsChain (fun a b => swapStep a.toList b.toList) rw [List.isChain_map] simpa using hchain lemma wx_root (input : Input) (result : Output) (reach : ∀ d, input.2.toList ∈ reachUpTo input.1.toList d ↔ ∃ k, k ≤ d ∧ KSimilar input.1 input.2 k) : kSimilarityDistance_check input result ↔ kSimilarityDistance_spec input result := by change Nat at result simp only [kSimilarityDistance_check, List.contains_eq_mem, Bool.and_eq_true, Bool.or_eq_true, beq_iff_eq, Bool.not_eq_true', decide_eq_true_eq, decide_eq_false_iff_not] simp only [reach] change ((∃ k, k ≤ result ∧ KSimilar input.1 input.2 k) ∧ (result = 0 ∨ ¬ ∃ k, k ≤ result - 1 ∧ KSimilar input.1 input.2 k)) ↔ (KSimilar input.1 input.2 result ∧ ∀ j, KSimilar input.1 input.2 j → result ≤ j) constructor · rintro ⟨⟨k, hk, hp⟩, hn⟩ have he : k = result := by rcases hn with hn | hn · omega · by_contra he exact hn ⟨k, by omega, hp⟩ subst k refine ⟨hp, ?_⟩ intro j hj rcases hn with hn | hn · omega · by_contra hjr exact hn ⟨j, by omega, hj⟩ · rintro ⟨hp, hmin⟩ refine ⟨⟨result, le_rfl, hp⟩, ?_⟩ by_cases hz : result = 0 · exact Or.inl hz · right rintro ⟨j, hj, hpj⟩ have := hmin j hpj omega /-- On valid input the checker accepts exactly the specified outputs. -/ theorem kSimilarityDistance_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : kSimilarityDistance_check input result ↔ kSimilarityDistance_spec input result := by apply wx_root input result intro d rw [wx_reach wx_neighbors] simp only [wx_similar] /-! ### Implementation helpers -/ /-- The positions in `cs` whose character equals the required character `need`. -/ def candidateIndices (need : Char) (cs : List Char) : List Nat := (List.range cs.length).filter fun i => cs[i]? == some need /-- Minimum further swaps to turn the suffix `current` into the suffix `target`, always fixing the leftmost mismatch by swapping in a later position that holds the needed character. -/ def minSwapsFrom (target current : List Char) : Nat := match current with | [] => 0 | c :: cs => match target with | [] => 0 | t :: ts => if c = t then minSwapsFrom ts cs else (candidateIndices t (c :: cs)).foldl (fun best i => Nat.min best (minSwapsFrom ts ((swapAt (c :: cs) 0 i).tail) + 1)) (c :: cs).length termination_by current.length decreasing_by simp_wf all_goals have hlen : ∀ (a : List Char) (i j : Nat), (swapAt a i j).length = a.length := by intro a i j unfold swapAt split <;> simp [List.length_set] all_goals simp only [List.length_cons, List.length_tail, hlen, Nat.add_sub_cancel] all_goals omega /-! ### Main algorithm (impl) -/ /-- A binary search tree used as a memo table from encoded mismatch-multigraph states to their minimum swap counts. -/ inductive MTree where | leaf : MTree | node : Nat → Nat → MTree → MTree → MTree /-- Lookup of an encoded state in the memo tree. -/ def mtreeFind : MTree → Nat → Option Nat | MTree.leaf, _ => none | MTree.node k v l r, x => if x = k then some v else if x < k then mtreeFind l x else mtreeFind r x /-- Insertion of an encoded state and its value into the memo tree. -/ def mtreeIns : MTree → Nat → Nat → MTree | MTree.leaf, k, v => MTree.node k v MTree.leaf MTree.leaf | MTree.node k v l r, x, w => if x = k then MTree.node k w l r else if x < k then MTree.node k v (mtreeIns l x w) r else MTree.node k v l (mtreeIns r x w) /-- All ways to insert `x` somewhere into the list. -/ def insEvery (x : Nat) : List Nat → List (List Nat) | [] => [[x]] | y :: ys => (x :: y :: ys) :: (insEvery x ys).map fun t => y :: t /-- All permutations of all sublists of `xs` (for four letters this is 65 sequences). -/ def cycPerms : List Nat → List (List Nat) | [] => [[]] | x :: xs => (cycPerms xs).flatMap fun p => p :: insEvery x p /-- The multiplicity of the directed edge stored in slot `i` of an encoded state; slot `u * 6 + v` counts positions carrying letter `u` in the source and letter `v` in the target, encoded in base 21 since no count exceeds 20. -/ def stateDig (st i : Nat) : Nat := (st / 21 ^ i) % 21 /-- Encode the mismatch multigraph of the two strings: one unit of `21 ^ (u * 6 + v)` per position whose source letter `u` differs from its target letter `v`. -/ def buildMismatch : List Char → List Char → Nat | [], _ => 0 | _, [] => 0 | c1 :: t1, c2 :: t2 => let u := c1.toNat - 97 let v := c2.toNat - 97 (if u = v then 0 else 21 ^ (u * 6 + v)) + buildMismatch t1 t2 /-- Minimum swaps to resolve the mismatch multigraph encoded by `state`, by exact memoized dynamic programming: the first present edge lies on some directed cycle of the optimal decomposition, a cycle of length `l` costs `l - 1` swaps, and removing it leaves a strictly smaller encoded state. -/ def solveSwaps (memo : MTree) (state : Nat) : Nat × MTree := if hs : state = 0 then (0, memo) else match mtreeFind memo state with | some v => (v, memo) | none => match (List.range 36).find? fun i => decide (0 < stateDig state i) with | none => (0, memo) | some fi => let u := fi / 6 let v := fi % 6 let others := [0, 1, 2, 3, 4, 5].filter fun x => x != u && x != v let cands := (cycPerms others).filterMap fun ns => let nodes := u :: v :: (ns ++ [u]) let pairs := nodes.zip nodes.tail if pairs.all fun p => decide (0 < stateDig state (p.1 * 6 + p.2)) then some (pairs.foldl (fun s p => s + 21 ^ (p.1 * 6 + p.2)) 0, pairs.length) else none let step := cands.foldl (fun (acc : Nat × MTree) cl => if hc : 0 < cl.1 then let (r, m) := solveSwaps acc.2 (state - cl.1) let cost := r + cl.2 - 1 (if cost < acc.1 then cost else acc.1, m) else acc) (100, memo) (step.1, mtreeIns step.2 state step.1) termination_by state decreasing_by simp_wf all_goals omega /-- Minimum number of swaps making `s1` equal `s2`, computed exactly by dynamic programming over the mismatch multigraph on the six letters. -/ def minSwapsToMakeSimilar (input : Input) : Output := (solveSwaps MTree.leaf (buildMismatch input.1.toList input.2.toList)).1 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem minSwapsToMakeSimilar_correct (input : Input) (h : isValidInput input) : kSimilarityDistance_spec input (minSwapsToMakeSimilar input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("ab", "ba") #guard isValidInput ("abc", "bca") #guard isValidInput ("abac", "baca") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("", "")) #guard !(isValidInput ("g", "g")) #guard !(isValidInput ("a", "b")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard kSimilarityDistance_check ("ab", "ba") 1 #guard kSimilarityDistance_check ("abc", "bca") 2 #guard kSimilarityDistance_check ("abac", "baca") 2 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(kSimilarityDistance_check ("ab", "ba") 3) #guard !(kSimilarityDistance_check ("abc", "bca") 4) #guard !(kSimilarityDistance_check ("abac", "baca") 3) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard minSwapsToMakeSimilar ("ab", "ba") == 1 #guard minSwapsToMakeSimilar ("abc", "bca") == 2 #guard minSwapsToMakeSimilar ("abac", "baca") == 2 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard kSimilarityDistance_check ("ab", "ba") (minSwapsToMakeSimilar ("ab", "ba")) #guard kSimilarityDistance_check ("abc", "bca") (minSwapsToMakeSimilar ("abc", "bca")) #guard kSimilarityDistance_check ("abac", "baca") (minSwapsToMakeSimilar ("abac", "baca")) end PKSimilarStrings