import Mathlib /-! # Remove Outermost Parentheses A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation. For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings. A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings. Given a valid parentheses string s, consider its primitive decomposition: s = P_1 + P_2 + ... + P_k, where P_i are primitive valid parentheses strings. Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s. ## Constraints - 1 <= s.length <= 10^5 - s[i] is either '(' or ')'. - s is a valid parentheses string. ## Provided examples - `s = "(()())(())"` → `"()()()"` - `s = "()()"` → `""` - `s = "(())"` → `"()"` ## Synthesized negative examples - invalid input: `s = ""` ([structural] a predicate that admits 1 <= s.length <= 10^5. empty under minimum length; a predicate accepting the grammar's empty case misses it) - invalid input: `s = "[]"` ([structural] a predicate that admits s[i] is either '(' or ')'.. square brackets outside the stated alphabet; a generic bracket matcher accepts it) - invalid input: `s = "("` ([structural] a predicate that admits s is a valid parentheses string.. unbalanced opening parenthesis; a predicate checking only the alphabet accepts it) - `s = "(()())(())"` → `"()()(())"` is wrong ([structural] every primitive requirement weakened to all but the last. leaves the second primitive intact) - `s = "()()"` → `"()()"` is wrong ([structural] answer may equal the input. No removal is required by this reading.) - `s = "(())"` → `""` is wrong ([structural] no clause ties the output to the input. amended 2026-08-18 alongside its base positive) -/ namespace PRemoveOutermostParentheses abbrev Input := String abbrev Output := String /-! ### Specification helpers -/ /-- Running balance of a character list: `'('` counts +1, `')'` counts -1. -/ def parenBalance (l : List Char) : Int := l.foldl (fun acc c => acc + (if c = '(' then (1 : Int) else if c = ')' then -1 else 0)) 0 /-- `s` is a valid parentheses string: total balance zero and every prefix balance nonnegative. -/ def IsValidParens (s : String) : Prop := parenBalance s.toList = 0 ∧ ∀ i : ℕ, 0 ≤ parenBalance (s.toList.take i) /-- `s` is primitive: a nonempty valid parentheses string that cannot be split into two nonempty valid parentheses strings. -/ def IsPrimitive (s : String) : Prop := s ≠ "" ∧ IsValidParens s ∧ ¬∃ a b : String, a ≠ "" ∧ b ≠ "" ∧ IsValidParens a ∧ IsValidParens b ∧ a ++ b = s /-- `t` is what the primitive block `P` leaves after deleting its outermost parentheses. -/ def IsInnerOfPrimitive (P t : String) : Prop := IsPrimitive P ∧ P = "(" ++ t ++ ")" /-- Boolean scan: the running balance of `s` never goes negative and ends at zero. -/ def isBalancedParens (s : String) : Bool := let r := s.toList.foldl (fun (p : Int × Bool) c => let bal := p.1 + (if c = '(' then (1 : Int) else -1) (bal, p.2 && 0 ≤ bal)) ((0 : Int), true) r.2 && r.1 = 0 /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty valid parentheses string of at most 10^5 characters from `'('` and `')'`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10 ^ 5 && input.toList.all (fun c => c = '(' || c = ')') && isBalancedParens input /-! ### Ideal specification (P_spec) -/ /-- `result` is `input` with the outermost parentheses of every block of its primitive decomposition removed. -/ def removeOutermostParentheses_spec (input : Input) (result : Output) : Prop := ∃ blocks : List String, ∃ inners : List String, List.Forall₂ IsInnerOfPrimitive blocks inners ∧ String.join blocks = input ∧ String.join inners = result /-! ### 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 sliceString (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 := if s.length = 0 then [0] else 0 :: ((List.finRange (s.length - 1)).filterMap (fun i => if cuts i then some (i.val + 1) else none)) ++ [s.length] /-- The blocks of `s` 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) => sliceString s a (b - a)) /-- `P` with its first and last character removed: the inner string of a primitive block. -/ def stripOuter (P : String) : String := String.ofList ((P.toList.drop 1).dropLast) /-- Executable primitivity: nonempty, balanced, and the balance never returns to zero before the end. -/ def isPrimitiveBlock (P : String) : Bool := let len := P.length let r := P.toList.foldl (fun (p : Int × Nat × Bool) c => let bal := p.1 + (if c = '(' then (1 : Int) else -1) let pos := p.2.1 + 1 let ok := p.2.2 && (if pos < len then 0 < bal else bal = 0) (bal, pos, ok)) ((0 : Int), 0, true) len != 0 && r.2.2 /-- Executable checker for `removeOutermostParentheses_spec` over the finite `cutCode`. -/ def removeOutermostParentheses_check (input : Input) (result : Output) : Bool := decide (∃ cuts : cutCode input, (decodeBlocks input cuts).all isPrimitiveBlock = true ∧ String.join (decodeBlocks input cuts) = input ∧ String.join ((decodeBlocks input cuts).map stripOuter) = result) /-! ### Added: balance helpers -/ theorem rop_foldl_init (f : Char → Int) : ∀ (l : List Char) (a : Int), l.foldl (fun acc c => acc + f c) a = a + l.foldl (fun acc c => acc + f c) 0 := by intro l induction l with | nil => intro a; simp | cons c t ih => intro a simp only [List.foldl_cons] rw [ih (a + f c), ih (0 + f c)] ring theorem rop_parenBalance_cons (c : Char) (l : List Char) : parenBalance (c :: l) = (if c = '(' then (1 : Int) else if c = ')' then -1 else 0) + parenBalance l := by unfold parenBalance rw [List.foldl_cons, rop_foldl_init] ring theorem rop_parenBalance_append (a b : List Char) : parenBalance (a ++ b) = parenBalance a + parenBalance b := by induction a with | nil => simp [parenBalance] | cons c t ih => rw [List.cons_append, rop_parenBalance_cons, ih, rop_parenBalance_cons] ring /-- The checker's balance: every non-`'('` character counts `-1`. -/ def rop_cbal : List Char → Int | [] => 0 | c :: l => (if c = '(' then (1 : Int) else -1) + rop_cbal l theorem rop_cbal_cons (c : Char) (l : List Char) : rop_cbal (c :: l) = (if c = '(' then (1 : Int) else -1) + rop_cbal l := rfl theorem rop_cbal_append (a b : List Char) : rop_cbal (a ++ b) = rop_cbal a + rop_cbal b := by induction a with | nil => simp [rop_cbal] | cons c t ih => rw [List.cons_append, rop_cbal_cons, ih, rop_cbal_cons] ring theorem rop_parenBalance_eq_cbal (l : List Char) (h : ∀ c ∈ l, c = '(' ∨ c = ')') : parenBalance l = rop_cbal l := by revert h induction l with | nil => intro _; simp [parenBalance, rop_cbal] | cons c t ih => intro h rw [rop_parenBalance_cons, rop_cbal_cons, ih (fun x hx => h x (by simp [hx]))] rcases h c (by simp) with hc | hc <;> simp [hc] /-! ### Added: the primitivity scan -/ /-- The step function of `isPrimitiveBlock`'s fold, named so it can be reasoned about. -/ def rop_step (len : Nat) (p : Int × Nat × Bool) (c : Char) : Int × Nat × Bool := let bal := p.1 + (if c = '(' then (1 : Int) else -1) let pos := p.2.1 + 1 let ok := p.2.2 && (if pos < len then 0 < bal else bal = 0) (bal, pos, ok) theorem rop_isPrimitiveBlock_eq (P : String) : isPrimitiveBlock P = (P.length != 0 && (P.toList.foldl (rop_step P.length) ((0 : Int), 0, true)).2.2) := rfl theorem rop_ite_decide_true (c : Prop) [Decidable c] (A B : Prop) [Decidable A] [Decidable B] : ((if c then decide A else decide B) = true) ↔ (if c then A else B) := by by_cases h : c <;> simp [h] theorem rop_fold_spec (len : Nat) : ∀ (l : List Char) (b : Int) (n : Nat) (o : Bool), (l.foldl (rop_step len) (b, n, o)).1 = b + rop_cbal l ∧ (l.foldl (rop_step len) (b, n, o)).2.1 = n + l.length ∧ ((l.foldl (rop_step len) (b, n, o)).2.2 = true ↔ (o = true ∧ ∀ k, 1 ≤ k → k ≤ l.length → (if n + k < len then 0 < b + rop_cbal (l.take k) else b + rop_cbal (l.take k) = 0))) := by intro l induction l with | nil => intro b n o refine ⟨by simp [rop_cbal], by simp, ?_⟩ simp only [List.foldl_nil, List.length_nil] constructor · intro ho refine ⟨ho, ?_⟩ intro k hk1 hk2 exact absurd hk1 (by omega) · intro hp; exact hp.1 | cons c t ih => intro b n o have hstep : List.foldl (rop_step len) (b, n, o) (c :: t) = List.foldl (rop_step len) (b + (if c = '(' then (1 : Int) else -1), n + 1, o && (if n + 1 < len then decide (0 < b + (if c = '(' then (1 : Int) else -1)) else decide (b + (if c = '(' then (1 : Int) else -1) = 0))) t := rfl obtain ⟨ih1, ih2, ih3⟩ := ih (b + (if c = '(' then (1 : Int) else -1)) (n + 1) (o && (if n + 1 < len then decide (0 < b + (if c = '(' then (1 : Int) else -1)) else decide (b + (if c = '(' then (1 : Int) else -1) = 0))) have hbridge : ∀ j : Nat, ((if n + (j + 1) < len then 0 < b + rop_cbal ((c :: t).take (j + 1)) else b + rop_cbal ((c :: t).take (j + 1)) = 0) ↔ (if n + 1 + j < len then 0 < b + (if c = '(' then (1 : Int) else -1) + rop_cbal (t.take j) else b + (if c = '(' then (1 : Int) else -1) + rop_cbal (t.take j) = 0)) := by intro j rw [List.take_succ_cons, rop_cbal_cons] have harith : n + (j + 1) = n + 1 + j := by omega rw [harith] have hassoc : b + ((if c = '(' then (1 : Int) else -1) + rop_cbal (t.take j)) = b + (if c = '(' then (1 : Int) else -1) + rop_cbal (t.take j) := by ring rw [hassoc] rw [hstep] refine ⟨?_, ?_, ?_⟩ · rw [ih1, rop_cbal_cons]; ring · rw [ih2, List.length_cons]; omega · rw [ih3, Bool.and_eq_true, rop_ite_decide_true] constructor · rintro ⟨⟨ho, hhead⟩, hall⟩ refine ⟨ho, ?_⟩ intro k hk1 hk2 obtain ⟨j, rfl⟩ : ∃ j, k = j + 1 := ⟨k - 1, by omega⟩ rw [hbridge j] rcases Nat.eq_zero_or_pos j with rfl | hj · simpa [rop_cbal] using hhead · exact hall j hj (by simp only [List.length_cons] at hk2; omega) · rintro ⟨ho, hall⟩ refine ⟨⟨ho, ?_⟩, ?_⟩ · have h0 := (hbridge 0).mp (hall (0 + 1) (by omega) (by simp)) simpa [rop_cbal] using h0 · intro j hj1 hj2 exact (hbridge j).mp (hall (j + 1) (by omega) (by simp only [List.length_cons]; omega)) /-- The content of `isPrimitiveBlock`, read off the scan. -/ def rop_Core (l : List Char) : Prop := l ≠ [] ∧ (∀ k, 1 ≤ k → k < l.length → 0 < rop_cbal (l.take k)) ∧ rop_cbal l = 0 theorem rop_isPrimitiveBlock_iff_core (P : String) : isPrimitiveBlock P = true ↔ rop_Core P.toList := by have hlen : P.toList.length = P.length := String.length_toList obtain ⟨-, -, h3⟩ := rop_fold_spec P.length P.toList 0 0 true rw [rop_isPrimitiveBlock_eq, Bool.and_eq_true, bne_iff_ne, ne_eq, h3] unfold rop_Core constructor · rintro ⟨hne, -, hall⟩ refine ⟨?_, ?_, ?_⟩ · intro he exact hne (by rw [← hlen, he]; rfl) · intro k hk1 hk2 have := hall k hk1 (by omega) rw [if_pos (by omega)] at this simpa using this · have := hall P.toList.length (by omega) le_rfl rw [if_neg (by omega), List.take_length] at this simpa using this · rintro ⟨hne, hpos, hzero⟩ refine ⟨?_, rfl, ?_⟩ · intro he exact hne (by rw [← hlen] at he; exact List.eq_nil_of_length_eq_zero he) · intro k hk1 hk2 rcases (by omega : k < P.toList.length ∨ k = P.toList.length) with hlt | heq · rw [if_pos (by omega)] simpa using hpos k hk1 hlt · rw [if_neg (by omega), heq, List.take_length] simpa using hzero /-- `IsValidParens` at the character-list level. -/ def rop_VP (l : List Char) : Prop := parenBalance l = 0 ∧ ∀ i : ℕ, 0 ≤ parenBalance (l.take i) theorem rop_toList_paren (x : String) : ("(" ++ x ++ ")").toList = '(' :: (x.toList ++ [')']) := by simp [String.toList_append, show ("(" : String).toList = ['('] from rfl, show (")" : String).toList = [')'] from rfl] theorem rop_toList_eq_nil (x : String) : x.toList = [] ↔ x = "" := by constructor · intro hx; exact String.toList_injective (s₂ := "") hx · intro hx; subst hx; rfl theorem rop_ofList_eq_empty (u : List Char) : String.ofList u = "" ↔ u = [] := by rw [← rop_toList_eq_nil, String.toList_ofList] theorem rop_isPrimitive_iff (s : String) : IsPrimitive s ↔ (s.toList ≠ [] ∧ rop_VP s.toList ∧ ¬ ∃ u v : List Char, u ≠ [] ∧ v ≠ [] ∧ rop_VP u ∧ rop_VP v ∧ u ++ v = s.toList) := by have hV : ∀ x : String, IsValidParens x ↔ rop_VP x.toList := fun _ => Iff.rfl unfold IsPrimitive constructor · rintro ⟨h1, h2, h3⟩ refine ⟨fun he => h1 ((rop_toList_eq_nil s).mp he), (hV s).mp h2, ?_⟩ rintro ⟨u, v, hu, hv, hvu, hvv, huv⟩ refine h3 ⟨String.ofList u, String.ofList v, ?_, ?_, ?_, ?_, ?_⟩ · exact fun he => hu ((rop_ofList_eq_empty u).mp he) · exact fun he => hv ((rop_ofList_eq_empty v).mp he) · rw [hV, String.toList_ofList]; exact hvu · rw [hV, String.toList_ofList]; exact hvv · rw [← String.ofList_append, huv, String.ofList_toList] · rintro ⟨h1, h2, h3⟩ refine ⟨fun he => h1 ((rop_toList_eq_nil s).mpr he), (hV s).mpr h2, ?_⟩ rintro ⟨a, b, ha, hb, hva, hvb, hab⟩ refine h3 ⟨a.toList, b.toList, ?_, ?_, (hV a).mp hva, (hV b).mp hvb, ?_⟩ · exact fun he => ha ((rop_toList_eq_nil a).mp he) · exact fun he => hb ((rop_toList_eq_nil b).mp he) · rw [← String.toList_append, hab] theorem rop_core_iff_prim (l : List Char) (hall : ∀ c ∈ l, c = '(' ∨ c = ')') : rop_Core l ↔ (l ≠ [] ∧ rop_VP l ∧ ¬ ∃ u v : List Char, u ≠ [] ∧ v ≠ [] ∧ rop_VP u ∧ rop_VP v ∧ u ++ v = l) := by have htk : ∀ k : Nat, parenBalance (l.take k) = rop_cbal (l.take k) := fun k => rop_parenBalance_eq_cbal _ (fun c hc => hall c (List.mem_of_mem_take hc)) have hfull : parenBalance l = rop_cbal l := rop_parenBalance_eq_cbal l hall unfold rop_Core constructor · rintro ⟨hne, hpos, hzero⟩ have hVP : rop_VP l := by refine ⟨by rw [hfull]; exact hzero, ?_⟩ intro i rw [htk i] rcases Nat.lt_or_ge i l.length with hi | hi · rcases Nat.eq_zero_or_pos i with rfl | hip · simp [rop_cbal] · exact le_of_lt (hpos i hip hi) · rw [List.take_of_length_le hi, ← hfull, ← List.take_of_length_le hi, htk] exact le_of_eq (by rw [List.take_of_length_le hi]; exact hzero.symm) refine ⟨hne, hVP, ?_⟩ rintro ⟨u, v, hu, hv, hvu, hvv, huv⟩ have hulen : 0 < u.length := List.length_pos_iff.mpr hu have hvlen : 0 < v.length := List.length_pos_iff.mpr hv have hlen : l.length = u.length + v.length := by rw [← huv, List.length_append] have htake : l.take u.length = u := by rw [← huv]; exact List.take_left' rfl have h1 := hpos u.length hulen (by omega) rw [← htk, htake, hvu.1] at h1 omega · rintro ⟨hne, hVP, hsplit⟩ refine ⟨hne, ?_, by rw [← hfull]; exact hVP.1⟩ intro k hk1 hk2 rw [← htk] rcases lt_or_eq_of_le (hVP.2 k) with hlt | heq · exact hlt · exfalso apply hsplit have hne1 : l.take k ≠ [] := List.length_pos_iff.mp (by rw [List.length_take]; omega) have hne2 : l.drop k ≠ [] := List.length_pos_iff.mp (by rw [List.length_drop]; omega) have ht : rop_VP (l.take k) := by refine ⟨heq.symm, ?_⟩ intro i rw [List.take_take] exact hVP.2 (min i k) have hd : rop_VP (l.drop k) := by constructor · have h1 : parenBalance (l.take k ++ l.drop k) = parenBalance (l.take k) + parenBalance (l.drop k) := rop_parenBalance_append _ _ rw [List.take_append_drop] at h1 rw [hVP.1, ← heq] at h1 omega · intro i have h2 : parenBalance (l.take (k + i)) = parenBalance (l.take k) + parenBalance ((l.drop k).take i) := by rw [List.take_add, rop_parenBalance_append] have h3 := hVP.2 (k + i) rw [h2, ← heq] at h3 omega exact ⟨l.take k, l.drop k, hne1, hne2, ht, hd, List.take_append_drop k l⟩ theorem rop_prim_iff (P : String) (hall : ∀ c ∈ P.toList, c = '(' ∨ c = ')') : isPrimitiveBlock P = true ↔ IsPrimitive P := (rop_isPrimitiveBlock_iff_core P).trans ((rop_core_iff_prim P.toList hall).trans (rop_isPrimitive_iff P).symm) theorem rop_core_outer (P : String) (hall : ∀ c ∈ P.toList, c = '(' ∨ c = ')') (hc : rop_Core P.toList) : P = "(" ++ stripOuter P ++ ")" := by obtain ⟨hne, hpos, hzero⟩ := hc cases hL : P.toList with | nil => exact absurd hL hne | cons c t => rw [hL] at hall hne hpos hzero have htne : t ≠ [] := by intro he rw [he] at hzero rcases hall c (by simp) with hcc | hcc <;> rw [hcc] at hzero <;> simp [rop_cbal] at hzero have htl : 0 < t.length := List.length_pos_iff.mpr htne have hsplit : t = t.dropLast ++ [t.getLast htne] := (List.dropLast_concat_getLast htne).symm have hcons : c :: t = (c :: t.dropLast) ++ [t.getLast htne] := by conv_lhs => rw [hsplit] rfl have hc1 : c = '(' := by have h1 := hpos 1 (le_refl 1) (by simp only [List.length_cons]; omega) have h2 : (c :: t).take 1 = [c] := rfl rw [h2] at h1 rcases hall c (by simp) with hcc | hcc · exact hcc · exfalso rw [hcc] at h1 have hv : rop_cbal [(')' : Char)] = -1 := by simp [rop_cbal] rw [hv] at h1 omega have hcl : (c :: t.dropLast).length = t.length := by rw [List.length_cons, List.length_dropLast] omega have h1 : 0 < rop_cbal (c :: t.dropLast) := by have h0 := hpos t.length htl (by simp only [List.length_cons]; omega) have h2 : (c :: t).take t.length = c :: t.dropLast := by conv_lhs => rw [hcons] exact List.take_left' hcl rw [h2] at h0 exact h0 have h3 : rop_cbal (c :: t) = rop_cbal (c :: t.dropLast) + rop_cbal [t.getLast htne] := by conv_lhs => rw [hcons] rw [rop_cbal_append] rw [h3] at hzero have hxmem : t.getLast htne ∈ c :: t := List.mem_cons_of_mem c (List.getLast_mem htne) have hx1 : t.getLast htne = ')' := by rcases hall _ hxmem with hxx | hxx · exfalso rw [hxx] at hzero have hv : rop_cbal [('(' : Char)] = 1 := by simp [rop_cbal] rw [hv] at hzero omega · exact hxx have hs : (stripOuter P).toList = t.dropLast := by unfold stripOuter rw [String.toList_ofList, hL] rfl have hfinal : c :: t = '(' :: (t.dropLast ++ [')']) := by rw [hc1, ← hx1] exact congrArg (List.cons '(') hsplit apply String.toList_injective rw [rop_toList_paren, hs, hL] exact hfinal theorem rop_stripOuter_eq (t : String) : stripOuter ("(" ++ t ++ ")") = t := by unfold stripOuter rw [rop_toList_paren] have h2 : (('(' : Char) :: (t.toList ++ [')'])).drop 1 = t.toList ++ [')'] := rfl rw [h2, List.dropLast_concat, String.ofList_toList] /-! ### Added: decoding a cut code into blocks -/ def rop_blocksOf (xs : List Char) : Nat → List Nat → List (List Char) | _, [] => [] | a, p :: ps => (xs.drop a).take (p - a) :: rop_blocksOf xs p ps def rop_interiorOf : Nat → List (List Char) → List Nat | _, [] => [] | a, b :: t => if t.isEmpty then [] else (a + b.length) :: rop_interiorOf (a + b.length) t theorem rop_blocksOf_nil (xs : List Char) (a : Nat) : rop_blocksOf xs a [] = [] := rfl theorem rop_blocksOf_cons (xs : List Char) (a p : Nat) (ps : List Nat) : rop_blocksOf xs a (p :: ps) = (xs.drop a).take (p - a) :: rop_blocksOf xs p ps := rfl theorem rop_interiorOf_single (a : Nat) (b : List Char) : rop_interiorOf a [b] = [] := rfl theorem rop_interiorOf_cons (a : Nat) (b c : List Char) (t : List (List Char)) : rop_interiorOf a (b :: c :: t) = (a + b.length) :: rop_interiorOf (a + b.length) (c :: t) := rfl theorem rop_decode_blocksOf (s : String) (a : Nat) (ps : List Nat) : (consecutivePairs (a :: ps)).map (fun (x, y) => sliceString s x (y - x)) = (rop_blocksOf s.toList a ps).map String.ofList := by induction ps generalizing a with | nil => rfl | cons p ps ih => show ((a, p) :: consecutivePairs (p :: ps)).map _ = _ rw [List.map_cons, ih p, rop_blocksOf_cons, List.map_cons] rfl theorem rop_blocksOf_interiorOf (xs : List Char) : ∀ (bs : List (List Char)) (a : Nat), bs ≠ [] → xs.drop a = bs.flatten → rop_blocksOf xs a (rop_interiorOf a bs ++ [a + bs.flatten.length]) = bs := by intro bs induction bs with | nil => intro a hne _; exact absurd rfl hne | cons b t ih => intro a _ hd have hslice : (xs.drop a).take (a + b.length - a) = b := by rw [hd, List.flatten_cons] exact List.take_left' (by omega) cases t with | nil => rw [rop_interiorOf_single, List.nil_append, rop_blocksOf_cons, rop_blocksOf_nil] rw [show (([b] : List (List Char)).flatten).length = b.length by simp] rw [hslice] | cons c t' => have hlen : a + ((b :: c :: t').flatten).length = (a + b.length) + ((c :: t').flatten).length := by simp only [List.flatten_cons, List.length_append] omega rw [rop_interiorOf_cons, List.cons_append, rop_blocksOf_cons, hslice, hlen] have hd2 : xs.drop (a + b.length) = (c :: t').flatten := by rw [← List.drop_drop, hd, List.flatten_cons] exact List.drop_left' rfl rw [ih (a + b.length) (by simp) hd2] theorem rop_interiorOf_props : ∀ (bs : List (List Char)) (a : Nat), (∀ b ∈ bs, b ≠ []) → (∀ p ∈ rop_interiorOf a bs, a < p ∧ p < a + bs.flatten.length) ∧ List.Pairwise (· < ·) (rop_interiorOf a bs) := by intro bs induction bs with | nil => intro a _; exact ⟨by simp [rop_interiorOf], by simp [rop_interiorOf]⟩ | cons b t ih => intro a hne cases t with | nil => rw [rop_interiorOf_single]; exact ⟨by simp, List.Pairwise.nil⟩ | cons c t' => have hb : 0 < b.length := List.length_pos_iff.mpr (hne b (by simp)) have hc : 0 < c.length := List.length_pos_iff.mpr (hne c (by simp)) obtain ⟨ihb, ihp⟩ := ih (a + b.length) (fun x hx => hne x (by simp [hx])) have hfl : ((b :: c :: t').flatten).length = b.length + ((c :: t').flatten).length := by simp only [List.flatten_cons, List.length_append] have hcl : c.length ≤ ((c :: t').flatten).length := by simp only [List.flatten_cons, List.length_append] omega rw [rop_interiorOf_cons] constructor · intro p hpm rcases List.mem_cons.mp hpm with h1 | h1 · subst h1; rw [hfl]; omega · have := ihb p h1 rw [hfl]; omega · rw [List.pairwise_cons] exact ⟨fun p hpm => (ihb p hpm).1, ihp⟩ theorem rop_finRange_map_val (m : Nat) : (List.finRange m).map Fin.val = List.range m := by apply List.ext_getElem <;> simp theorem rop_finRange_filterMap (m : Nat) (p : Nat → Bool) : (List.finRange m).filterMap (fun i : Fin m => if p i.val then some (i.val + 1) else none) = (List.range m).filterMap (fun j => if p j then some (j + 1) else none) := by rw [← rop_finRange_map_val m, List.filterMap_map] rfl theorem rop_range'_filterMap_eq (q : Nat → Bool) : ∀ (len s : Nat) (I : List Nat), List.Pairwise (· < ·) I → (∀ x ∈ I, s ≤ x ∧ x < s + len) → (∀ j, s ≤ j → j < s + len → (q j = true ↔ j ∈ I)) → (List.range' s len).filterMap (fun j => if q j then some j else none) = I := by intro len induction len with | zero => intro s I _ hb _ rw [List.range'_zero, List.filterMap_nil] symm rw [List.eq_nil_iff_forall_not_mem] intro x hx have := hb x hx omega | succ len ih => intro s I hpw hb hiff rw [List.range'_succ] by_cases hs : q s = true · have hfs : (fun j => if q j then some j else none) s = some s := by simp [hs] rw [List.filterMap_cons_some (f := fun j => if q j then some j else none) hfs] have hmem : s ∈ I := (hiff s (Nat.le_refl s) (by omega)).mp hs cases I with | nil => exact absurd hmem (by simp) | cons hd ys => obtain ⟨hhd, htl⟩ := List.pairwise_cons.mp hpw have hhs : hd = s := by by_contra hh have hys : s ∈ ys := by rcases List.mem_cons.mp hmem with h1 | h1 · exact absurd h1.symm hh · exact h1 have h2 := hhd s hys have h3 := (hb hd (by simp)).1 omega subst hhs congr 1 refine ih (hd + 1) ys htl ?_ ?_ · intro x hx have h1 := hhd x hx have h2 := (hb x (by simp [hx])).2 omega · intro j hj1 hj2 rw [hiff j (by omega) (by omega), List.mem_cons] constructor · rintro (rfl | hh) · omega · exact hh · intro hh; exact Or.inr hh · have hfs : (fun j => if q j then some j else none) s = none := by simp [hs] rw [List.filterMap_cons_none (f := fun j => if q j then some j else none) hfs] refine ih (s + 1) I hpw ?_ ?_ · intro x hx have h1 := hb x hx have h2 : x ≠ s := by intro he subst he exact hs ((hiff x h1.1 h1.2).mpr hx) omega · intro j hj1 hj2 exact hiff j (by omega) (by omega) theorem rop_range_shift (m : Nat) (I : List Nat) : (List.range m).filterMap (fun j => if decide (j + 1 ∈ I) then some (j + 1) else none) = (List.range' 1 m).filterMap (fun j => if decide (j ∈ I) then some j else none) := by rw [List.range'_eq_map_range, List.filterMap_map] congr 1 funext j simp [Nat.add_comm] theorem rop_range_filterMap_eq (m : Nat) (I : List Nat) (hpw : List.Pairwise (· < ·) I) (hb : ∀ x ∈ I, 1 ≤ x ∧ x ≤ m) : (List.range m).filterMap (fun j => if decide (j + 1 ∈ I) then some (j + 1) else none) = I := by rw [rop_range_shift] refine rop_range'_filterMap_eq (fun j => decide (j ∈ I)) m 1 I hpw ?_ ?_ · intro x hx have := hb x hx omega · intro j _ _ simp theorem rop_cutPositions_eq (s : String) (hn : 1 ≤ s.length) (cuts : cutCode s) : cutPositions s cuts = 0 :: (((List.finRange (s.length - 1)).filterMap (fun i => if cuts i then some (i.val + 1) else none)) ++ [s.length]) := by unfold cutPositions rw [if_neg (by omega), List.cons_append] theorem rop_decodeBlocks_eq (s : String) (hn : 1 ≤ s.length) (cuts : cutCode s) : decodeBlocks s cuts = (rop_blocksOf s.toList 0 (((List.finRange (s.length - 1)).filterMap (fun i => if cuts i then some (i.val + 1) else none)) ++ [s.toList.length])).map String.ofList := by unfold decodeBlocks rw [if_neg (by omega), rop_cutPositions_eq s hn cuts, rop_decode_blocksOf, String.length_toList] theorem rop_encode_exists (s : String) (hn : 1 ≤ s.length) (bs : List String) (hjoin : String.join bs = s) (hne : ∀ b ∈ bs, b ≠ "") : ∃ cuts : cutCode s, decodeBlocks s cuts = bs := by have hfl : (bs.map String.toList).flatten = s.toList := by rw [← hjoin, String.toList_join, List.flatMap_def] have hne' : ∀ b ∈ bs.map String.toList, b ≠ [] := by intro b hb rw [List.mem_map] at hb obtain ⟨x, hx, rfl⟩ := hb intro hc exact hne x hx ((rop_toList_eq_nil x).mp hc) have hbsne : bs.map String.toList ≠ [] := by intro he rw [he, List.flatten_nil] at hfl have hz : s.toList.length = s.length := String.length_toList rw [← hfl] at hz simp at hz omega obtain ⟨hIb, hIpw⟩ := rop_interiorOf_props (bs.map String.toList) 0 hne' refine ⟨fun i => decide (i.val + 1 ∈ rop_interiorOf 0 (bs.map String.toList)), ?_⟩ rw [rop_decodeBlocks_eq s hn] have hfm : (List.finRange (s.length - 1)).filterMap (fun i : Fin (s.length - 1) => if decide (i.val + 1 ∈ rop_interiorOf 0 (bs.map String.toList)) then some (i.val + 1) else none) = rop_interiorOf 0 (bs.map String.toList) := by rw [rop_finRange_filterMap (s.length - 1) (fun j => decide (j + 1 ∈ rop_interiorOf 0 (bs.map String.toList)))] refine rop_range_filterMap_eq _ _ hIpw ?_ intro q hq have hq2 := hIb q hq rw [hfl] at hq2 have hz : s.toList.length = s.length := String.length_toList omega rw [hfm] have hbi := rop_blocksOf_interiorOf s.toList (bs.map String.toList) 0 hbsne (by rw [List.drop_zero, hfl]) rw [hfl, Nat.zero_add] at hbi rw [hbi, List.map_map] simp [Function.comp_def, String.ofList_toList] /-! ### Added: plumbing -/ theorem rop_forall2_of_map (bs : List String) (f : String → String) (R : String → String → Prop) (h : ∀ b ∈ bs, R b (f b)) : List.Forall₂ R bs (bs.map f) := by revert h induction bs with | nil => intro _; simp only [List.map_nil]; exact List.Forall₂.nil | cons a t ih => intro h rw [List.map_cons] exact List.Forall₂.cons (h a (by simp)) (ih (fun b hb => h b (by simp [hb]))) theorem rop_forall2_map_of (bs ts : List String) (f : String → String) (R : String → String → Prop) (hf : ∀ b t : String, R b t → t = f b) (h : List.Forall₂ R bs ts) : ts = bs.map f ∧ ∀ b ∈ bs, R b (f b) := by induction bs generalizing ts with | nil => rw [List.forall₂_nil_left_iff] at h subst h simp | cons a t ih => rw [List.forall₂_cons_left_iff] at h obtain ⟨b, u', hr, hrest, rfl⟩ := h obtain ⟨ih1, ih2⟩ := ih u' hrest refine ⟨?_, ?_⟩ · rw [List.map_cons, ih1, hf a b hr] · intro x hx rcases List.mem_cons.mp hx with h1 | h1 · rw [h1, ← hf a b hr]; exact hr · exact ih2 x h1 theorem rop_chars_of_join (bs : List String) (s : String) (hj : String.join bs = s) (hs : ∀ c ∈ s.toList, c = '(' ∨ c = ')') : ∀ b ∈ bs, ∀ c ∈ b.toList, c = '(' ∨ c = ')' := by intro b hb c hc apply hs rw [← hj, String.toList_join] exact List.mem_flatMap.mpr ⟨b, hb, hc⟩ theorem rop_valid_chars (s : String) (hv : isValidInput s = true) : 1 ≤ s.length ∧ ∀ c ∈ s.toList, c = '(' ∨ c = ')' := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, Bool.or_eq_true, beq_iff_eq] at hv exact ⟨hv.1.1.1, hv.1.2⟩ theorem rop_check_eq (input : Input) (result : Output) : (removeOutermostParentheses_check input result = true) ↔ ∃ cuts : cutCode input, (decodeBlocks input cuts).all isPrimitiveBlock = true ∧ String.join (decodeBlocks input cuts) = input ∧ String.join ((decodeBlocks input cuts).map stripOuter) = result := by unfold removeOutermostParentheses_check rw [decide_eq_true_eq] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem removeOutermostParentheses_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : removeOutermostParentheses_check input result ↔ removeOutermostParentheses_spec input result := by rw [rop_check_eq] unfold removeOutermostParentheses_spec obtain ⟨hlen, hchars⟩ := rop_valid_chars input h constructor · rintro ⟨cuts, hallp, hjoin, hres⟩ refine ⟨decodeBlocks input cuts, (decodeBlocks input cuts).map stripOuter, ?_, hjoin, hres⟩ refine rop_forall2_of_map _ _ _ ?_ intro b hb have hpb : isPrimitiveBlock b = true := (List.all_eq_true.mp hallp) b hb have hch : ∀ c ∈ b.toList, c = '(' ∨ c = ')' := rop_chars_of_join _ _ hjoin hchars b hb exact ⟨(rop_prim_iff b hch).mp hpb, rop_core_outer b hch ((rop_isPrimitiveBlock_iff_core b).mp hpb)⟩ · rintro ⟨blocks, inners, hf2, hjoin, hres⟩ have hf : ∀ b t : String, IsInnerOfPrimitive b t → t = stripOuter b := by intro b t hbt rw [hbt.2, rop_stripOuter_eq] obtain ⟨hmap, hR⟩ := rop_forall2_map_of blocks inners stripOuter IsInnerOfPrimitive hf hf2 have hch : ∀ b ∈ blocks, ∀ c ∈ b.toList, c = '(' ∨ c = ')' := rop_chars_of_join _ _ hjoin hchars have hallp : blocks.all isPrimitiveBlock = true := by rw [List.all_eq_true] intro b hb exact (rop_prim_iff b (hch b hb)).mpr (hR b hb).1 have hne : ∀ b ∈ blocks, b ≠ "" := fun b hb => (hR b hb).1.1 obtain ⟨cuts, hcuts⟩ := rop_encode_exists input hlen blocks hjoin hne refine ⟨cuts, ?_, ?_, ?_⟩ · rw [hcuts]; exact hallp · rw [hcuts]; exact hjoin · rw [hcuts, ← hmap]; exact hres /-! ### Implementation helpers -/ /-- Tail-recursive scan: walking the character list with running balance, cutting a primitive block whenever the balance returns to zero and collecting the reversed inner strings. -/ def parenScan : List Char → Int → List Char → List String → List String | [], _, _, out => out | c :: cs, bal, cur, out => let bal' := bal + (if c = '(' then (1 : Int) else -1) let cur' := c :: cur if bal' = 0 then parenScan cs bal' [] (stripOuter (String.ofList cur'.reverse) :: out) else parenScan cs bal' cur' out /-! ### Main algorithm (impl) -/ /-- Removes the outermost parentheses of every primitive block by one linear balance-driven scan. -/ def removeOutermostParenthesesImpl (input : Input) : Output := String.join (parenScan input.toList 0 [] []).reverse /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem removeOutermostParenthesesImpl_correct (input : Input) (h : isValidInput input) : removeOutermostParentheses_spec input (removeOutermostParenthesesImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "(()())(())" #guard isValidInput "()()" #guard isValidInput "(())" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "") #guard !(isValidInput "[]") #guard !(isValidInput "(") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard removeOutermostParentheses_check "(()())(())" "()()()" #guard removeOutermostParentheses_check "()()" "" #guard removeOutermostParentheses_check "(())" "()" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(removeOutermostParentheses_check "(()())(())" "()()(())") #guard !(removeOutermostParentheses_check "()()" "()()") #guard !(removeOutermostParentheses_check "(())" "") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard removeOutermostParenthesesImpl "(()())(())" == "()()()" #guard removeOutermostParenthesesImpl "()()" == "" #guard removeOutermostParenthesesImpl "(())" == "()" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard removeOutermostParentheses_check "(()())(())" (removeOutermostParenthesesImpl "(()())(())") #guard removeOutermostParentheses_check "()()" (removeOutermostParenthesesImpl "()()") #guard removeOutermostParentheses_check "(())" (removeOutermostParenthesesImpl "(())") end PRemoveOutermostParentheses