import Mathlib /-! # Edit Distance Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: Insert a character Delete a character Replace a character ## Constraints - 0 <= word1.length, word2.length <= 500 - word1 and word2 consist of lowercase English letters. ## Provided examples - `word1 = "horse", word2 = "ros"` → `3` - `word1 = "", word2 = ""` → `0` - `word1 = "a", word2 = ""` → `1` ## Synthesized negative examples - invalid input: `word1 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", word2 = "a"` ([structural] a predicate that admits 0 <= word1.length, word2.length <= 500. above the length ceiling) - invalid input: `word1 = "A", word2 = "a"` ([structural] a predicate that admits word1 and word2 consist of lowercase English letters.. uppercase; a predicate using isalpha() accepts it) - invalid input: `word1 = "a", word2 = "A"` ([structural] a predicate that admits word1 and word2 consist of lowercase English letters.. word2 uppercase; a predicate checking only word1 accepts it) - `word1 = "horse", word2 = "ros"` → `2` is wrong ([structural] answer is not required to be achievable by any edit sequence. below the true distance; no series of operations reaches it) - `word1 = "", word2 = ""` → `2` is wrong ([structural] minimality stated as achievability alone. insert then delete converts empty to empty in 2) - `word1 = "a", word2 = ""` → `2` is wrong ([structural] minimality stated as achievability alone. 2 is attainable by a real operation sequence but not minimal) -/ namespace PEditDistance /-! ### Representation -/ /-- One permitted edit operation: insert, delete, or replace at a 0-based position. -/ inductive EditOperation where | insert (pos : Nat) (c : Char) | delete (pos : Nat) | replace (pos : Nat) (c : Char) abbrev Input := (String) × (String) abbrev Output := Nat /-! ### Specification helpers -/ /-- Apply one edit operation to a word, or fail if its position is not well-formed. -/ def applyEdit (s : String) : EditOperation → Option String | .insert pos c => if pos ≤ s.length then some (String.mk (s.toList.take pos ++ c :: s.toList.drop pos)) else none | .delete pos => if pos < s.length then some (String.mk (s.toList.take pos ++ s.toList.drop (pos + 1))) else none | .replace pos c => if pos < s.length then some (String.mk (s.toList.take pos ++ c :: s.toList.drop (pos + 1))) else none /-- `ops` converts the first word into the second when applied in order. -/ inductive Converts : String → String → List EditOperation → Prop where | nil {s : String} : Converts s s [] | cons {s t u : String} (op : EditOperation) (ops : List EditOperation) (hstep : applyEdit s op = some u) (hrest : Converts u t ops) : Converts s t (op :: ops) /-! ### Validity predicate (V) -/ /-- Valid input: both words have length at most 500 and use only lowercase English letters. -/ def isValidInput (input : Input) : Bool := input.1.length ≤ 500 && input.2.length ≤ 500 && 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 the least length of any permitted edit sequence converting `word1` to `word2`. -/ def minDistance_spec (input : Input) (result : Output) : Prop := IsLeast {k | ∃ ops : List EditOperation, Converts input.1 input.2 ops ∧ ops.length = k} result /-! ### Decidable specification (P_check) -/ /-- The cost of every monotone alignment of the two character lists: delete the first head, insert the second head, or advance both (free on a match, one replacement otherwise). -/ def pathCosts : List Char → List Char → List Nat | [], [] => [0] | [], _ :: ys => (pathCosts [] ys).map (· + 1) | _ :: xs, [] => (pathCosts xs []).map (· + 1) | x :: xs, y :: ys => (pathCosts xs (y :: ys)).map (· + 1) ++ (pathCosts (x :: xs) ys).map (· + 1) ++ (pathCosts xs ys).map (fun c => if x = y then c else c + 1) termination_by a b => a.length + b.length decreasing_by all_goals (simp_wf <;> omega) /-- Executable checker for `minDistance_spec`: `result` is an attainable alignment cost and a lower bound on all alignment costs. -/ def minDistance_check (input : Input) (result : Output) : Bool := let costs := pathCosts input.1.toList input.2.toList decide ((∃ c ∈ costs, c = result) ∧ (∀ c ∈ costs, result ≤ c)) def snd_prepend (a : Char) (s : String) : String := String.ofList (a :: s.toList) lemma snd_mk (l : List Char) : String.mk l = String.ofList l := by apply String.toByteArray_inj.mp simp [String.mk] def snd_shiftOp : EditOperation → EditOperation | .insert p a => .insert (p + 1) a | .delete p => .delete (p + 1) | .replace p a => .replace (p + 1) a lemma snd_applyEdit_prepend (a : Char) (s : String) (op : EditOperation) : applyEdit (snd_prepend a s) (snd_shiftOp op) = (applyEdit s op).map (snd_prepend a) := by cases op <;> simp [applyEdit, snd_prepend, snd_shiftOp, snd_mk, String.length] lemma snd_converts_prepend (a : Char) {s t : String} {ops : List EditOperation} (h : Converts s t ops) : Converts (snd_prepend a s) (snd_prepend a t) (ops.map snd_shiftOp) := by induction h with | nil => exact Converts.nil | cons op ops hstep hrest ih => apply Converts.cons (snd_shiftOp op) (ops.map snd_shiftOp) · rw [snd_applyEdit_prepend, hstep] rfl · exact ih lemma snd_alignment_sound_list : ∀ (xs ys : List Char) (c : Nat), c ∈ pathCosts xs ys → ∃ ops, Converts (String.ofList xs) (String.ofList ys) ops ∧ ops.length = c := by intro xs ys induction xs, ys using pathCosts.induct with | case1 => intro c hc simp [pathCosts] at hc subst c exact ⟨[], Converts.nil, rfl⟩ | case2 y ys ih => intro c hc simp only [pathCosts, List.mem_map] at hc obtain ⟨d, hd, rfl⟩ := hc obtain ⟨ops, hops, hlen⟩ := ih d hd refine ⟨.insert 0 y :: ops.map snd_shiftOp, ?_, ?_⟩ · apply Converts.cons (u := String.ofList [y]) (.insert 0 y) (ops.map snd_shiftOp) · simp [applyEdit, snd_mk] · simpa [snd_prepend] using snd_converts_prepend y hops · simp [hlen] | case3 x xs ih => intro c hc simp only [pathCosts, List.mem_map] at hc obtain ⟨d, hd, rfl⟩ := hc obtain ⟨ops, hops, hlen⟩ := ih d hd refine ⟨.delete 0 :: ops, ?_, ?_⟩ · apply Converts.cons (u := String.ofList xs) (.delete 0) ops · simp [applyEdit, snd_mk] · exact hops · simp [hlen] | case4 x xs y ys ihDel ihIns ihDiag => intro c hc simp only [pathCosts, List.mem_append, List.mem_map] at hc rcases hc with (hdel | hins) | hdiag · obtain ⟨d, hd, rfl⟩ := hdel obtain ⟨ops, hops, hlen⟩ := ihDel d hd refine ⟨.delete 0 :: ops, ?_, ?_⟩ · apply Converts.cons (u := String.ofList xs) (.delete 0) ops · simp [applyEdit, snd_mk] · exact hops · simp [hlen] · obtain ⟨d, hd, rfl⟩ := hins obtain ⟨ops, hops, hlen⟩ := ihIns d hd refine ⟨.insert 0 y :: ops.map snd_shiftOp, ?_, ?_⟩ · apply Converts.cons (u := String.ofList (y :: x :: xs)) (.insert 0 y) (ops.map snd_shiftOp) · simp [applyEdit, snd_mk] · simpa [snd_prepend] using snd_converts_prepend y hops · simp [hlen] · by_cases hxy : x = y · subst y simp only [if_pos rfl] at hdiag obtain ⟨d, hd, rfl⟩ := hdiag obtain ⟨ops, hops, hlen⟩ := ihDiag d hd refine ⟨ops.map snd_shiftOp, ?_, ?_⟩ · simpa [snd_prepend] using snd_converts_prepend x hops · simpa using hlen · simp only [if_neg hxy] at hdiag obtain ⟨d, hd, rfl⟩ := hdiag obtain ⟨ops, hops, hlen⟩ := ihDiag d hd refine ⟨.replace 0 y :: ops.map snd_shiftOp, ?_, ?_⟩ · apply Converts.cons (u := String.ofList (y :: xs)) (.replace 0 y) (ops.map snd_shiftOp) · simp [applyEdit, snd_mk] · simpa [snd_prepend] using snd_converts_prepend y hops · simp [hlen] lemma alignment_sound : ∀ (s t : String) (c : Nat), c ∈ pathCosts s.toList t.toList → ∃ ops, Converts s t ops ∧ ops.length = c := by intro s t c hc simpa using snd_alignment_sound_list s.toList t.toList c hc theorem root_of_bridges (sound : ∀ (s t : String) (c : Nat), c ∈ pathCosts s.toList t.toList → ∃ ops, Converts s t ops ∧ ops.length = c) (dominate : ∀ (s t : String) (ops : List EditOperation), Converts s t ops → ∃ c ∈ pathCosts s.toList t.toList, c ≤ ops.length) (input : Input) (result : Output) : minDistance_check input result ↔ minDistance_spec input result := by simp only [minDistance_check, decide_eq_true_eq, minDistance_spec, IsLeast, mem_lowerBounds, Set.mem_setOf_eq] constructor · rintro ⟨⟨c, hc, rfl⟩, hlo⟩ refine ⟨sound _ _ _ hc, ?_⟩ rintro k ⟨ops, ho, rfl⟩ obtain ⟨d, hd, hle⟩ := dominate _ _ _ ho exact le_trans (hlo d hd) hle · rintro ⟨⟨ops, ho, he⟩, hlo⟩ obtain ⟨c, hc, hle⟩ := dominate _ _ _ ho have hr : result ≤ c := hlo c (sound _ _ _ hc) have eq : c = result := le_antisymm (he ▸ hle) hr refine ⟨⟨c, hc, eq⟩, ?_⟩ intro d hd exact hlo d (sound _ _ _ hd) inductive Al : List Char → List Char → Nat → Prop where | nil : Al [] [] 0 | del {xs ys n} (x : Char) : Al xs ys n → Al (x :: xs) ys (n+1) | ins {xs ys n} (y : Char) : Al xs ys n → Al xs (y :: ys) (n+1) | pair {xs ys n} (x y : Char) : Al xs ys n → Al (x :: xs) (y :: ys) (n + if x = y then 0 else 1) theorem al_mem {xs ys n} (h : Al xs ys n) : n ∈ pathCosts xs ys := by induction h with | nil => simp [pathCosts] | @del xs ys n x h ih => cases ys <;> simp only [pathCosts, List.mem_append, List.mem_map] · exact ⟨n, ih, rfl⟩ · exact Or.inl (Or.inl ⟨n, ih, rfl⟩) | @ins xs ys n y h ih => cases xs <;> simp only [pathCosts, List.mem_append, List.mem_map] · exact ⟨n, ih, rfl⟩ · exact Or.inl (Or.inr ⟨n, ih, rfl⟩) | @pair xs ys n x y h ih => simp only [pathCosts, List.mem_append, List.mem_map] apply Or.inr refine ⟨n, ih, ?_⟩ split_ifs <;> omega theorem al_refl (xs : List Char) : Al xs xs 0 := by induction xs with | nil => exact .nil | cons x xs ih => simpa using Al.pair x x ih theorem al_trans {xs ys zs : List Char} {n m : Nat} (h : Al xs ys n) (g : Al ys zs m) : ∃ k, Al xs zs k ∧ k ≤ n + m := by cases h with | nil => exact ⟨m, g, by omega⟩ | @del as bs a x h => obtain ⟨k, hk, hl⟩ := al_trans h g exact ⟨k+1, .del x hk, by omega⟩ | @ins as bs a y h => cases g with | del _ g => obtain ⟨k, hk, hl⟩ := al_trans h g exact ⟨k, hk, by omega⟩ | ins z g => obtain ⟨k, hk, hl⟩ := al_trans (Al.ins y h) g exact ⟨k+1, .ins z hk, by omega⟩ | pair _ z g => obtain ⟨k, hk, hl⟩ := al_trans h g exact ⟨k+1, .ins z hk, by omega⟩ | @pair as bs a x y h => cases g with | del _ g => obtain ⟨k, hk, hl⟩ := al_trans h g exact ⟨k+1, .del x hk, by omega⟩ | ins z g => obtain ⟨k, hk, hl⟩ := al_trans (Al.pair x y h) g exact ⟨k+1, .ins z hk, by omega⟩ | pair _ z g => obtain ⟨k, hk, hl⟩ := al_trans h g refine ⟨k + if x = z then 0 else 1, .pair x z hk, ?_⟩ split_ifs at * <;> simp_all <;> omega termination_by xs.length + ys.length + zs.length decreasing_by all_goals simp_all only [List.cons.injEq, List.length_cons] <;> omega theorem al_prefix (pre : List Char) {xs ys n} (h : Al xs ys n) : Al (pre ++ xs) (pre ++ ys) n := by induction pre with | nil => exact h | cons x pre ih => simpa using Al.pair x x ih theorem al_mk (l : List Char) : String.mk l = String.ofList l := by apply String.toByteArray_inj.mp simp [String.mk] theorem al_step {s t : String} (op : EditOperation) (h : applyEdit s op = some t) : ∃ k, Al s.toList t.toList k ∧ k ≤ 1 := by cases op with | insert pos c => simp only [applyEdit] at h split_ifs at h with hb have ht : t = String.ofList (s.toList.take pos ++ c :: s.toList.drop pos) := by simpa only [al_mk, Option.some.injEq] using h.symm subst t refine ⟨1, ?_, by omega⟩ have hh := al_prefix (s.toList.take pos) (Al.ins c (al_refl (s.toList.drop pos))) simpa using hh | delete pos => simp only [applyEdit] at h split_ifs at h with hb have ht : t = String.ofList (s.toList.take pos ++ s.toList.drop (pos+1)) := by simpa only [al_mk, Option.some.injEq] using h.symm subst t have hp : pos < s.toList.length := by simpa only [String.length] using hb refine ⟨1, ?_, by omega⟩ have hh := al_prefix (s.toList.take pos) (Al.del s.toList[pos] (al_refl (s.toList.drop (pos+1)))) simpa only [List.cons_getElem_drop_succ, List.take_append_drop, String.toList_ofList] using hh | replace pos c => simp only [applyEdit] at h split_ifs at h with hb have ht : t = String.ofList (s.toList.take pos ++ c :: s.toList.drop (pos+1)) := by simpa only [al_mk, Option.some.injEq] using h.symm subst t have hp : pos < s.toList.length := by simpa only [String.length] using hb refine ⟨(if s.toList[pos] = c then 0 else 1), ?_, by split_ifs <;> omega⟩ have hh := al_prefix (s.toList.take pos) (Al.pair s.toList[pos] c (al_refl (s.toList.drop (pos+1)))) simpa only [List.cons_getElem_drop_succ, List.take_append_drop, String.toList_ofList, Nat.zero_add] using hh theorem al_converts {s t : String} {ops : List EditOperation} (h : Converts s t ops) : ∃ k, Al s.toList t.toList k ∧ k ≤ ops.length := by induction h with | nil => exact ⟨0, al_refl _, by simp⟩ | cons op ops hs hr ih => obtain ⟨a, ha, hla⟩ := al_step op hs obtain ⟨b, hb, hlb⟩ := ih obtain ⟨k, hk, hlk⟩ := al_trans ha hb exact ⟨k, hk, by simp only [List.length_cons]; omega⟩ theorem alignment_dominate (s t : String) (ops : List EditOperation) (h : Converts s t ops) : ∃ c ∈ pathCosts s.toList t.toList, c ≤ ops.length := by obtain ⟨k, hk, hl⟩ := al_converts h exact ⟨k, al_mem hk, hl⟩ theorem root_with_sound (sound : ∀ (s t : String) (c : Nat), c ∈ pathCosts s.toList t.toList → ∃ ops, Converts s t ops ∧ ops.length = c) (input : Input) (result : Output) : minDistance_check input result ↔ minDistance_spec input result := by exact root_of_bridges sound alignment_dominate input result /-- On valid input the checker accepts exactly the specified outputs. -/ theorem minDistance_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : minDistance_check input result ↔ minDistance_spec input result := by exact root_of_bridges alignment_sound alignment_dominate input result /-! ### Implementation helpers -/ /-- The prefix-distance table: row `i`, column `j` holds the minimum edit distance between the first `i` characters of `cs1` and the first `j` characters of `cs2`. -/ def editDistanceDP (cs1 cs2 : List Char) : Array (Array Nat) := let n := cs1.length let m := cs2.length let row0 : Array Nat := (List.range (m + 1)).foldl (fun acc j => acc.push j) #[] (List.range n).foldl (fun table i => let prev := table[i]! let row : Array Nat := (List.range m).foldl (fun acc j => let deleteCost := prev[j + 1]! + 1 let insertCost := acc[j]! + 1 let replaceCost := prev[j]! + (if cs1[i]! == cs2[j]! then 0 else 1) acc.push (Nat.min replaceCost (Nat.min deleteCost insertCost))) (#[].push (i + 1)) table.push row) #[row0] /-! ### Main algorithm (impl) -/ /-- Minimum edit distance by dynamic programming over prefix lengths of the two words. -/ def computeEditDistance (input : Input) : Output := let cs1 := input.1.toList let cs2 := input.2.toList let table := editDistanceDP cs1 cs2 (table[cs1.length]!)[cs2.length]! /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem computeEditDistance_correct (input : Input) (h : isValidInput input) : minDistance_spec input (computeEditDistance input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("horse", "ros") #guard isValidInput ("", "") #guard isValidInput ("a", "") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "a")) #guard !(isValidInput ("A", "a")) #guard !(isValidInput ("a", "A")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard minDistance_check ("horse", "ros") 3 #guard minDistance_check ("", "") 0 #guard minDistance_check ("a", "") 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(minDistance_check ("horse", "ros") 2) #guard !(minDistance_check ("", "") 2) #guard !(minDistance_check ("a", "") 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard computeEditDistance ("horse", "ros") == 3 #guard computeEditDistance ("", "") == 0 #guard computeEditDistance ("a", "") == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard minDistance_check ("horse", "ros") (computeEditDistance ("horse", "ros")) #guard minDistance_check ("", "") (computeEditDistance ("", "")) #guard minDistance_check ("a", "") (computeEditDistance ("a", "")) end PEditDistance