import Mathlib /-! # House Robber Iii The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root. Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night. Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police. ## Constraints - The number of nodes in the tree is in the range [1, 10^4]. - 0 <= Node.val <= 10^4 ## Provided examples - `root = [3, 2, 3, null, 3, null, 1]` → `7` - `root = [3, 4, 5, 1, 3, null, 1]` → `9` - `root = [0]` → `0` ## Synthesized negative examples - invalid input: `root = []` ([structural] a predicate that admits The number of nodes in the tree is in the range [1, 10^4].. zero nodes; a value-only predicate accepts it) - invalid input: `root = [10001]` ([structural] a predicate that admits 0 <= Node.val <= 10^4. one past the stated maximum at root) - invalid input: `root = [-1]` ([structural] a predicate that admits 0 <= Node.val <= 10^4. one below the stated minimum at root) - `root = [3, 2, 3, null, 3, null, 1]` → `5` is wrong ([structural] maximality stated as achievability alone. robbing the two children totals 5, feasible but not maximal) - `root = [3, 4, 5, 1, 3, null, 1]` → `8` is wrong ([structural] maximum stated as feasibility alone. 8 is achieved by robbing root and all grandchildren, but 9 is larger) - `root = [0]` → `2` is wrong ([structural] the maximum is stated as an upper bound without requiring a robbery plan that reaches it. 2 exceeds the only possible total, 0) -/ namespace PHouseRobberIii /-! ### Representation -/ /-- A binary tree with integer-valued nodes; `leaf` marks an absent child. -/ inductive BinTree | leaf : BinTree | node (val : Int) (left right : BinTree) : BinTree deriving BEq, DecidableEq abbrev Input := BinTree abbrev Output := Nat /-! ### Specification helpers -/ /-- The subtree rooted at level-order index `i` of `l`, with children at `2i+1` and `2i+2`. -/ def binTreeFromArray (l : List (Option Int)) (i : Nat) : BinTree := if h : i < l.length then match l[i] with | none => BinTree.leaf | some v => BinTree.node v (binTreeFromArray l (2 * i + 1)) (binTreeFromArray l (2 * i + 2)) else BinTree.leaf termination_by l.length - i decreasing_by all_goals omega /-- Builds the tree from its level-order array serialization, `none` marking an absent node. -/ def arrayToBinTree (l : List (Option Int)) : BinTree := binTreeFromArray l 0 /-- The number of nodes in `t`. -/ def treeSize : BinTree → Nat | BinTree.leaf => 0 | BinTree.node _ l r => 1 + treeSize l + treeSize r /-- Every node value of `t` lies between `0` and `10^4` inclusive. -/ def treeValuesInRange : BinTree → Bool | BinTree.leaf => true | BinTree.node v l r => 0 ≤ v && v ≤ 10000 && treeValuesInRange l && treeValuesInRange r /-- The subtree of `t` at path `p`, where `false` steps left and `true` steps right. -/ def nodeAt : BinTree → List Bool → Option BinTree | t, [] => some t | BinTree.leaf, _ :: _ => none | BinTree.node _ l _, false :: p => nodeAt l p | BinTree.node _ _ r, true :: p => nodeAt r p /-- `selected` picks positions of `root` that hold houses, with no two directly linked. -/ def IsRobberyPlan (root : BinTree) (selected : List Bool → Bool) : Prop := (∀ p, selected p → ∃ v l r, nodeAt root p = some (BinTree.node v l r)) ∧ ∀ p q, selected p → selected q → q ≠ p ++ [false] ∧ q ≠ p ++ [true] /-- The sum of the values at the selected positions of `t`, `path` being the position of `t`. -/ def robberyTotalAt : BinTree → List Bool → (List Bool → Bool) → Nat | BinTree.leaf, _, _ => 0 | BinTree.node v l r, path, selected => (if selected path then v.toNat else 0) + robberyTotalAt l (path ++ [false]) selected + robberyTotalAt r (path ++ [true]) selected /-- The total stolen value of the position selection `selected` on `root`. -/ def RobberyTotal (root : BinTree) (selected : List Bool → Bool) : Nat := robberyTotalAt root [] selected /-! ### Validity predicate (V) -/ /-- Valid input: `1` to `10^4` nodes and every node value between `0` and `10^4`. -/ def isValidInput (input : Input) : Bool := 1 ≤ treeSize input && treeSize input ≤ 10000 && treeValuesInRange input /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest total stolen value over all non-adjacent selections of houses. -/ def maxRobAmount_spec (input : Input) (result : Output) : Prop := IsGreatest {n : Nat | ∃ selected : List Bool → Bool, IsRobberyPlan input selected ∧ RobberyTotal input selected = n} result /-! ### Decidable specification (P_check) -/ /-- A finite selection code containing one Boolean for every node of the tree. -/ def selectionCode : BinTree → Type | BinTree.leaf => Unit | BinTree.node _ left right => Bool × selectionCode left × selectionCode right /-- All Boolean selections of the nodes of `t`. -/ def allSelectionCodes : (t : BinTree) → List (selectionCode t) | BinTree.leaf => [()] | BinTree.node _ left right => [false, true].flatMap fun picked => (allSelectionCodes left).flatMap fun leftCode => (allSelectionCodes right).flatMap fun rightCode => [(picked, leftCode, rightCode)] /-- Whether the root node of `t` is selected by `code`. -/ def selectedRoot : (t : BinTree) → selectionCode t → Bool | BinTree.leaf, _ => false | BinTree.node _ _ _, (picked, _, _) => picked /-- Whether `code` selects no parent together with either of its children. -/ def isRobberyPlanCode : (t : BinTree) → selectionCode t → Bool | BinTree.leaf, _ => true | BinTree.node _ left right, (picked, leftCode, rightCode) => !(picked && selectedRoot left leftCode) && !(picked && selectedRoot right rightCode) && isRobberyPlanCode left leftCode && isRobberyPlanCode right rightCode /-- The total value selected by `code` in `t`. -/ def codeTotal : (t : BinTree) → selectionCode t → Nat | BinTree.leaf, _ => 0 | BinTree.node value left right, (picked, leftCode, rightCode) => (if picked then value.toNat else 0) + codeTotal left leftCode + codeTotal right rightCode /-- Executable checker for `maxRobAmount_spec` over all tree-shaped selections. -/ def maxRobAmount_check (input : Input) (result : Output) : Bool := let codes := allSelectionCodes input List.any codes (fun code => isRobberyPlanCode input code && codeTotal input code == result) && List.all codes (fun code => !isRobberyPlanCode input code || Nat.ble (codeTotal input code) result) /-- The selection function induced by a tree-shaped selection code. -/ def hr3SelOfCode : (t : BinTree) → selectionCode t → List Bool → Bool | BinTree.leaf, _, _ => false | BinTree.node _ _ _, (picked, _, _), [] => picked | BinTree.node _ l _, (_, lc, _), false :: p => hr3SelOfCode l lc p | BinTree.node _ _ r, (_, _, rc), true :: p => hr3SelOfCode r rc p /-- The selection code obtained by restricting `sel` to the nodes of `t` sitting at `path`. -/ def hr3CodeOfSel : (t : BinTree) → List Bool → (List Bool → Bool) → selectionCode t | BinTree.leaf, _, _ => () | BinTree.node _ l r, path, sel => (sel path, hr3CodeOfSel l (path ++ [false]) sel, hr3CodeOfSel r (path ++ [true]) sel) theorem hr3_check_eq (input : Input) (result : Output) : maxRobAmount_check input result = (List.any (allSelectionCodes input) (fun code => isRobberyPlanCode input code && codeTotal input code == result) && List.all (allSelectionCodes input) (fun code => !isRobberyPlanCode input code || Nat.ble (codeTotal input code) result)) := rfl theorem hr3_isGreatest_unfold (S : Set Nat) (r : Nat) : IsGreatest S r ↔ (r ∈ S ∧ ∀ y : Nat, y ∈ S → y ≤ r) := Iff.rfl theorem hr3_mem_allSelectionCodes : ∀ (t : BinTree) (c : selectionCode t), c ∈ allSelectionCodes t := by intro t induction t with | leaf => intro c; simp only [allSelectionCodes, List.mem_cons, List.not_mem_nil, or_false]; rfl | node v l r ihl ihr => intro c obtain ⟨picked, lc, rc⟩ := c rw [allSelectionCodes] simp only [List.mem_flatMap, List.mem_cons, List.mem_singleton, List.not_mem_nil] exact ⟨picked, by cases picked <;> simp, lc, ihl lc, rc, ihr rc, Or.inl rfl⟩ theorem hr3_selOfCode_nil : ∀ (t : BinTree) (c : selectionCode t), hr3SelOfCode t c [] = selectedRoot t c := by intro t c cases t with | leaf => rfl | node v l r => obtain ⟨picked, lc, rc⟩ := c; rfl theorem hr3_robberyTotalAt_selOfCode : ∀ (t : BinTree) (c : selectionCode t) (path : List Bool) (sel : List Bool → Bool), (∀ p, sel (path ++ p) = hr3SelOfCode t c p) → robberyTotalAt t path sel = codeTotal t c := by intro t induction t with | leaf => intro c path sel _; rfl | node v l r ihl ihr => intro c path sel hsel obtain ⟨picked, lc, rc⟩ := c have h0 : sel path = picked := by have h := hsel [] simpa only [List.append_nil, hr3SelOfCode] using h have hL : ∀ p, sel ((path ++ [false]) ++ p) = hr3SelOfCode l lc p := by intro p have h := hsel (false :: p) simpa only [List.append_assoc, List.singleton_append, hr3SelOfCode] using h have hR : ∀ p, sel ((path ++ [true]) ++ p) = hr3SelOfCode r rc p := by intro p have h := hsel (true :: p) simpa only [List.append_assoc, List.singleton_append, hr3SelOfCode] using h simp only [robberyTotalAt, codeTotal, h0, ihl lc (path ++ [false]) sel hL, ihr rc (path ++ [true]) sel hR] theorem hr3_selOfCode_node : ∀ (t : BinTree) (c : selectionCode t) (p : List Bool), hr3SelOfCode t c p = true → ∃ v l r, nodeAt t p = some (BinTree.node v l r) := by intro t induction t with | leaf => intro c p hp; simp only [hr3SelOfCode] at hp; exact absurd hp (by simp) | node v l r ihl ihr => intro c p hp obtain ⟨picked, lc, rc⟩ := c cases p with | nil => exact ⟨v, l, r, rfl⟩ | cons b p' => cases b with | false => simp only [hr3SelOfCode] at hp simpa only [nodeAt] using ihl lc p' hp | true => simp only [hr3SelOfCode] at hp simpa only [nodeAt] using ihr rc p' hp theorem hr3_selOfCode_child : ∀ (t : BinTree) (c : selectionCode t), isRobberyPlanCode t c = true → ∀ (p : List Bool) (bb : Bool), hr3SelOfCode t c p = true → hr3SelOfCode t c (p ++ [bb]) = false := by intro t induction t with | leaf => intro c _ p bb hp; simp only [hr3SelOfCode] at hp; exact absurd hp (by simp) | node v l r ihl ihr => intro c hc p bb hp obtain ⟨picked, lc, rc⟩ := c rw [isRobberyPlanCode] at hc simp only [Bool.and_eq_true] at hc obtain ⟨⟨⟨hc1, hc2⟩, hc3⟩, hc4⟩ := hc cases p with | nil => have hpicked : picked = true := by simpa only [hr3SelOfCode] using hp rw [hpicked] at hc1 hc2 cases bb with | false => have hs : selectedRoot l lc = false := by simpa using hc1 simp only [List.nil_append, hr3SelOfCode] rw [hr3_selOfCode_nil l lc, hs] | true => have hs : selectedRoot r rc = false := by simpa using hc2 simp only [List.nil_append, hr3SelOfCode] rw [hr3_selOfCode_nil r rc, hs] | cons b p' => cases b with | false => simp only [hr3SelOfCode] at hp simpa only [List.cons_append, hr3SelOfCode] using ihl lc hc3 p' bb hp | true => simp only [hr3SelOfCode] at hp simpa only [List.cons_append, hr3SelOfCode] using ihr rc hc4 p' bb hp theorem hr3_isRobberyPlan_selOfCode : ∀ (t : BinTree) (c : selectionCode t), isRobberyPlanCode t c = true → IsRobberyPlan t (hr3SelOfCode t c) := by intro t c hc refine ⟨fun p hp => hr3_selOfCode_node t c p hp, ?_⟩ intro p q hp hq constructor · rintro rfl rw [hr3_selOfCode_child t c hc p false hp] at hq simp at hq · rintro rfl rw [hr3_selOfCode_child t c hc p true hp] at hq simp at hq theorem hr3_codeTotal_codeOfSel : ∀ (t : BinTree) (path : List Bool) (sel : List Bool → Bool), codeTotal t (hr3CodeOfSel t path sel) = robberyTotalAt t path sel := by intro t induction t with | leaf => intro path sel; rfl | node v l r ihl ihr => intro path sel rw [hr3CodeOfSel, codeTotal, robberyTotalAt, ihl, ihr] theorem hr3_selectedRoot_codeOfSel : ∀ (t : BinTree) (path : List Bool) (sel : List Bool → Bool), selectedRoot t (hr3CodeOfSel t path sel) = true → sel path = true := by intro t path sel hs cases t with | leaf => simp only [selectedRoot] at hs; exact absurd hs (by simp) | node v l r => simpa only [hr3CodeOfSel, selectedRoot] using hs theorem hr3_isRobberyPlanCode_codeOfSel : ∀ (t : BinTree) (path : List Bool) (sel : List Bool → Bool), (∀ p q, sel p → sel q → q ≠ p ++ [false] ∧ q ≠ p ++ [true]) → isRobberyPlanCode t (hr3CodeOfSel t path sel) = true := by intro t induction t with | leaf => intro path sel _; rfl | node v l r ihl ihr => intro path sel hsel rw [hr3CodeOfSel, isRobberyPlanCode] simp only [Bool.and_eq_true] refine ⟨⟨⟨?_, ?_⟩, ihl _ sel hsel⟩, ihr _ sel hsel⟩ · cases hsp : sel path with | false => simp | true => cases hsr : selectedRoot l (hr3CodeOfSel l (path ++ [false]) sel) with | false => simp | true => exact absurd rfl (hsel path (path ++ [false]) hsp (hr3_selectedRoot_codeOfSel l (path ++ [false]) sel hsr)).1 · cases hsp : sel path with | false => simp | true => cases hsr : selectedRoot r (hr3CodeOfSel r (path ++ [true]) sel) with | false => simp | true => exact absurd rfl (hsel path (path ++ [true]) hsp (hr3_selectedRoot_codeOfSel r (path ++ [true]) sel hsr)).2 theorem hr3_codes_iff (input : Input) (n : Nat) : (∃ c : selectionCode input, isRobberyPlanCode input c = true ∧ codeTotal input c = n) ↔ (∃ sel : List Bool → Bool, IsRobberyPlan input sel ∧ RobberyTotal input sel = n) := by constructor · rintro ⟨c, hc, rfl⟩ refine ⟨hr3SelOfCode input c, hr3_isRobberyPlan_selOfCode input c hc, ?_⟩ exact hr3_robberyTotalAt_selOfCode input c [] _ (fun p => by rw [List.nil_append]) · rintro ⟨sel, hplan, rfl⟩ exact ⟨hr3CodeOfSel input [] sel, hr3_isRobberyPlanCode_codeOfSel input [] sel hplan.2, hr3_codeTotal_codeOfSel input [] sel⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem maxRobAmount_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : maxRobAmount_check input result ↔ maxRobAmount_spec input result := by rw [hr3_check_eq] unfold maxRobAmount_spec rw [hr3_isGreatest_unfold] simp only [Set.mem_setOf_eq, List.any_eq_true, List.all_eq_true, Bool.and_eq_true, Bool.or_eq_true, beq_iff_eq, Nat.ble_eq] constructor · rintro ⟨⟨c, -, hplan, htot⟩, hub⟩ refine ⟨(hr3_codes_iff input result).mp ⟨c, hplan, htot⟩, ?_⟩ rintro y ⟨sel, hsel, rfl⟩ obtain ⟨c', hc', htot'⟩ := (hr3_codes_iff input (RobberyTotal input sel)).mpr ⟨sel, hsel, rfl⟩ rcases hub c' (hr3_mem_allSelectionCodes input c') with hb | hb · simp [hc'] at hb · omega · rintro ⟨hmem, hub⟩ obtain ⟨c, hc, htot⟩ := (hr3_codes_iff input result).mpr hmem refine ⟨⟨c, hr3_mem_allSelectionCodes input c, hc, htot⟩, ?_⟩ intro c' _ cases hp : isRobberyPlanCode input c' with | false => left; simp | true => right exact hub _ ((hr3_codes_iff input (codeTotal input c')).mp ⟨c', hp, rfl⟩) /-! ### Implementation helpers -/ /-- The pair of optimal totals for a subtree: root selected, root skipped. -/ def robSubtree : BinTree → Nat × Nat | BinTree.leaf => (0, 0) | BinTree.node v l r => let (lRob, lSkip) := robSubtree l let (rRob, rSkip) := robSubtree r (v.toNat + lSkip + rSkip, max lRob lSkip + max rRob rSkip) /-! ### Main algorithm (impl) -/ /-- Maximum stolen total by post-order dynamic programming of rob/skip pairs. -/ def robHouses (input : Input) : Output := let (robbed, skipped) := robSubtree input max robbed skipped /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem robHouses_correct (input : Input) (h : isValidInput input) : maxRobAmount_spec input (robHouses input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (arrayToBinTree [(some 3), (some 2), (some 3), none, (some 3), none, (some 1)]) #guard isValidInput (arrayToBinTree [(some 3), (some 4), (some 5), (some 1), (some 3), none, (some 1)]) #guard isValidInput (arrayToBinTree [(some 0)]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (arrayToBinTree [])) #guard !(isValidInput (arrayToBinTree [(some 10001)])) #guard !(isValidInput (arrayToBinTree [(some (-1))])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard maxRobAmount_check (arrayToBinTree [(some 3), (some 2), (some 3), none, (some 3), none, (some 1)]) 7 #guard maxRobAmount_check (arrayToBinTree [(some 3), (some 4), (some 5), (some 1), (some 3), none, (some 1)]) 9 #guard maxRobAmount_check (arrayToBinTree [(some 0)]) 0 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(maxRobAmount_check (arrayToBinTree [(some 3), (some 2), (some 3), none, (some 3), none, (some 1)]) 5) #guard !(maxRobAmount_check (arrayToBinTree [(some 3), (some 4), (some 5), (some 1), (some 3), none, (some 1)]) 8) #guard !(maxRobAmount_check (arrayToBinTree [(some 0)]) 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard robHouses (arrayToBinTree [(some 3), (some 2), (some 3), none, (some 3), none, (some 1)]) == 7 #guard robHouses (arrayToBinTree [(some 3), (some 4), (some 5), (some 1), (some 3), none, (some 1)]) == 9 #guard robHouses (arrayToBinTree [(some 0)]) == 0 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard maxRobAmount_check (arrayToBinTree [(some 3), (some 2), (some 3), none, (some 3), none, (some 1)]) (robHouses (arrayToBinTree [(some 3), (some 2), (some 3), none, (some 3), none, (some 1)])) #guard maxRobAmount_check (arrayToBinTree [(some 3), (some 4), (some 5), (some 1), (some 3), none, (some 1)]) (robHouses (arrayToBinTree [(some 3), (some 4), (some 5), (some 1), (some 3), none, (some 1)])) #guard maxRobAmount_check (arrayToBinTree [(some 0)]) (robHouses (arrayToBinTree [(some 0)])) end PHouseRobberIii