import Mathlib /-! # Scramble String We can scramble a string s to get a string t using the following algorithm: If the length of the string is 1, stop. If the length of the string is > 1, do the following: Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y. Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x. Apply step 1 recursively on each of the two substrings x and y. Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false. ## Constraints - s1.length == s2.length - 1 <= s1.length <= 30 - s1 and s2 consist of lowercase English letters. ## Provided examples - `s1 = "great", s2 = "rgeat"` → `true` - `s1 = "abcde", s2 = "caebd"` → `false` - `s1 = "a", s2 = "a"` → `true` ## Synthesized negative examples - invalid input: `s1 = "a", s2 = "ab"` ([structural] a predicate that admits s1.length == s2.length. lengths differ; a predicate checking each string alone accepts it) - invalid input: `s1 = "", s2 = ""` ([structural] a predicate that admits 1 <= s1.length <= 30. empty string below the minimum length) - invalid input: `s1 = "A", s2 = "a"` ([structural] a predicate that admits s1 and s2 consist of lowercase English letters.. uppercase in s1; a case-insensitive predicate accepts it) - `s1 = "great", s2 = "rgeat"` → `false` is wrong ([structural] identity-only reading accepts false for any non-identical pair. identity-only check rejects a valid scramble) - `s1 = "abcde", s2 = "caebd"` → `true` is wrong ([structural] only character counts are required, not the recursive scramble relation. caebd is an anagram of abcde) - `s1 = "a", s2 = "a"` → `false` is wrong ([structural] base-case equality is dropped. for length 1, no split exists, so false is the only defined result) -/ namespace PScrambleString abbrev Input := (String) × (String) abbrev Output := Bool /-! ### Specification helpers -/ /-- `t` is a scramble of `s`: equal at length one, and at greater lengths there is a split at some `i` with the two halves scrambled in matching order or in swapped order. -/ inductive IsScramble : String → String → Prop | base {s t : String} : s.length = 1 → s = t → IsScramble s t | same {s t : String} (i : Nat) : 0 < i → i < s.length → s.length = t.length → IsScramble (s.take i).copy (t.take i).copy → IsScramble (s.drop i).copy (t.drop i).copy → IsScramble s t | swap {s t : String} (i : Nat) : 0 < i → i < s.length → s.length = t.length → IsScramble (s.take i).copy (t.drop (t.length - i)).copy → IsScramble (s.drop i).copy (t.take (t.length - i)).copy → IsScramble s t /-! ### Validity predicate (V) -/ /-- Valid input: two strings of equal length between 1 and 30, both consisting only of lowercase English letters. -/ def isValidInput (input : Input) : Bool := input.1.length == input.2.length && 1 ≤ input.1.length && input.1.length ≤ 30 && input.1.toList.all (fun c => 'a' ≤ c && c ≤ 'z') && input.2.toList.all (fun c => 'a' ≤ c && c ≤ 'z') /-! ### Ideal specification (P_spec) -/ /-- The answer is `true` exactly when `input.2` is a scramble of `input.1`. -/ def isScramble_spec (input : Input) (result : Output) : Prop := result ↔ IsScramble input.1 input.2 /-! ### Decidable specification (P_check) -/ /-- Fuel-bounded decidable scramble test: equality at length one, otherwise some proper split with the halves scrambled in matching order or in swapped order, mirroring `IsScramble`. -/ def scrambleFuel : Nat → String → String → Bool | 0, _, _ => false | fuel + 1, s, t => if s.length == 1 then s == t else if s.length != t.length then false else (List.range s.length).any fun i => if 0 < i && i < s.length then (scrambleFuel fuel (s.take i).copy (t.take i).copy && scrambleFuel fuel (s.drop i).copy (t.drop i).copy) || (scrambleFuel fuel (s.take i).copy (t.drop (t.length - i)).copy && scrambleFuel fuel (s.drop i).copy (t.take (t.length - i)).copy) else false /-- Executable checker for `isScramble_spec`: `result` must equal the fuel-bounded scramble test on the input pair. -/ def isScramble_check (input : Input) (result : Output) : Bool := result == scrambleFuel (input.1.length + 1) input.1 input.2 theorem root_of_bridges (bridge : ∀ (fuel : Nat) (s t : String), s.length < fuel → (scrambleFuel fuel s t = true ↔ IsScramble s t)) (input : Input) (result : Output) : isScramble_check input result ↔ isScramble_spec input result := by have hb := bridge (input.1.length + 1) input.1 input.2 (by omega) simp only [isScramble_check, isScramble_spec, beq_iff_eq] cases result <;> cases hf : scrambleFuel (input.1.length + 1) input.1 input.2 <;> simp_all theorem fuel_sound (fuel : Nat) (s t : String) (h : scrambleFuel fuel s t = true) : IsScramble s t := by induction fuel generalizing s t with | zero => simp [scrambleFuel] at h | succ fuel ih => simp only [scrambleFuel] at h split at h · rename_i hs exact IsScramble.base (by simpa using hs) (by simpa using h) · split at h · simp at h · rename_i hs ht have hlen : s.length = t.length := by simpa using ht simp only [List.any_eq_true, List.mem_range] at h obtain ⟨i, hi, h⟩ := h split at h · rename_i hb have hib : 0 < i ∧ i < s.length := by simpa using hb simp only [Bool.or_eq_true, Bool.and_eq_true] at h rcases h with ⟨h₁, h₂⟩ | ⟨h₁, h₂⟩ · exact IsScramble.same i hib.1 hib.2 hlen (ih _ _ h₁) (ih _ _ h₂) · exact IsScramble.swap i hib.1 hib.2 hlen (ih _ _ h₁) (ih _ _ h₂) · simp at h theorem take_length (s : String) (i : Nat) : (s.take i).copy.length = min i s.length := by simpa only [String.length_toList, String.toList_copy_take, List.length_take] using (String.length_toList (s := (s.take i).copy)).symm theorem drop_length (s : String) (i : Nat) : (s.drop i).copy.length = s.length - i := by simpa only [String.length_toList, String.toList_copy_drop, List.length_drop] using (String.length_toList (s := (s.drop i).copy)).symm theorem fuel_complete (s t : String) (h : IsScramble s t) (fuel : Nat) (hf : s.length < fuel) : scrambleFuel fuel s t = true := by induction h generalizing fuel with | @base s t hs he => cases fuel with | zero => omega | succ fuel => subst t simp [scrambleFuel, hs] | @same s t i hi hi' hlen h₁ h₂ ih₁ ih₂ => cases fuel with | zero => omega | succ fuel => have hs : (s.length == 1) = false := by simp; omega have ht : (s.length != t.length) = false := by simp [hlen] rw [scrambleFuel, hs, ht] simp only [Bool.false_eq_true, if_false, List.any_eq_true] refine ⟨i, List.mem_range.mpr hi', ?_⟩ have hl : (s.take i).copy.length < fuel := by rw [take_length]; omega have hr : (s.drop i).copy.length < fuel := by rw [drop_length]; omega simp [hi, hi', ih₁ fuel hl, ih₂ fuel hr] | @swap s t i hi hi' hlen h₁ h₂ ih₁ ih₂ => cases fuel with | zero => omega | succ fuel => have hs : (s.length == 1) = false := by simp; omega have ht : (s.length != t.length) = false := by simp [hlen] rw [scrambleFuel, hs, ht] simp only [Bool.false_eq_true, if_false, List.any_eq_true] refine ⟨i, List.mem_range.mpr hi', ?_⟩ have hl : (s.take i).copy.length < fuel := by rw [take_length]; omega have hr : (s.drop i).copy.length < fuel := by rw [drop_length]; omega simp [hi, hi', ih₁ fuel hl, ih₂ fuel hr] theorem fuel_iff (fuel : Nat) (s t : String) (hf : s.length < fuel) : scrambleFuel fuel s t = true ↔ IsScramble s t := ⟨fuel_sound fuel s t, fun h => fuel_complete s t h fuel hf⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem isScramble_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : isScramble_check input result ↔ isScramble_spec input result := by exact root_of_bridges fuel_iff input result /-! ### Implementation helpers -/ /-- Fills the table `dp[i][j][l]`: true when the length-`l` slice of `a1` starting at `i` scrambles to the length-`l` slice of `a2` starting at `j`. -/ def buildScrambleTable (a1 a2 : Array Char) : Array (Array (Array Bool)) := let n := a1.size (List.range (n + 1)).foldl (fun dp l => if l = 0 then dp else (List.range (n + 1)).foldl (fun dp i => if n < i + l then dp else (List.range (n + 1)).foldl (fun dp j => if n < j + l then dp else let v : Bool := if l = 1 then a1[i]! == a2[j]! else (List.range l).any fun k => if 0 < k && k < l then (((dp[i]!)[j]!)[k]! && ((dp[i + k]!)[j + k]!)[l - k]!) || (((dp[i]!)[j + l - k]!)[k]! && ((dp[i + k]!)[j]!)[l - k]!) else false dp.set! i ((dp[i]!).set! j (((dp[i]!)[j]!).set! l v))) dp) dp) (Array.replicate (n + 1) (Array.replicate (n + 1) (Array.replicate (n + 1) false))) /-! ### Main algorithm (impl) -/ /-- Decides the scramble relation by memoized dynamic programming over substrings in O(n^4) time. -/ def checkScramble (input : Input) : Output := let a1 := input.1.toList.toArray let a2 := input.2.toList.toArray if a2.size != a1.size then false else (((buildScrambleTable a1 a2)[0]!)[0]!)[a1.size]! /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem checkScramble_correct (input : Input) (h : isValidInput input) : isScramble_spec input (checkScramble input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("great", "rgeat") #guard isValidInput ("abcde", "caebd") #guard isValidInput ("a", "a") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("a", "ab")) #guard !(isValidInput ("", "")) #guard !(isValidInput ("A", "a")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard isScramble_check ("great", "rgeat") true #guard isScramble_check ("abcde", "caebd") false #guard isScramble_check ("a", "a") true /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(isScramble_check ("great", "rgeat") false) #guard !(isScramble_check ("abcde", "caebd") true) #guard !(isScramble_check ("a", "a") false) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard checkScramble ("great", "rgeat") == true #guard checkScramble ("abcde", "caebd") == false #guard checkScramble ("a", "a") == true /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard isScramble_check ("great", "rgeat") (checkScramble ("great", "rgeat")) #guard isScramble_check ("abcde", "caebd") (checkScramble ("abcde", "caebd")) #guard isScramble_check ("a", "a") (checkScramble ("a", "a")) end PScrambleString