import Mathlib /-! # Maximum Width Ramp A ramp in an integer array nums is a pair (i, j) for which i < j and nums[i] <= nums[j]. The width of such a ramp is j - i. Given an integer array nums, return the maximum width of a ramp in nums. If there is no ramp in nums, return 0. ## Constraints - 2 <= nums.length <= 5 * 10^4 - 0 <= nums[i] <= 5 * 10^4 ## Provided examples - `nums = [6, 0, 8, 2, 1, 5]` → `4` - `nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1]` → `7` - `nums = [0, 0, 0, 0, 0]` → `4` ## Synthesized negative examples - invalid input: `nums = [0]` ([structural] a predicate that admits 2 <= nums.length <= 5 * 10^4. one element below minimum; a predicate that only special-cases empty accepts it) - invalid input: `nums = [0, -1]` ([structural] a predicate that admits 0 <= nums[i] <= 5 * 10^4. negative one step below non-negative floor; a ceiling-only check accepts it) - invalid input: `nums = [0, 50001]` ([structural] a predicate that admits 0 <= nums[i] <= 5 * 10^4. one past stated maximum; a floor-only check accepts it) - `nums = [6, 0, 8, 2, 1, 5]` → `3` is wrong ([structural] maximum width stated as achievability alone. 3 is a real ramp width, but 4 is wider) - `nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1]` → `8` is wrong ([structural] no ramp is required to attain the reported width. no ramp has width 8; spec accepts any upper bound) - `nums = [0, 0, 0, 0, 0]` → `3` is wrong ([structural] maximality stated as achievability alone. 3 is a real ramp width but 4 is larger) -/ namespace PMaximumWidthRamp abbrev Input := List Int abbrev Output := Nat /-! ### Specification helpers -/ /-- Indices `i` and `j` form a ramp in `nums`: both in bounds, `i < j`, and `nums[i] ≤ nums[j]`. -/ def IsRamp (nums : List Int) (i j : Nat) : Prop := ∃ hi : i < nums.length, ∃ hj : j < nums.length, i < j ∧ nums[i]'hi ≤ nums[j]'hj /-- `w` is an admissible answer for `nums`: either `0`, or the width `j - i` of a ramp. -/ def AttainableWidth (nums : List Int) (w : Nat) : Prop := w = 0 ∨ ∃ i j, IsRamp nums i j ∧ w = j - i /-! ### Validity predicate (V) -/ /-- Valid input: length between 2 and 5·10⁴, with every element between 0 and 5·10⁴. -/ def isValidInput (input : Input) : Bool := 2 ≤ input.length && input.length ≤ 5 * 10^4 && input.all (fun x => 0 ≤ x && x ≤ 5 * 10^4) /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest admissible width for `input`: the maximum ramp width, or 0 if none. -/ def maxWidthRamp_spec (input : Input) (result : Output) : Prop := IsGreatest {w | AttainableWidth input w} result /-! ### Decidable specification (P_check) -/ /-- Helper for `IsRamp`: an existential `∃ h : p, q h` over proofs of a decidable proposition `p` is decidable, because any two proofs of `p` are equal, so the body only needs to be decided at one canonical proof. -/ instance decExistsProp (p : Prop) [instp : Decidable p] (q : p → Prop) [instq : ∀ h, Decidable (q h)] : Decidable (∃ h : p, q h) := match instp with | isTrue hp => match instq hp with | isTrue hq => isTrue ⟨hp, hq⟩ | isFalse hq => isFalse fun h => hq (Subsingleton.elim h.1 hp ▸ h.2) | isFalse hp => isFalse fun h => hp h.1 /-- Decides `IsRamp nums i j`: after unfolding, it is a pair of proof-existentials (decided by `decExistsProp`) around decidable arithmetic on the list entries. -/ instance decIsRamp (nums : List Int) (i j : Nat) : Decidable (IsRamp nums i j) := inferInstanceAs (Decidable (∃ hi : i < nums.length, ∃ hj : j < nums.length, i < j ∧ nums[i]'hi ≤ nums[j]'hj)) /-- Decides `AttainableWidth nums w`: a ramp uses indices below `nums.length`, so the unbounded existential over `i j` reduces to the bounded search `∃ i < nums.length, ∃ j < nums.length, IsRamp nums i j ∧ w = j - i`. -/ instance decAttainableWidth (nums : List Int) (w : Nat) : Decidable (AttainableWidth nums w) := decidable_of_iff (w = 0 ∨ ∃ i < nums.length, ∃ j < nums.length, IsRamp nums i j ∧ w = j - i) (by unfold AttainableWidth constructor · rintro (h | ⟨i, hi, j, hj, hramp, hwidth⟩) · exact Or.inl h · exact Or.inr ⟨i, j, hramp, hwidth⟩ · rintro (h | ⟨i, j, hramp, hwidth⟩) · exact Or.inl h · have hramp' := hramp unfold IsRamp at hramp' obtain ⟨hi, hj, -, -⟩ := hramp' exact Or.inr ⟨i, hi, j, hj, hramp, hwidth⟩) /-- Decides the unfolded `maxWidthRamp_spec`, namely `IsGreatest {w | AttainableWidth input w} result`: membership is decided by `decAttainableWidth`, and the upper-bound condition only needs checking for `w < input.length`, since every nonzero attainable width is `j - i` with `j < input.length`. -/ instance decMaxWidthRamp (input : List Int) (result : Nat) : Decidable (IsGreatest {w | AttainableWidth input w} result) := decidable_of_iff (AttainableWidth input result ∧ ∀ w < input.length, AttainableWidth input w → w ≤ result) (by unfold IsGreatest upperBounds simp only [Set.mem_setOf_eq] constructor · rintro ⟨hres, hub⟩ refine ⟨hres, fun a hAw => ?_⟩ unfold AttainableWidth at hAw rcases hAw with h | ⟨i, j, hramp, hwidth⟩ · subst h exact Nat.zero_le _ · subst hwidth have hb : j - i < input.length := by have h := hramp unfold IsRamp at h obtain ⟨hi, hj, -, -⟩ := h omega exact hub (j - i) hb (Or.inr ⟨i, j, hramp, rfl⟩) · rintro ⟨hres, hub⟩ exact ⟨hres, fun w _ hAw => hub hAw⟩) /-- Executable checker obtained mechanically from the specification. -/ def maxWidthRamp_check (input : Input) (result : Output) : Bool := @decide (maxWidthRamp_spec input result) (by unfold maxWidthRamp_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem maxWidthRamp_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : maxWidthRamp_check input result ↔ maxWidthRamp_spec input result := by simp [maxWidthRamp_check] /-! ### Implementation helpers -/ /-- Fold left over the enumerated list, keeping a strictly decreasing stack of candidate left indices with the top at the head. -/ def buildStack (l : List (Nat × Int)) : List (Nat × Int) := l.foldl (fun st p => match st with | [] => [p] | top :: _ => if p.2 < top.2 then p :: st else st) [] /-- Pop every stack entry whose value is ≤ `v`, updating the best width with right endpoint `j`, and return what remains. -/ def popForRight (j : Nat) (v : Int) (st : List (Nat × Int)) (best : Nat) : List (Nat × Int) × Nat := match st with | [] => ([], best) | (i, vi) :: rest => if vi ≤ v then popForRight j v rest (max best (j - i)) else (st, best) /-- Scan the reversed enumerated list, popping candidate left indices valid for each right endpoint and tracking the maximum width. -/ def scanRight (rev : List (Nat × Int)) (st : List (Nat × Int)) (best : Nat) : Nat := match rev with | [] => best | (j, v) :: rest => let (st', best') := popForRight j v st best scanRight rest st' best' /-! ### Main algorithm (impl) -/ /-- Maximum ramp width by a monotonic stack of candidate left indices scanned against right endpoints from right to left. -/ def maximumWidthRamp (input : Input) : Output := let indexed := (List.range input.length).zip input scanRight indexed.reverse (buildStack indexed) 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem maximumWidthRamp_correct (input : Input) (h : isValidInput input) : maxWidthRamp_spec input (maximumWidthRamp input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [6, 0, 8, 2, 1, 5] #guard isValidInput [9, 8, 1, 0, 1, 9, 4, 0, 4, 1] #guard isValidInput [0, 0, 0, 0, 0] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput [0]) #guard !(isValidInput [0, (-1)]) #guard !(isValidInput [0, 50001]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard maxWidthRamp_check [6, 0, 8, 2, 1, 5] 4 #guard maxWidthRamp_check [9, 8, 1, 0, 1, 9, 4, 0, 4, 1] 7 #guard maxWidthRamp_check [0, 0, 0, 0, 0] 4 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(maxWidthRamp_check [6, 0, 8, 2, 1, 5] 3) #guard !(maxWidthRamp_check [9, 8, 1, 0, 1, 9, 4, 0, 4, 1] 8) #guard !(maxWidthRamp_check [0, 0, 0, 0, 0] 3) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard maximumWidthRamp [6, 0, 8, 2, 1, 5] == 4 #guard maximumWidthRamp [9, 8, 1, 0, 1, 9, 4, 0, 4, 1] == 7 #guard maximumWidthRamp [0, 0, 0, 0, 0] == 4 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard maxWidthRamp_check [6, 0, 8, 2, 1, 5] (maximumWidthRamp [6, 0, 8, 2, 1, 5]) #guard maxWidthRamp_check [9, 8, 1, 0, 1, 9, 4, 0, 4, 1] (maximumWidthRamp [9, 8, 1, 0, 1, 9, 4, 0, 4, 1]) #guard maxWidthRamp_check [0, 0, 0, 0, 0] (maximumWidthRamp [0, 0, 0, 0, 0]) end PMaximumWidthRamp