import Mathlib /-! # Symmetric Tree Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center). ## Constraints - The number of nodes in the tree is in the range [1, 1000]. - -100 <= Node.val <= 100 ## Provided examples - `root = [1, 2, 2, 3, 4, 4, 3]` → `true` - `root = [1, 2, 2, null, 3, null, 3]` → `false` - `root = [1]` → `true` ## Synthesized negative examples - invalid input: `root = []` ([structural] a predicate that admits The number of nodes in the tree is in the range [1, 1000].. empty serialized tree has zero nodes, below the stated minimum) - invalid input: `root = [101]` ([structural] a predicate that admits -100 <= Node.val <= 100. one past the stated maximum value) - invalid input: `root = [-101]` ([structural] a predicate that admits -100 <= Node.val <= 100. one below the stated minimum value) - `root = [1, 2, 2, 3, 4, 4, 3]` → `false` is wrong ([structural] symmetry is read as equality of left and right subtrees. left and right subtrees differ, so equality check returns false) - `root = [1, 2, 2, null, 3, null, 3]` → `true` is wrong ([structural] only root's immediate children are compared, not recursive mirror structure. root children both 2 so it passes) - `root = [1]` → `false` is wrong ([structural] no clause requires a positive answer for a single-node tree. constant false is accepted and does no work) -/ namespace PSymmetricTree /-! ### Representation -/ /-- A numeric entry of the JSON array is a node value, so `n : Option Int` is `some n`. -/ instance instOfNatOptionInt {n : Nat} : OfNat (Option Int) n := ⟨some (n : Int)⟩ /-- Negation of an array entry negates a present node value and leaves `none` alone. -/ instance instNegOptionInt : Neg (Option Int) := ⟨Option.map (fun v : Int => -v)⟩ /-- A binary tree with integer node values, the denotation of a level-order array. -/ inductive Tree where | nil : Tree | node : Int → Tree → Tree → Tree abbrev Input := List (Option Int) abbrev Output := Bool /-! ### Specification helpers -/ /-- The serialized argument is already the declared level-order list, so the bridge is the identity. -/ def rootFromArray (l : List (Option Int)) : List (Option Int) := l /-- The subtree of the level-order array `a` rooted at index `i`. -/ def buildTree (a : List (Option Int)) (i : Nat) : Tree := if h : i < a.length then match a[i]'h with | none => Tree.nil | some v => Tree.node v (buildTree a (2 * i + 1)) (buildTree a (2 * i + 2)) else Tree.nil termination_by a.length - i decreasing_by all_goals omega /-- Mirror images: both empty, or equal roots with each side's left mirroring the other's right. -/ inductive Mirror : Tree → Tree → Prop where | nil : Mirror Tree.nil Tree.nil | node {v : Int} {l₁ r₁ l₂ r₂ : Tree} : Mirror l₁ r₂ → Mirror r₁ l₂ → Mirror (Tree.node v l₁ r₁) (Tree.node v l₂ r₂) /-- The tree encoded by `a` is symmetric: its root's two subtrees are mirror images. -/ def IsSymmetric (a : List (Option Int)) : Prop := match buildTree a 0 with | Tree.nil => True | Tree.node _ l r => Mirror l r /-! ### Validity predicate (V) -/ /-- Valid input: a well-formed level-order serialization of a binary tree with 1 to 1000 nodes, every value between -100 and 100. -/ def isValidInput (root : Input) : Bool := (root.headD none).isSome && (List.range root.length).all (fun i => i == 0 || (root.getD ((i - 1) / 2) none).isSome) && 1 ≤ (root.filterMap id).length && (root.filterMap id).length ≤ 1000 && (root.filterMap id).all (fun v => -100 ≤ v && v ≤ 100) /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when the tree encoded by `input` is a mirror of itself. -/ def isSymmetric_spec (input : Input) (result : Output) : Prop := result ↔ IsSymmetric input /-! ### Decidable specification (P_check) -/ /-- Decides `Mirror t₁ t₂` by structural recursion on the trees: two empty trees mirror, and two nodes mirror exactly when their values agree and the crossed subtrees mirror. -/ instance decMirror : (t₁ t₂ : Tree) → Decidable (Mirror t₁ t₂) | Tree.nil, Tree.nil => isTrue Mirror.nil | Tree.nil, Tree.node _ _ _ => isFalse (fun h => by cases h) | Tree.node _ _ _, Tree.nil => isFalse (fun h => by cases h) | Tree.node v₁ l₁ r₁, Tree.node v₂ l₂ r₂ => if hv : v₁ = v₂ then match decMirror l₁ r₂, decMirror r₁ l₂ with | isTrue h₁, isTrue h₂ => isTrue (by subst hv; exact Mirror.node h₁ h₂) | isFalse hf, _ => isFalse (fun h => by subst hv; cases h with | node a _ => exact hf a) | _, isFalse hf => isFalse (fun h => by subst hv; cases h with | node _ b => exact hf b) else isFalse (fun h => by cases h with | node _ _ => exact hv rfl) /-- Decides `IsSymmetric a`: it unfolds to a match on the decoded tree, which is either `True` for an empty tree or a `Mirror` check handled by `decMirror`. -/ instance decIsSymmetric (a : Input) : Decidable (IsSymmetric a) := by unfold IsSymmetric split · infer_instance · infer_instance /-- Decides the specification `result = true ↔ IsSymmetric input` componentwise: decidable equality of `result` with `true`, and `decIsSymmetric` for the right side. -/ instance decSpec (input : Input) (result : Output) : Decidable (result = true ↔ IsSymmetric input) := match inferInstanceAs (Decidable (result = true)), decIsSymmetric input with | isTrue h₁, isTrue h₂ => isTrue ⟨fun _ => h₂, fun _ => h₁⟩ | isTrue h₁, isFalse h₂ => isFalse (fun h => h₂ (h.mp h₁)) | isFalse h₁, isTrue h₂ => isFalse (fun h => h₁ (h.mpr h₂)) | isFalse h₁, isFalse h₂ => isTrue ⟨fun h => absurd h h₁, fun h => absurd h h₂⟩ /-- Executable checker obtained mechanically from the specification. -/ def isSymmetric_check (input : Input) (result : Output) : Bool := @decide (isSymmetric_spec input result) (by unfold isSymmetric_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem isSymmetric_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : isSymmetric_check input result ↔ isSymmetric_spec input result := by simp [isSymmetric_check] /-! ### Implementation helpers -/ /-- Mirror property of two trees as a proposition, clause for clause the shape of `Mirror`. -/ def mirrorProp : Tree → Tree → Prop | Tree.nil, Tree.nil => True | Tree.node v l₁ r₁, Tree.node w l₂ r₂ => v = w ∧ mirrorProp l₁ r₂ ∧ mirrorProp r₁ l₂ | _, _ => False /-- Decision procedure for `mirrorProp` by the same structural recursion as the predicate. -/ def decMirrorProp : (t₁ t₂ : Tree) → Decidable (mirrorProp t₁ t₂) | Tree.nil, Tree.nil => isTrue trivial | Tree.nil, Tree.node _ _ _ => isFalse id | Tree.node _ _ _, Tree.nil => isFalse id | Tree.node v l₁ r₁, Tree.node w l₂ r₂ => match decEq v w, decMirrorProp l₁ r₂, decMirrorProp r₁ l₂ with | isTrue hv, isTrue h₁, isTrue h₂ => isTrue ⟨hv, h₁, h₂⟩ | isFalse hv, _, _ => isFalse (fun hc => hv hc.1) | _, isFalse h₁, _ => isFalse (fun hc => h₁ hc.2.1) | _, _, isFalse h₂ => isFalse (fun hc => h₂ hc.2.2) /-- `mirrorProp` is decidable on any pair of trees. -/ instance instMirrorPropDecidable (t₁ t₂ : Tree) : Decidable (mirrorProp t₁ t₂) := decMirrorProp t₁ t₂ /-- Symmetry of the tree encoded by `a` as a proposition, mirroring `IsSymmetric`. -/ def symmetricProp (a : List (Option Int)) : Prop := match buildTree a 0 with | Tree.nil => True | Tree.node _ l r => mirrorProp l r /-- `symmetricProp` is decidable by cases on the decoded root. -/ instance instSymmetricPropDecidable (a : List (Option Int)) : Decidable (symmetricProp a) := by unfold symmetricProp split · exact isTrue trivial · exact inferInstance /-! ### Main algorithm (impl) -/ /-- Symmetry by deciding the checker's executable mirror proposition on the decoded tree. -/ def checkSymmetricTree (input : Input) : Output := decide (symmetricProp input) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem checkSymmetricTree_correct (input : Input) (h : isValidInput input) : isSymmetric_spec input (checkSymmetricTree input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (rootFromArray [1, 2, 2, 3, 4, 4, 3]) #guard isValidInput (rootFromArray [(some 1), (some 2), (some 2), none, (some 3), none, (some 3)]) #guard isValidInput (rootFromArray [1]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (rootFromArray [])) #guard !(isValidInput (rootFromArray [101])) #guard !(isValidInput (rootFromArray [(-101)])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard isSymmetric_check (rootFromArray [1, 2, 2, 3, 4, 4, 3]) true #guard isSymmetric_check (rootFromArray [(some 1), (some 2), (some 2), none, (some 3), none, (some 3)]) false #guard isSymmetric_check (rootFromArray [1]) true /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(isSymmetric_check (rootFromArray [1, 2, 2, 3, 4, 4, 3]) false) #guard !(isSymmetric_check (rootFromArray [(some 1), (some 2), (some 2), none, (some 3), none, (some 3)]) true) #guard !(isSymmetric_check (rootFromArray [1]) false) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard checkSymmetricTree (rootFromArray [1, 2, 2, 3, 4, 4, 3]) == true #guard checkSymmetricTree (rootFromArray [(some 1), (some 2), (some 2), none, (some 3), none, (some 3)]) == false #guard checkSymmetricTree (rootFromArray [1]) == true /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard isSymmetric_check (rootFromArray [1, 2, 2, 3, 4, 4, 3]) (checkSymmetricTree (rootFromArray [1, 2, 2, 3, 4, 4, 3])) #guard isSymmetric_check (rootFromArray [(some 1), (some 2), (some 2), none, (some 3), none, (some 3)]) (checkSymmetricTree (rootFromArray [(some 1), (some 2), (some 2), none, (some 3), none, (some 3)])) #guard isSymmetric_check (rootFromArray [1]) (checkSymmetricTree (rootFromArray [1])) end PSymmetricTree