import Mathlib /-! # Container With Most Water You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container. ## Constraints - n == height.length - 2 <= n <= 10^5 - 0 <= height[i] <= 10^4 ## Provided examples - `height = [1, 8, 6, 2, 5, 4, 8, 3, 7]` → `49` - `height = [1, 1]` → `1` - `height = [1, 2, 1]` → `2` ## Synthesized negative examples - invalid input: `height = [-1, 1]` ([structural] a predicate that admits 0 <= height[i] <= 10^4. negative height; catches a predicate checking only the upper bound) - invalid input: `height = [10001, 1]` ([structural] a predicate that admits 0 <= height[i] <= 10^4. one past the maximum; catches a predicate checking only the lower bound) - invalid input: `height = [1]` ([structural] a predicate that admits 2 <= n <= 10^5. one line below the minimum of two) - `height = [1, 8, 6, 2, 5, 4, 8, 3, 7]` → `40` is wrong ([structural] maximality stated as achievability alone. 40 is area of pair (1,6) but not maximum) - `height = [1, 1]` → `2` is wrong ([structural] capacity formula uses the sum of the two heights instead of the minimum. with sum formula the only pair gives 2) - `height = [1, 2, 1]` → `1` is wrong ([structural] maximality stated as achievability alone. 1 is a real pair's area but not the maximum) -/ namespace PContainerWithMostWater abbrev Input := List Int abbrev Output := Nat /-! ### Specification helpers -/ /-- `ContainerArea height i j a` means the lines at `i < j` form a container of area `a`. -/ def ContainerArea (height : List Int) (i j : Nat) (a : Nat) : Prop := i < j ∧ j < height.length ∧ a = (min (height.getD i 0) (height.getD j 0)).toNat * (j - i) /-! ### Validity predicate (V) -/ /-- Valid input: at least two lines, at most 100000 lines, and every height between 0 and 10000. -/ def isValidInput (input : Input) : Bool := decide (2 ≤ input.length) && decide (input.length ≤ 100000) && input.all (fun h => decide (0 ≤ h ∧ h ≤ 10000)) /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest area attained by any pair of distinct in-bounds lines. -/ def maxArea_spec (input : Input) (result : Output) : Prop := IsGreatest {a : Nat | ∃ i j : Nat, ContainerArea input i j a} result /-! ### Decidable specification (P_check) -/ /-- The finite set of areas formed by every valid pair of lines in `input`. -/ def containerAreas (input : Input) : Finset Nat := (((Finset.range input.length).product (Finset.range input.length)).filter fun p => p.1 < p.2).image fun p => (min (input.getD p.1 0) (input.getD p.2 0)).toNat * (p.2 - p.1) /-- Executable checker for `maxArea_spec`: `result` is attained and bounds every pair's area. -/ def maxArea_check (input : Input) (result : Output) : Bool := decide (result ∈ containerAreas input) && decide (∀ a ∈ containerAreas input, a ≤ result) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem maxArea_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : maxArea_check input result ↔ maxArea_spec input result := by classical simp [maxArea_check, maxArea_spec, IsGreatest, upperBounds, containerAreas, ContainerArea] grind only [] /-! ### Implementation helpers -/ /-- The input list as an array, giving the scan constant-time index access. -/ def heightsArr (input : List Int) : Array Int := input.toArray /-- The water area between the lines at indices `i` and `j` of `arr`. -/ def areaBetween (arr : Array Int) (i j : Nat) : Nat := (min (arr.getD i 0) (arr.getD j 0)).toNat * (j - i) /-- Running maximum of the areas seen while the pointers close in from `l` and `r`. -/ def maxAreaLoop (arr : Array Int) (l r best : Nat) : Nat := if h : l < r then let best' := Nat.max best (areaBetween arr l r) if arr.getD l 0 ≤ arr.getD r 0 then maxAreaLoop arr (l + 1) r best' else maxAreaLoop arr l (r - 1) best' else best termination_by r - l /-! ### Main algorithm (impl) -/ /-- Maximum container area by a two-pointer scan that moves the shorter wall inward. -/ def maxContainerArea (input : Input) : Output := let arr := heightsArr input if arr.size < 2 then 0 else maxAreaLoop arr 0 (arr.size - 1) 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem maxContainerArea_correct (input : Input) (h : isValidInput input) : maxArea_spec input (maxContainerArea input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 8, 6, 2, 5, 4, 8, 3, 7] #guard isValidInput [1, 1] #guard isValidInput [1, 2, 1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput [(-1), 1]) #guard !(isValidInput [10001, 1]) #guard !(isValidInput [1]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard maxArea_check [1, 8, 6, 2, 5, 4, 8, 3, 7] 49 #guard maxArea_check [1, 1] 1 #guard maxArea_check [1, 2, 1] 2 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(maxArea_check [1, 8, 6, 2, 5, 4, 8, 3, 7] 40) #guard !(maxArea_check [1, 1] 2) #guard !(maxArea_check [1, 2, 1] 1) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard maxContainerArea [1, 8, 6, 2, 5, 4, 8, 3, 7] == 49 #guard maxContainerArea [1, 1] == 1 #guard maxContainerArea [1, 2, 1] == 2 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard maxArea_check [1, 8, 6, 2, 5, 4, 8, 3, 7] (maxContainerArea [1, 8, 6, 2, 5, 4, 8, 3, 7]) #guard maxArea_check [1, 1] (maxContainerArea [1, 1]) #guard maxArea_check [1, 2, 1] (maxContainerArea [1, 2, 1]) end PContainerWithMostWater