import Mathlib /-! # Interleaving String Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2. An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ... Note: a + b is the concatenation of strings a and b. ## Constraints - 0 <= s1.length, s2.length <= 100 - 0 <= s3.length <= 200 - s1, s2, and s3 consist of lowercase English letters. ## Provided examples - `s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"` → `true` - `s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"` → `false` - `s1 = "", s2 = "", s3 = ""` → `true` ## Synthesized negative examples - invalid input: `s1 = "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghija", s2 = "", s3 = ""` ([structural] a predicate that admits 0 <= s1.length, s2.length <= 100. s1 is one past the maximum length) - invalid input: `s1 = "", s2 = "", s3 = "A"` ([structural] a predicate that admits s1, s2, and s3 consist of lowercase English letters.. uppercase in s3; catches a predicate checking only s1 and s2) - invalid input: `s1 = "", s2 = "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghija", s3 = ""` ([structural] a predicate that admits 0 <= s1.length, s2.length <= 100. s2 is one past the maximum length) - `s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"` → `false` is wrong ([structural] only the soundness direction is required: answer true implies interleaving, but completeness is missing. false makes the one-way implication vacuous) - `s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"` → `true` is wrong ([structural] drops the requirement that the order within each string be preserved. s3 is a permutation of s1+s2, so it fits an anagram reading) - `s1 = "", s2 = "", s3 = ""` → `false` is wrong ([structural] empty interleaving base case is not required to be true. false is the trivial rejection for all-empty input) -/ namespace PInterleavingString abbrev Input := (String) × (String) × (String) abbrev Output := Bool /-! ### Specification helpers -/ /-- The alternating concatenation of two lists of blocks, starting with a block of the first list. -/ def interleaveBlocks : List String → List String → String | [], ys => String.join ys | x :: xs, ys => x ++ interleaveBlocks ys xs termination_by xs ys => xs.length + ys.length decreasing_by simp_wf omega /-- `s3` is an interleaving of `s1` and `s2`: both split into nonempty blocks whose counts differ by at most one, and `s3` is the alternating concatenation starting from either side. -/ def IsInterleaving (s1 s2 s3 : String) : Prop := ∃ bs1 bs2 : List String, String.join bs1 = s1 ∧ String.join bs2 = s2 ∧ (∀ b ∈ bs1, b ≠ "") ∧ (∀ b ∈ bs2, b ≠ "") ∧ bs1.length ≤ bs2.length + 1 ∧ bs2.length ≤ bs1.length + 1 ∧ (s3 = interleaveBlocks bs1 bs2 ∨ s3 = interleaveBlocks bs2 bs1) /-! ### Validity predicate (V) -/ /-- Valid input: `s1`, `s2` at most 100 lowercase letters each, `s3` at most 200 lowercase letters. -/ def isValidInput (input : Input) : Bool := input.1.length ≤ 100 && input.2.1.length ≤ 100 && input.2.2.length ≤ 200 && input.1.toList.all (fun c => decide ('a' ≤ c ∧ c ≤ 'z')) && input.2.1.toList.all (fun c => decide ('a' ≤ c ∧ c ≤ 'z')) && input.2.2.toList.all (fun c => decide ('a' ≤ c ∧ c ≤ 'z')) /-! ### Ideal specification (P_spec) -/ /-- `result` holds exactly when `s3` is an interleaving of `s1` and `s2`. -/ def isInterleaving_spec (input : Input) (result : Output) : Prop := result ↔ IsInterleaving input.1 input.2.1 input.2.2 /-! ### Decidable specification (P_check) -/ /-- One Bool per gap between adjacent characters: a choice of cut points. -/ abbrev CutCode (s : String) : Type := Fin (s.length - 1) → Bool /-- The length-`len` substring of `s` starting at `start`. -/ def sliceAt (s : String) (start len : Nat) : String := String.ofList ((s.toList.drop start).take len) /-- Adjacent pairs of a list, `[a, b, c] ↦ [(a, b), (b, c)]`. -/ def consecutivePairs : List Nat → List (Nat × Nat) | a :: b :: xs => (a, b) :: consecutivePairs (b :: xs) | _ => [] /-- The block boundaries selected by `cuts`, including both endpoints. -/ def cutPositions (s : String) (cuts : CutCode s) : List Nat := 0 :: ((List.finRange (s.length - 1)).filterMap (fun i => if cuts i then some (i.val + 1) else none)) ++ [s.length] /-- The split of `s` into nonempty blocks selected by the cut points `cuts`. -/ def decodeBlocks (s : String) (cuts : CutCode s) : List String := if s.length = 0 then [] else (consecutivePairs (cutPositions s cuts)).map (fun (a, b) => sliceAt s a (b - a)) /-- Executable checker for `isInterleaving_spec` over the finite cut codes. -/ def isInterleaving_check (input : Input) (result : Output) : Bool := decide (result ↔ ∃ (c1 : CutCode input.1) (c2 : CutCode input.2.1), let bs1 := decodeBlocks input.1 c1 let bs2 := decodeBlocks input.2.1 c2 bs1.length ≤ bs2.length + 1 ∧ bs2.length ≤ bs1.length + 1 ∧ (input.2.2 = interleaveBlocks bs1 bs2 ∨ input.2.2 = interleaveBlocks bs2 bs1)) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem isInterleaving_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : isInterleaving_check input result ↔ isInterleaving_spec input result := by have selected_order (s : String) (code : CutCode s) : ((List.finRange (s.length-1)).filterMap (fun i => if code i then some (i.val+1) else none)).Pairwise (· < ·) := by apply (List.pairwise_lt_finRange _).filterMap intro a b hab x hx y hy split at hx · split at hy · simp only [Option.some.injEq] at hx hy subst x; subst y exact Nat.add_lt_add_right hab 1 · cases hy · cases hx have positions_order (s : String) (code : CutCode s) (hn : 0 if code i then some (i.val+1) else none)) : 0 sliceAt s x (y-x))) = String.ofList (s.toList.drop a) := by induction xs generalizing a with | nil => contradiction | cons b bs ih => have hab : a have hb : b=s.length := by simpa using he subst b simp only [consecutivePairs,List.map_cons,List.map_nil,String.join_cons,String.join_nil,String.append_empty,sliceAt] congr 1 apply (List.take_eq_self_iff _).mpr simp only [List.length_drop] rfl | cons c cs => have he' : (b::c::cs).getLast?=some s.length := by simpa using he have hj := ih b (by simp) ht he' simp only [consecutivePairs,List.map_cons,String.join_cons] at hj ⊢ rw [hj] apply String.toList_injective simp only [String.toList_append,sliceAt,String.toList_ofList] have hd : (s.toList.drop a).drop (b-a)=s.toList.drop b := by rw [List.drop_drop,Nat.add_sub_of_le (Nat.le_of_lt hab)] rw [←hd,List.take_append_drop] have pieces_nonempty (s : String) (xs : List Nat) (a : Nat) (hs : (a::xs).Pairwise (· < ·)) (hb : ∀x∈a::xs,x ≤ s.length) : ∀p∈(consecutivePairs (a::xs)).map (fun (x,y) => sliceAt s x (y-x)),p≠"" := by induction xs generalizing a with | nil => simp [consecutivePairs] | cons b bs ih => have hab : a hb x (by simp [hx])) cases bs with | nil => simpa [consecutivePairs] using ha | cons c cs => simpa only [consecutivePairs,List.map_cons,List.mem_cons,forall_eq_or_imp] using And.intro ha ht have pairs_scan (a b : Nat) (ns : List Nat) : consecutivePairs (a::ns.scanl (·+·) b) = (a,b)::consecutivePairs (ns.scanl (·+·) b) := by cases ns <;> simp [List.scanl_cons,consecutivePairs] have decode_scan (bs : List (List Char)) (pre : List Char) : (consecutivePairs ((bs.map List.length).scanl (·+·) pre.length)).map (fun (a,b) => sliceAt (String.ofList (pre++bs.flatten)) a (b-a)) = bs.map String.ofList := by induction bs generalizing pre with | nil => simp [consecutivePairs] | cons b bs ih => simp only [List.map_cons,List.scanl_cons,pairs_scan,List.map_cons,List.flatten_cons] apply congrArg₂ List.cons · simp [sliceAt,List.append_assoc] · simpa only [List.length_append,List.append_assoc] using ih (pre++b) have scan_lower (ns : List Nat) (a : Nat) : ∀x∈ns.scanl (·+·) a,a≤x := by induction ns generalizing a with | nil => simp | cons b ns ih => rw [List.scanl_cons] intro x hx rcases List.mem_cons.mp hx with rfl|hx · exact le_rfl · have := ih (a+b) x hx; omega have scan_order (ns : List Nat) (a : Nat) (hn : ∀n∈ns,0 simp | cons b ns ih => rw [List.scanl_cons] apply List.pairwise_cons.mpr refine ⟨?_,ih _ (fun n hn' => hn n (by simp [hn']))⟩ intro x hx have := scan_lower ns (a+b) x hx have := hn b (by simp) omega have scan_last (ns : List Nat) (a : Nat) : (ns.scanl (·+·) a).getLast?=some (a+ns.sum) := by rw [List.getLast?_scanl] congr 1 induction ns generalizing a with | nil => simp | cons b ns ih => simp [ih,Nat.add_assoc] have scan_head (ns : List Nat) (a : Nat) : (ns.scanl (·+·) a).head?=some a := by cases ns <;> simp [List.scanl_cons,consecutivePairs] have join_length (bs : List String) : (String.join bs).length=(bs.map String.length).sum := by induction bs with | nil => simp | cons b bs ih => simp [String.join_cons,ih] have encode_inner (s : String) (xs : List Nat) (ho : xs.Pairwise (·<·)) (hb : ∀x∈xs,0 decide (i.val+1∈xs) refine ⟨code,?_⟩ unfold cutPositions have he : ((List.finRange (s.length-1)).filterMap (fun i => if code i then some (i.val+1) else none))=xs := by apply (selected_order s code).eq_of_mem_iff ho intro x constructor · intro hx obtain ⟨i,_,hi⟩ := List.mem_filterMap.mp hx split at hi <;> rename_i hc · have he : i.val+1=x := Option.some.inj hi have hm : i.val+1∈xs := of_decide_eq_true hc exact he ▸ hm · cases hi · intro hx obtain ⟨hl,hu⟩ := hb x hx let i : Fin (s.length-1) := ⟨x-1,by omega⟩ have hi : i.val+1=x := by dsimp [i]; omega apply List.mem_filterMap.mpr refine ⟨i,List.mem_finRange i,?_⟩ simp [code,hi,hx] rw [he] have decode_sound (s : String) (code : CutCode s) : String.join (decodeBlocks s code)=s ∧ ∀b∈decodeBlocks s code,b≠"" := by by_cases hn : s.length=0 · have hs : s="" := String.length_eq_zero_iff.mp hn simp [decodeBlocks,hn,hs] let xs := (List.finRange (s.length-1)).filterMap (fun i => if code i then some (i.val+1) else none) have ho := positions_order s code (by omega) have he : (cutPositions s code).getLast?=some s.length := List.getLast?_eq_some_iff.mpr ⟨0::xs,rfl⟩ have hb : ∀x∈cutPositions s code,x ≤ s.length := by have hh := (List.pairwise_append.mp ho).2.2 intro x hx rcases List.mem_append.mp hx with hx|hx · exact Nat.le_of_lt (hh x hx s.length (by simp)) · have heq : x=s.length := by simpa using hx omega have hj := pieces_join s (xs++[s.length]) 0 (by simp) ho he have hp := pieces_nonempty s (xs++[s.length]) 0 ho hb simp only [decodeBlocks,hn,ite_false] exact ⟨by simpa only [cutPositions,xs,List.drop_zero,String.ofList_toList,List.cons_append] using hj,hp⟩ have decode_complete (s : String) (bs : List String) (hj : String.join bs=s) (hb : ∀b∈bs,b≠"") : ∃code : CutCode s,decodeBlocks s code=bs := by cases bs with | nil => have hs : s="" := by simpa using hj.symm subst s exact ⟨fun _ => false,rfl⟩ | cons b bs => have hb0 := hb b (by simp) have hbpos : 0 have hlen := congrArg List.length he simp [ns] at hlen | cons a xs => have hhead := scan_head ns 0 rw [he] at hhead have ha : a=0 := by simpa using hhead subst a have hp : (0::xs++[s.length]).Pairwise (·<·) := he ▸ ho have hin := (List.pairwise_append.mp (List.pairwise_cons.mp hp).2).1 have hbounds : ∀x∈xs,0