import Mathlib /-! # Trapping Rain Water Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. ## Constraints - n == height.length - 1 <= n <= 2 * 10^4 - 0 <= height[i] <= 10^5 ## Provided examples - `height = [4, 2, 0, 3, 2, 5]` → `9` - `height = [1]` → `0` - `height = [2, 0, 2]` → `2` ## Synthesized negative examples - invalid input: `height = []` ([structural] a predicate that admits 1 <= n <= 2 * 10^4. empty elevation map has no bars) - invalid input: `height = [-1]` ([structural] a predicate that admits 0 <= height[i] <= 10^5. checks only upper bound and length, misses non-negative) - invalid input: `height = [100001]` ([structural] a predicate that admits 0 <= height[i] <= 10^5. checks only non-negativity and length, misses upper bound) - `height = [4, 2, 0, 3, 2, 5]` → `8` is wrong ([structural] total is computed one unit short. eight is one less than the true nine) - `height = [1]` → `1` is wrong ([structural] no requirement that the answer be computed from trapped water; trivial first element accepted. returns height[0] = 1) - `height = [2, 0, 2]` → `3` is wrong ([structural] answer not required to be realizable. exceeds actual capacity of 2) -/ namespace PTrappingRainWater abbrev Input := List Int abbrev Output := Int /-! ### Specification helpers -/ /-- `water` is a valid assignment of non-negative depths, one per bar, where the water surface at each bar is bounded by some bar weakly to its left and some bar weakly to its right. -/ def ValidWaterAssignment (height water : List Int) : Prop := ∃ h : water.length = height.length, ∀ i : Fin height.length, 0 ≤ water[i.cast h.symm] ∧ (∃ j : Fin height.length, j ≤ i ∧ height[i] + water[i.cast h.symm] ≤ height[j]) ∧ (∃ j : Fin height.length, i ≤ j ∧ height[i] + water[i.cast h.symm] ≤ height[j]) /-! ### Validity predicate (V) -/ /-- Valid input: between 1 and 20000 bar heights, each between 0 and 100000. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 2 * 10^4 && input.all (fun h => 0 ≤ h && h ≤ 10^5) /-! ### Ideal specification (P_spec) -/ /-- `result` is the largest total trapped volume attained by any valid water assignment for `input`. -/ def trappedWater_spec (input : Input) (result : Output) : Prop := IsGreatest {n | ∃ water : List Int, ValidWaterAssignment input water ∧ water.sum = n} result /-! ### Decidable specification (P_check) -/ /-- Maximum of an integer list, with `0` for the empty list. -/ def intListMax : List Int → Int | [] => 0 | x :: xs => max x (intListMax xs) /-- Weak maximum bar height at or left of `i`. -/ def leftMax (height : List Int) (i : Fin height.length) : Int := intListMax (height.take (i.val + 1)) /-- Weak maximum bar height at or right of `i`. -/ def rightMax (height : List Int) (i : Fin height.length) : Int := intListMax (height.drop i.val) /-- Largest legal water depth over bar `i`. -/ def waterCapacity (height : List Int) (i : Fin height.length) : Int := max 0 (min (leftMax height i) (rightMax height i) - height.get i) /-- Greatest total trapped volume, summed over all bars. -/ def totalCapacity (height : List Int) : Int := ((List.finRange height.length).map (waterCapacity height)).sum /-- Executable checker for `trappedWater_spec`. -/ def trappedWater_check (input : Input) (result : Output) : Bool := decide (result = totalCapacity input) theorem root_of_bridges (input : Input) (result : Output) (hg : trappedWater_spec input (totalCapacity input)) : trappedWater_check input result ↔ trappedWater_spec input result := by simp only [trappedWater_check, decide_eq_true_eq] constructor · rintro rfl exact hg · intro hr exact le_antisymm (hg.2 hr.1) (hr.2 hg.1) theorem sum_eq_indexed (xs : List Int) (n : Nat) (h : xs.length = n) : xs.sum = ((List.finRange n).map (fun i => xs[i.cast h.symm])).sum := by subst n simp [← List.ofFn_eq_map] theorem capacity_greatest_of_pointwise (height : List Int) (hp : ∀ (i : Fin height.length) (d : Int), (0 ≤ d ∧ (∃ j : Fin height.length, j ≤ i ∧ height[i] + d ≤ height[j]) ∧ (∃ j : Fin height.length, i ≤ j ∧ height[i] + d ≤ height[j])) ↔ (0 ≤ d ∧ d ≤ waterCapacity height i)) : trappedWater_spec height (totalCapacity height) := by change (∃ water, ValidWaterAssignment height water ∧ water.sum = totalCapacity height) ∧ ∀ n, (∃ water, ValidWaterAssignment height water ∧ water.sum = n) → n ≤ totalCapacity height constructor · refine ⟨List.ofFn (waterCapacity height), ?_, ?_⟩ · refine ⟨by simp, ?_⟩ intro i have hc := (hp i (waterCapacity height i)).mpr ⟨le_max_left _ _, le_rfl⟩ simpa using hc · exact congrArg List.sum List.ofFn_eq_map · rintro n ⟨water, ⟨hlen, hw⟩, rfl⟩ rw [sum_eq_indexed water height.length hlen] exact List.sum_le_sum fun i _ => ((hp i _).mp (hw i)).2 theorem root_of_pointwise (bridge : ∀ (height : List Int), (∀ x ∈ height, 0 ≤ x) → ∀ (i : Fin height.length) (d : Int), (0 ≤ d ∧ (∃ j : Fin height.length, j ≤ i ∧ height[i] + d ≤ height[j]) ∧ (∃ j : Fin height.length, i ≤ j ∧ height[i] + d ≤ height[j])) ↔ (0 ≤ d ∧ d ≤ waterCapacity height i)) (input : Input) (result : Output) (h : isValidInput input) : trappedWater_check input result ↔ trappedWater_spec input result := by have hn : ∀ x ∈ input, 0 ≤ x := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true] at h exact fun x hx => (h.2 x hx).1 exact root_of_bridges input result (capacity_greatest_of_pointwise input (bridge input hn)) theorem capacity_intListMax_ge_mem {xs : List Int} {x : Int} (hx : x ∈ xs) : x ≤ intListMax xs := by induction xs with | nil => simp at hx | cons a xs ih => simp only [intListMax] rcases (List.mem_cons.mp hx) with rfl | hx · exact le_max_left _ _ · exact le_trans (ih hx) (le_max_right _ _) theorem capacity_intListMax_mem (xs : List Int) (hne : xs ≠ []) (hn : ∀ x ∈ xs, 0 ≤ x) : intListMax xs ∈ xs := by induction xs with | nil => exact (hne rfl).elim | cons a xs ih => cases xs with | nil => simp only [intListMax] rw [max_eq_left (hn a (by simp))] simp | cons b bs => change max a (intListMax (b :: bs)) ∈ a :: b :: bs by_cases h : a ≤ intListMax (b :: bs) · rw [max_eq_right h] exact List.mem_cons_of_mem a (ih (by simp) (fun x hx => hn x (List.mem_cons_of_mem a hx))) · rw [max_eq_left (le_of_not_ge h)] exact List.mem_cons_self theorem capacity_mem_left {height : List Int} (i j : Fin height.length) (hji : j ≤ i) : height[j] ∈ height.take (i.val + 1) := by rw [List.mem_take_iff_getElem] refine ⟨j.val, ?_, rfl⟩ omega theorem capacity_mem_right {height : List Int} (i j : Fin height.length) (hij : i ≤ j) : height[j] ∈ height.drop i.val := by rw [List.mem_drop_iff_getElem] refine ⟨j.val - i.val, ?_, ?_⟩ · omega · have heq : i.val + (j.val - i.val) = j.val := by omega simpa [heq] theorem capacity_left_witness_iff (height : List Int) (i : Fin height.length) (t : Int) (hn : ∀ x ∈ height, 0 ≤ x) : (∃ j : Fin height.length, j ≤ i ∧ t ≤ height[j]) ↔ t ≤ leftMax height i := by constructor · rintro ⟨j, hji, ht⟩ exact le_trans ht (capacity_intListMax_ge_mem (capacity_mem_left i j hji)) · intro ht have hiMem : height[i] ∈ height.take (i.val + 1) := capacity_mem_left i i le_rfl have hne : height.take (i.val + 1) ≠ [] := by intro he rw [he] at hiMem simp at hiMem have hnTake : ∀ x ∈ height.take (i.val + 1), 0 ≤ x := by intro x hx exact hn x (List.mem_of_mem_take hx) have hm := capacity_intListMax_mem (height.take (i.val + 1)) hne hnTake rw [List.mem_take_iff_getElem] at hm rcases hm with ⟨k, hk, heq⟩ have hklen : k < height.length := by omega let j : Fin height.length := ⟨k, hklen⟩ refine ⟨j, ?_, ?_⟩ · change k ≤ i.val omega · unfold leftMax at ht change t ≤ height[k] simpa [heq] using ht theorem capacity_right_witness_iff (height : List Int) (i : Fin height.length) (t : Int) (hn : ∀ x ∈ height, 0 ≤ x) : (∃ j : Fin height.length, i ≤ j ∧ t ≤ height[j]) ↔ t ≤ rightMax height i := by constructor · rintro ⟨j, hij, ht⟩ exact le_trans ht (capacity_intListMax_ge_mem (capacity_mem_right i j hij)) · intro ht have hiMem : height[i] ∈ height.drop i.val := capacity_mem_right i i le_rfl have hne : height.drop i.val ≠ [] := by intro he rw [he] at hiMem simp at hiMem have hnDrop : ∀ x ∈ height.drop i.val, 0 ≤ x := by intro x hx exact hn x (List.mem_of_mem_drop hx) have hm := capacity_intListMax_mem (height.drop i.val) hne hnDrop rw [List.mem_drop_iff_getElem] at hm rcases hm with ⟨k, hk, heq⟩ have hidx : i.val + k < height.length := by omega let j : Fin height.length := ⟨i.val + k, hidx⟩ refine ⟨j, ?_, ?_⟩ · change i.val ≤ i.val + k omega · unfold rightMax at ht change t ≤ height[i.val + k] exact heq.symm ▸ ht theorem capacity_pointwise (height : List Int) (hn : ∀ x ∈ height, 0 ≤ x) (i : Fin height.length) (d : Int) : (0 ≤ d ∧ (∃ j : Fin height.length, j ≤ i ∧ height[i] + d ≤ height[j]) ∧ (∃ j : Fin height.length, i ≤ j ∧ height[i] + d ≤ height[j])) ↔ (0 ≤ d ∧ d ≤ waterCapacity height i) := by rw [capacity_left_witness_iff height i (height[i] + d) hn, capacity_right_witness_iff height i (height[i] + d) hn] have hleft : height[i] ≤ leftMax height i := capacity_intListMax_ge_mem (capacity_mem_left i i le_rfl) have hright : height[i] ≤ rightMax height i := capacity_intListMax_ge_mem (capacity_mem_right i i le_rfl) have hnonneg : 0 ≤ min (leftMax height i) (rightMax height i) - height[i] := by omega unfold waterCapacity simp only [List.get_eq_getElem, Fin.getElem_fin] at * rw [max_eq_right hnonneg] omega /-- On valid input the checker accepts exactly the specified outputs. -/ theorem trappedWater_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : trappedWater_check input result ↔ trappedWater_spec input result := by exact root_of_pointwise capacity_pointwise input result h /-! ### Implementation helpers -/ /-- Running maxima from the left: the `i`-th element is the maximum of `height.take (i + 1)`. -/ def leftMaxima : List Int → List Int | [] => [] | x :: xs => x :: (leftMaxima xs).map (max x) /-- Running maxima from the right: the `i`-th element is the maximum of `height.drop i`. -/ def rightMaxima (height : List Int) : List Int := (leftMaxima height.reverse).reverse /-- Water trapped above bar `i` given precomputed left and right maxima. -/ def capacityAt (height lMaxima rMaxima : List Int) (i : Nat) : Int := max 0 (min (lMaxima.getD i 0) (rMaxima.getD i 0) - height.getD i 0) /-- Total trapped water summed over all bars from precomputed maxima. -/ def totalCapacityFast (height : List Int) : Int := let lMaxima := leftMaxima height let rMaxima := rightMaxima height ((List.finRange height.length).map (fun i => capacityAt height lMaxima rMaxima i.val)).sum /-! ### Main algorithm (impl) -/ /-- Linear two-pointer worker for trapped rain water over an array: shrinks the window `[l, r]` from the side with the lower bar, carrying the running left and right maxima and the accumulated water. Each step moves `l` up or `r` down, so `r - l` strictly decreases. -/ def trapRainWaterAux (h : Array Int) (l r : Nat) (lMax rMax water : Int) : Int := if hl : l < r then if h[l]! < h[r]! then if lMax ≤ h[l]! then trapRainWaterAux h (l + 1) r h[l]! rMax water else trapRainWaterAux h (l + 1) r lMax rMax (water + lMax - h[l]!) else if rMax ≤ h[r]! then trapRainWaterAux h l (r - 1) lMax h[r]! water else trapRainWaterAux h l (r - 1) lMax rMax (water + rMax - h[r]!) else water termination_by r - l decreasing_by all_goals first | (rw [← Nat.sub_sub]; exact Nat.sub_lt (Nat.sub_pos_of_lt hl) (Nat.succ_pos 0)) | (rw [Nat.sub_sub, Nat.add_comm 1 l, ← Nat.sub_sub]; exact Nat.sub_lt (Nat.sub_pos_of_lt hl) (Nat.succ_pos 0)) /-- Trapped rain water in O(n) time: copies the heights into an array for O(1) access and runs the two-pointer worker over the full range. -/ def trapRainWater (input : Input) : Output := let h := input.toArray trapRainWaterAux h 0 (h.size - 1) 0 0 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem trapRainWater_correct (input : Input) (h : isValidInput input) : trappedWater_spec input (trapRainWater input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [4, 2, 0, 3, 2, 5] #guard isValidInput [1] #guard isValidInput [2, 0, 2] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [(-1)]) #guard !(isValidInput [100001]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard trappedWater_check [4, 2, 0, 3, 2, 5] 9 #guard trappedWater_check [1] 0 #guard trappedWater_check [2, 0, 2] 2 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(trappedWater_check [4, 2, 0, 3, 2, 5] 8) #guard !(trappedWater_check [1] 1) #guard !(trappedWater_check [2, 0, 2] 3) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard trapRainWater [4, 2, 0, 3, 2, 5] == 9 #guard trapRainWater [1] == 0 #guard trapRainWater [2, 0, 2] == 2 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard trappedWater_check [4, 2, 0, 3, 2, 5] (trapRainWater [4, 2, 0, 3, 2, 5]) #guard trappedWater_check [1] (trapRainWater [1]) #guard trappedWater_check [2, 0, 2] (trapRainWater [2, 0, 2]) end PTrappingRainWater