import Mathlib /-! # Add One Row To Tree Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth depth. Note that the root node is at depth 1. The adding rule is: Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur's left subtree root and right subtree root. cur's original left subtree should be the left subtree of the new left subtree root. cur's original right subtree should be the right subtree of the new right subtree root. If depth == 1 that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root's left subtree. ## Constraints - The number of nodes in the tree is in the range [1, 10^4]. - The depth of the tree is in the range [1, 10^4]. - -100 <= Node.val <= 100 - -10^5 <= val <= 10^5 - 1 <= depth <= the depth of tree + 1 ## Provided examples - `root = [4, 2, 6, 3, 1, 5], val = 1, depth = 2` → `[4, 1, 1, 2, null, null, 6, 3, 1, 5]` - `root = [4, 2, null, 3, 1], val = 1, depth = 3` → `[4, 2, null, 1, 1, 3, null, null, 1]` - `root = [1], val = 2, depth = 1` → `[2, 1]` ## Synthesized negative examples - invalid input: `root = [], val = 0, depth = 1` ([structural] a predicate that admits The number of nodes in the tree is in the range [1, 10^4].. empty tree has zero nodes; a predicate checking depth alone accepts it) - invalid input: `root = [101], val = 0, depth = 1` ([structural] a predicate that admits -100 <= Node.val <= 100. node value one past the stated maximum) - invalid input: `root = [1], val = 0, depth = 3` ([structural] a predicate that admits 1 <= depth <= the depth of tree + 1. depth exceeds tree depth plus one; a predicate checking depth alone accepts it) - `root = [4, 2, 6, 3, 1, 5], val = 1, depth = 2` → `[4, 0, 0, 2, null, null, 6, 3, 1, 5]` is wrong ([structural] inserted nodes value is not required to equal val. new row has value 0 instead of 1) - `root = [4, 2, null, 3, 1], val = 1, depth = 3` → `[4, 1, 1, 2, null, null, null, 3, 1]` is wrong ([structural] row inserted one depth too early. nodes added at depth 2 instead of depth 3) - `root = [1], val = 2, depth = 1` → `[1, 2, 2]` is wrong ([structural] depth is counted from 0, so depth 1 inserts one level below the root. inserts at depth 2 instead of depth 1) -/ namespace PAddOneRowToTree abbrev Input := (List (Option Int)) × (Int) × (Nat) abbrev Output := List (Option Int) /-! ### Specification helpers -/ /-- Binary tree with integer node values, the object the insertion rule ranges over. -/ abbrev TreeNode := Tree Int /-- The level-order entry a slot contributes: the value for a node, none for a missing child. -/ def slotEntry : Tree Int → Option Int | BinaryTree.nil => none | BinaryTree.node v _ _ => some v /-- The two child slots a node contributes to the next level; a missing node contributes none. -/ def slotChildren : Tree Int → List (Tree Int) | BinaryTree.nil => [] | BinaryTree.node _ l r => [l, r] /-- The breadth-first entries of a forest, emitting one level per unit of fuel. -/ def bfsLevels : Nat → List (Tree Int) → List (Option Int) | 0, _ => [] | _, [] => [] | fuel + 1, q => q.map slotEntry ++ bfsLevels fuel (q.flatMap slotChildren) /-- Drop the trailing null entries of a level-order listing. -/ def trimTrailingNulls (l : List (Option Int)) : List (Option Int) := (l.reverse.dropWhile (fun e => e.isNone)).reverse /-- The LeetCode level-order serialization of a tree: breadth-first entries with trailing nulls removed. -/ def bfsSeq (t : Tree Int) : List (Option Int) := trimTrailingNulls (bfsLevels (Tree.height t) [t]) /-- `l` is exactly the level-order serialization of the tree `t`. -/ def LevelOrderSerialization (t : TreeNode) (l : List (Option Int)) : Prop := l = bfsSeq t /-- `t'` is `t` with a row of nodes of value `v` inserted at 1-based depth `d`. -/ inductive IsRowInsertion : TreeNode → Int → Nat → TreeNode → Prop where | base (r : TreeNode) (v : Int) : IsRowInsertion r v 1 (Tree.node v r BinaryTree.nil) | wrap (l r : TreeNode) (x v : Int) : IsRowInsertion (Tree.node x l r) v 2 (Tree.node x (Tree.node v l BinaryTree.nil) (Tree.node v BinaryTree.nil r)) | step (l r l' r' : TreeNode) (x v : Int) (d : Nat) : IsRowInsertion l v (d + 2) l' → IsRowInsertion r v (d + 2) r' → IsRowInsertion (Tree.node x l r) v (d + 3) (Tree.node x l' r') | nil (v : Int) (d : Nat) : IsRowInsertion BinaryTree.nil v (d + 2) BinaryTree.nil /-- Walk a serialized list against a queue of open slot depths, returning the node count and the greatest node depth, or none if some entry has no open slot. -/ def scanSerial : List Nat → List (Option Int) → Nat → Nat → Option (Nat × Nat) | _, [], count, maxD => some (count, maxD) | [], _ :: _, _, _ => none | _ :: ds, none :: es, count, maxD => scanSerial ds es count maxD | d :: ds, (some _) :: es, count, maxD => scanSerial (ds ++ [d + 1, d + 1]) es (count + 1) (max maxD d) /-- The node count and depth of the tree a serialization describes, or none if the slots do not line up. -/ def analyzeSerial (l : List (Option Int)) : Option (Nat × Nat) := scanSerial [1] l 0 0 /-- A present node value lies in [-100, 100]; a null marker imposes no constraint. -/ def nodeValueOk (e : Option Int) : Bool := match e with | some v => decide (-100 ≤ v ∧ v ≤ 100) | none => true /-! ### Validity predicate (V) -/ /-- Valid input: a structurally consistent level-order serialization with no trailing nulls, 1 to 10^4 nodes, tree depth 1 to 10^4, node values in [-100, 100], val in [-10^5, 10^5], and 1 <= depth <= tree depth + 1. -/ def isValidInput (input : Input) : Bool := match input with | (root, val, depth) => match analyzeSerial root with | none => false | some (count, treeDepth) => decide (1 ≤ count ∧ count ≤ 10000 ∧ 1 ≤ treeDepth ∧ treeDepth ≤ 10000 ∧ -100000 ≤ val ∧ val ≤ 100000 ∧ 1 ≤ depth ∧ depth ≤ treeDepth + 1) && root.all nodeValueOk && (match root.getLast? with | some (some _) => true | _ => false) /-! ### Ideal specification (P_spec) -/ /-- `result` is the level-order serialization of a tree obtained from the tree serialized by `root` by inserting a row of value `val` at 1-based depth `depth`, with every position before the last non-null one — including interior null markers — matching that tree's level-order entries. -/ def addOneRow_spec (input : Input) (result : Output) : Prop := match input with | (root, val, depth) => ∃ r t : TreeNode, LevelOrderSerialization r root ∧ IsRowInsertion r val depth t ∧ LevelOrderSerialization t result ∧ ∀ i : Nat, i < (bfsSeq t).length → result[i]? = (bfsSeq t)[i]? /-! ### Decidable specification (P_check) -/ /-- Insert a row of nodes of value `v` at 1-based depth `d`, the computational form of `IsRowInsertion`. -/ def insertRow (t : Tree Int) (v : Int) : Nat → Tree Int | 0 => t | 1 => Tree.node v t BinaryTree.nil | 2 => match t with | BinaryTree.nil => BinaryTree.nil | BinaryTree.node x l r => Tree.node x (Tree.node v l BinaryTree.nil) (Tree.node v BinaryTree.nil r) | d + 3 => match t with | BinaryTree.nil => BinaryTree.nil | BinaryTree.node x l r => Tree.node x (insertRow l v (d + 2)) (insertRow r v (d + 2)) /-- Assemble `n` trees of one BFS level from slot entries and the queue of already-built child subtrees, padding missing entries and children with nil. -/ def assemble : Nat → List (Option Int) → List (Tree Int) → List (Tree Int) | 0, _, _ => [] | n + 1, none :: es, cs => BinaryTree.nil :: assemble n es cs | n + 1, some v :: es, l :: r :: cs => Tree.node v l r :: assemble n es cs | n + 1, some v :: es, [l] => Tree.node v l BinaryTree.nil :: assemble n es [] | n + 1, some v :: es, [] => Tree.node v BinaryTree.nil BinaryTree.nil :: assemble n es [] | n + 1, [], _ => BinaryTree.nil :: assemble n [] [] /-- Build the forest of one BFS level for `slots` open slots from the remaining entries, with `fuel` bounding the tree's height. -/ def buildLevel : Nat → Nat → List (Option Int) → List (Tree Int) × List (Option Int) | 0, _, es => ([], es) | _ + 1, 0, es => ([], es) | fuel + 1, slots + 1, es => let levelEntries := es.take (slots + 1) let rest := es.drop (slots + 1) let countSome := levelEntries.countP (fun e => e.isSome) let (childTrees, rest') := buildLevel fuel (2 * countSome) rest (assemble (slots + 1) levelEntries childTrees, rest') /-- The unique tree whose level-order serialization is `l`, with missing trailing slots read as nil. -/ def decodeTree (l : List (Option Int)) : Tree Int := match (buildLevel (l.length + 1) 1 l).1 with | t :: _ => t | [] => BinaryTree.nil /-- Executable checker for `addOneRow_spec`: the serialization determines the tree and the insertion rule determines the result tree, so verify each clause against these computed witnesses. -/ def addOneRow_check (input : Input) (result : Output) : Bool := match input with | (root, val, depth) => let r := decodeTree root let t := insertRow r val depth decide (root = bfsSeq r) && decide (result = bfsSeq t) && (List.range (bfsSeq t).length).all fun i => decide (result[i]? = (bfsSeq t)[i]?) /-- `L` is `es` followed by some null entries. -/ def PadEq (es L : List (Option Int)) : Prop := ∃ k, L = es ++ List.replicate k none theorem padEq_split : ∀ (M L' es : List (Option Int)), PadEq es (M ++ L') → PadEq (es.take M.length) M ∧ PadEq (es.drop M.length) L' := by intro M induction M with | nil => intro L' es h; exact ⟨⟨0, by simp⟩, by simpa using h⟩ | cons m M ih => intro L' es hp obtain ⟨k, hk⟩ := hp rcases es with _ | ⟨e, es⟩ · rcases k with _ | k · simp at hk · simp only [List.nil_append, List.replicate_succ, List.cons_append, List.cons.injEq] at hk obtain ⟨rfl, hk⟩ := hk obtain ⟨⟨j, hj⟩, h2⟩ := ih L' [] ⟨k, by rw [List.nil_append]; exact hk⟩ refine ⟨⟨j + 1, ?_⟩, by simpa using h2⟩ simp only [List.take_nil, List.nil_append] at hj ⊢ rw [hj, List.replicate_succ] · simp only [List.cons_append, List.cons.injEq] at hk obtain ⟨rfl, hk⟩ := hk obtain ⟨⟨j, hj⟩, h2⟩ := ih L' es ⟨k, hk⟩ refine ⟨⟨j, ?_⟩, by simpa using h2⟩ rw [List.length_cons, List.take_succ_cons, List.cons_append, ← hj] theorem countP_pad (es : List (Option Int)) (k : Nat) : (es ++ List.replicate k none).countP (fun (e : Option Int) => e.isSome) = es.countP (fun (e : Option Int) => e.isSome) := by simp [List.countP_append] theorem countP_slot (q : List (BinaryTree Int)) : 2 * (q.map slotEntry).countP (fun e => e.isSome) = (q.flatMap slotChildren).length := by induction q with | nil => simp | cons t q ih => cases t with | nil => simp only [List.map_cons, List.countP_cons, List.flatMap_cons, slotEntry, slotChildren, List.nil_append] simpa using ih | node x l r => simp only [List.map_cons, List.countP_cons, List.flatMap_cons, slotEntry, slotChildren, List.length_append] simp only [Option.isSome_some, if_true, List.length_cons, List.length_nil] omega theorem pad_nil_children : ∀ (q : List (BinaryTree Int)), PadEq [] (q.map slotEntry) → q.flatMap slotChildren = [] := by intro q induction q with | nil => intro _; rfl | cons t q ih => intro hp obtain ⟨k, hk⟩ := hp rcases k with _ | k · simp at hk · cases t with | nil => simp only [List.map_cons, slotEntry, List.nil_append, List.replicate_succ, List.cons.injEq, true_and] at hk simp only [List.flatMap_cons, slotChildren, List.nil_append] exact ih ⟨k, by rw [List.nil_append]; exact hk⟩ | node x l r => simp [slotEntry, List.replicate_succ] at hk theorem asm_none (n : Nat) (es : List (Option Int)) (cs : List (BinaryTree Int)) : assemble (n + 1) (none :: es) cs = BinaryTree.nil :: assemble n es cs := rfl theorem asm_some (n : Nat) (v : Int) (es : List (Option Int)) (l r : BinaryTree Int) (cs : List (BinaryTree Int)) : assemble (n + 1) (some v :: es) (l :: r :: cs) = BinaryTree.node v l r :: assemble n es cs := rfl theorem asm_empty (n : Nat) (cs : List (BinaryTree Int)) : assemble (n + 1) [] cs = BinaryTree.nil :: assemble n [] [] := rfl theorem assemble_eq : ∀ (q : List (BinaryTree Int)) (es : List (Option Int)), PadEq es (q.map slotEntry) → assemble q.length es (q.flatMap slotChildren) = q := by intro q induction q with | nil => intro es _; rfl | cons t q ih => intro es hp have hp' := hp obtain ⟨k, hk⟩ := hp cases t with | nil => rcases es with _ | ⟨e, es⟩ · rcases k with _ | k · simp at hk · simp only [List.map_cons, slotEntry, List.nil_append, List.replicate_succ, List.cons.injEq, true_and] at hk have hc : q.flatMap slotChildren = [] := pad_nil_children q ⟨k, by rw [List.nil_append]; exact hk⟩ have := ih [] ⟨k, by rw [List.nil_append]; exact hk⟩ rw [hc] at this rw [List.length_cons, asm_empty, this] · simp only [List.map_cons, slotEntry, List.cons_append, List.cons.injEq] at hk obtain ⟨rfl, hk⟩ := hk simp only [List.flatMap_cons, slotChildren, List.nil_append] rw [List.length_cons, asm_none, ih es ⟨k, hk⟩] | node x l r => rcases es with _ | ⟨e, es⟩ · rcases k with _ | k · simp at hk · simp [slotEntry, List.replicate_succ] at hk · simp only [List.map_cons, slotEntry, List.cons_append, List.cons.injEq] at hk obtain ⟨rfl, hk⟩ := hk simp only [List.flatMap_cons, slotChildren, List.cons_append, List.nil_append] rw [List.length_cons, asm_some, ih es ⟨k, hk⟩] theorem build_step (f s : Nat) (es : List (Option Int)) (C : List (BinaryTree Int)) (r' : List (Option Int)) (h : buildLevel f (2 * (es.take (s + 1)).countP (fun e => e.isSome)) (es.drop (s + 1)) = (C, r')) : buildLevel (f + 1) (s + 1) es = (assemble (s + 1) (es.take (s + 1)) C, r') := by rw [buildLevel, h] theorem bfs_succ_cons (F : Nat) (t : BinaryTree Int) (q : List (BinaryTree Int)) : bfsLevels (F + 1) (t :: q) = (t :: q).map slotEntry ++ bfsLevels F ((t :: q).flatMap slotChildren) := rfl theorem build_empty (q : List (BinaryTree Int)) (fuel : Nat) (hf : 1 ≤ fuel) (hp : PadEq [] (q.map slotEntry)) : buildLevel fuel q.length [] = (q, []) := by rcases q with _ | ⟨t, q⟩ · rcases fuel with _ | f <;> rfl · obtain ⟨f, rfl⟩ : ∃ f, fuel = f + 1 := ⟨fuel - 1, by omega⟩ have hA := assemble_eq (t :: q) [] hp rw [pad_nil_children _ hp, List.length_cons] at hA rw [List.length_cons, build_step f q.length [] [] [] (by rcases f with _ | f <;> rfl)] simp only [List.take_nil] rw [hA] theorem children_height (q : List (BinaryTree Int)) (F : Nat) (hh : ∀ t ∈ q, t.height ≤ F + 1) : ∀ c ∈ q.flatMap slotChildren, c.height ≤ F := by intro c hc obtain ⟨a, ha, hca⟩ := List.mem_flatMap.mp hc have := hh a ha cases a with | nil => simp [slotChildren] at hca | node x l r => have h2 : max l.height r.height + 1 ≤ F + 1 := this simp only [slotChildren, List.mem_cons, List.not_mem_nil, or_false] at hca rcases hca with rfl | rfl · exact le_trans (le_max_left _ _) (Nat.le_of_succ_le_succ h2) · exact le_trans (le_max_right _ _) (Nat.le_of_succ_le_succ h2) theorem buildLevel_bfs : ∀ (F : Nat) (q : List (BinaryTree Int)) (es : List (Option Int)) (fuel : Nat), (∀ t ∈ q, t.height ≤ F) → PadEq es (bfsLevels F q) → es.length + 1 ≤ fuel → buildLevel fuel q.length es = (q, []) := by intro F induction F with | zero => intro q es fuel hh hp hf obtain ⟨k, hk⟩ := hp have hes : es = [] := by have h0 : bfsLevels 0 q = [] := by simp [bfsLevels] rw [h0] at hk exact (List.append_eq_nil_iff.mp hk.symm).1 subst hes refine build_empty q fuel hf ⟨q.length, ?_⟩ rw [List.nil_append, List.eq_replicate_iff] refine ⟨by simp, fun b hb => ?_⟩ obtain ⟨t, ht, rfl⟩ := List.mem_map.mp hb have h1 := hh t ht cases t with | nil => rfl | node x l r => simp [BinaryTree.height] at h1 | succ F ih => intro q es fuel hh hp hf rcases q with _ | ⟨t, q⟩ · obtain ⟨k, hk⟩ := hp have h0 : bfsLevels (F + 1) ([] : List (BinaryTree Int)) = [] := by simp [bfsLevels] rw [h0] at hk have hes : es = [] := (List.append_eq_nil_iff.mp hk.symm).1 subst hes rcases fuel with _ | f <;> rfl · rw [bfs_succ_cons] at hp have hsplit := padEq_split _ _ _ hp simp only [List.length_map, List.length_cons] at hsplit obtain ⟨h1, h2⟩ := hsplit by_cases hes : es = [] · subst hes simp only [List.take_nil] at h1 exact build_empty (t :: q) fuel (by omega) h1 · obtain ⟨f, rfl⟩ : ∃ f, fuel = f + 1 := ⟨fuel - 1, by omega⟩ have hlen : es.length ≠ 0 := fun h0 => hes (List.length_eq_zero_iff.mp h0) have hC := ih ((t :: q).flatMap slotChildren) (es.drop (q.length + 1)) f (children_height (t :: q) F hh) h2 (by rw [List.length_drop]; omega) have hcount : 2 * (es.take (q.length + 1)).countP (fun e => e.isSome) = ((t :: q).flatMap slotChildren).length := by obtain ⟨j, hj⟩ := h1 rw [← countP_slot, hj, countP_pad] have hA := assemble_eq (t :: q) _ h1 rw [List.length_cons] at hA rw [List.length_cons, build_step f q.length es _ [] (by rw [hcount]; exact hC), hA] theorem padEq_trim (L : List (Option Int)) : PadEq (trimTrailingNulls L) L := by unfold trimTrailingNulls PadEq obtain ⟨k, hk⟩ : ∃ k, L.reverse.takeWhile (fun (e : Option Int) => e.isNone) = List.replicate k none := ⟨_, List.eq_replicate_iff.mpr ⟨rfl, fun b hb => by simpa using List.mem_takeWhile_imp hb⟩⟩ refine ⟨k, ?_⟩ have h1 := List.takeWhile_append_dropWhile (p := fun (e : Option Int) => e.isNone) (l := L.reverse) rw [hk] at h1 calc L = L.reverse.reverse := (List.reverse_reverse L).symm _ = (List.replicate k none ++ L.reverse.dropWhile (fun (e : Option Int) => e.isNone)).reverse := by rw [h1] _ = _ := by rw [List.reverse_append, List.reverse_replicate] theorem decode_bfsSeq (r : BinaryTree Int) : decodeTree (bfsSeq r) = r := by have h := buildLevel_bfs r.height [r] (bfsSeq r) ((bfsSeq r).length + 1) (by intro t ht; simp only [List.mem_singleton] at ht; subst ht; exact le_refl _) (padEq_trim _) (le_refl _) simp only [List.length_singleton] at h unfold decodeTree rw [h] theorem insertRow_sound (t : BinaryTree Int) (v : Int) : ∀ d, 1 ≤ d → IsRowInsertion t v d (insertRow t v d) := by induction t with | nil => intro d hd match d, hd with | 1, _ => exact IsRowInsertion.base _ _ | 2, _ => exact IsRowInsertion.nil v 0 | d + 3, _ => exact IsRowInsertion.nil v (d + 1) | node x l r ihl ihr => intro d hd match d, hd with | 1, _ => exact IsRowInsertion.base _ _ | 2, _ => exact IsRowInsertion.wrap l r x v | d + 3, _ => exact IsRowInsertion.step _ _ _ _ x v d (ihl (d + 2) (by omega)) (ihr (d + 2) (by omega)) theorem insertRow_of_rel {r t : BinaryTree Int} {v : Int} {d : Nat} (h : IsRowInsertion r v d t) : t = insertRow r v d := by induction h with | base r v => cases r <;> rfl | wrap l r x v => rfl | step l r l' r' x v d _ _ ihl ihr => rw [ihl, ihr]; rfl | nil v d => cases d <;> rfl theorem check_eq (root : List (Option Int)) (val : Int) (depth : Nat) (result : List (Option Int)) : addOneRow_check (root, val, depth) result = true ↔ (root = bfsSeq (decodeTree root) ∧ result = bfsSeq (insertRow (decodeTree root) val depth)) ∧ ∀ i ∈ List.range (bfsSeq (insertRow (decodeTree root) val depth)).length, result[i]? = (bfsSeq (insertRow (decodeTree root) val depth))[i]? := by simp only [addOneRow_check, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true] theorem spec_eq (root : List (Option Int)) (val : Int) (depth : Nat) (result : List (Option Int)) : addOneRow_spec (root, val, depth) result ↔ ∃ r t : BinaryTree Int, root = bfsSeq r ∧ IsRowInsertion r val depth t ∧ result = bfsSeq t ∧ ∀ i : Nat, i < (bfsSeq t).length → result[i]? = (bfsSeq t)[i]? := Iff.rfl /-- On valid input the checker accepts exactly the specified outputs. -/ theorem addOneRow_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : addOneRow_check input result ↔ addOneRow_spec input result := by obtain ⟨root, val, depth⟩ := input have hd : 1 ≤ depth := by simp only [isValidInput] at h cases hA : analyzeSerial root with | none => simp [hA] at h | some p => obtain ⟨c, td⟩ := p simp only [hA, Bool.and_eq_true, decide_eq_true_eq] at h omega rw [check_eq, spec_eq] constructor · rintro ⟨⟨h1, h2⟩, h3⟩ exact ⟨decodeTree root, _, h1, insertRow_sound _ val depth hd, h2, fun i hi => h3 i (List.mem_range.mpr hi)⟩ · rintro ⟨r, t, h1, h2, h3, h4⟩ have hr : decodeTree root = r := by rw [h1]; exact decode_bfsSeq r have ht : t = insertRow r val depth := insertRow_of_rel h2 subst ht rw [hr] exact ⟨⟨h1, h3⟩, fun i hi => h4 i (List.mem_range.mp hi)⟩ /-! ### Main algorithm (impl) -/ /-- Insert a row of value `val` at 1-based depth `depth` by decoding the serialization into a tree, inserting the row on the tree, and re-serializing breadth-first. -/ def addRowAtDepth (input : Input) : Output := match input with | (root, val, depth) => bfsSeq (insertRow (decodeTree root) val depth) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem addRowAtDepth_correct (input : Input) (h : isValidInput input) : addOneRow_spec input (addRowAtDepth input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([(some 4), (some 2), (some 6), (some 3), (some 1), (some 5)], 1, 2) #guard isValidInput ([(some 4), (some 2), none, (some 3), (some 1)], 1, 3) #guard isValidInput ([(some 1)], 2, 1) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], 0, 1)) #guard !(isValidInput ([(some 101)], 0, 1)) #guard !(isValidInput ([(some 1)], 0, 3)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard addOneRow_check ([(some 4), (some 2), (some 6), (some 3), (some 1), (some 5)], 1, 2) [(some 4), (some 1), (some 1), (some 2), none, none, (some 6), (some 3), (some 1), (some 5)] #guard addOneRow_check ([(some 4), (some 2), none, (some 3), (some 1)], 1, 3) [(some 4), (some 2), none, (some 1), (some 1), (some 3), none, none, (some 1)] #guard addOneRow_check ([(some 1)], 2, 1) [(some 2), (some 1)] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(addOneRow_check ([(some 4), (some 2), (some 6), (some 3), (some 1), (some 5)], 1, 2) [(some 4), (some 0), (some 0), (some 2), none, none, (some 6), (some 3), (some 1), (some 5)]) #guard !(addOneRow_check ([(some 4), (some 2), none, (some 3), (some 1)], 1, 3) [(some 4), (some 1), (some 1), (some 2), none, none, none, (some 3), (some 1)]) #guard !(addOneRow_check ([(some 1)], 2, 1) [(some 1), (some 2), (some 2)]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard addRowAtDepth ([(some 4), (some 2), (some 6), (some 3), (some 1), (some 5)], 1, 2) == [(some 4), (some 1), (some 1), (some 2), none, none, (some 6), (some 3), (some 1), (some 5)] #guard addRowAtDepth ([(some 4), (some 2), none, (some 3), (some 1)], 1, 3) == [(some 4), (some 2), none, (some 1), (some 1), (some 3), none, none, (some 1)] #guard addRowAtDepth ([(some 1)], 2, 1) == [(some 2), (some 1)] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard addOneRow_check ([(some 4), (some 2), (some 6), (some 3), (some 1), (some 5)], 1, 2) (addRowAtDepth ([(some 4), (some 2), (some 6), (some 3), (some 1), (some 5)], 1, 2)) #guard addOneRow_check ([(some 4), (some 2), none, (some 3), (some 1)], 1, 3) (addRowAtDepth ([(some 4), (some 2), none, (some 3), (some 1)], 1, 3)) #guard addOneRow_check ([(some 1)], 2, 1) (addRowAtDepth ([(some 1)], 2, 1)) end PAddOneRowToTree