import Mathlib /-! # The Skyline Problem A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively. The geometric information of each building is given in the array buildings where buildings[i] = [left_i, right_i, height_i]: left_i is the x coordinate of the left edge of the ith building. right_i is the x coordinate of the right edge of the ith building. height_i is the height of the ith building. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0. The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour. Note: There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2, 3],[4, 5],[7, 5],[11, 5],[12, 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...,[2, 3],[4, 5],[12, 7],...] ## Constraints - 1 <= buildings.length <= 10^4 - 0 <= left_i < right_i <= 2^31 - 1 - 1 <= height_i <= 2^31 - 1 - buildings is sorted by left_i in non-decreasing order. ## Provided examples - `buildings = [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]` → `[[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]` - `buildings = [[0, 2, 3], [2, 5, 3]]` → `[[0, 3], [5, 0]]` - `buildings = [[1, 2, 1], [1, 2, 2], [1, 2, 3]]` → `[[1, 3], [2, 0]]` ## Synthesized negative examples - invalid input: `buildings = []` ([structural] a predicate that admits 1 <= buildings.length <= 10^4. per-building checker accepts vacuously) - invalid input: `buildings = [[-1, 2, 1]]` ([structural] a predicate that admits 0 <= lefti < righti <= 2^31 - 1. predicate checking only left max acc b[1]!) 0 /-- The greatest height among the buildings covering integer coordinate `x`, 0 when none covers it. -/ def SkylineHeight (buildings : List (List Int)) (x : Int) : Int := (buildings.filterMap fun b => match b with | [l, r, h] => if l ≤ x ∧ x < r then some h else none | _ => none).foldl max 0 /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 10^4 triples `[left, right, height]` with `0 ≤ left < right ≤ 2^31 - 1`, `1 ≤ height ≤ 2^31 - 1`, sorted by `left`. -/ def isValidInput (input : Input) : Bool := decide (1 ≤ input.length) && decide (input.length ≤ 10000) && input.all (fun b => decide (b.length = 3) && decide (0 ≤ b[0]!) && decide (b[0]! < b[1]!) && decide (b[1]! ≤ 2147483647) && decide (1 ≤ b[2]!) && decide (b[2]! ≤ 2147483647)) && (input.zip input.tail).all (fun p => decide (p.1[0]! ≤ p.2[0]!)) /-! ### Ideal specification (P_spec) -/ /-- `result` is the skyline contour of `input`: at least two key points of strictly increasing x from the first building's left edge to the greatest right edge, ending at height 0 with distinct adjacent heights, and every segment between adjacent points lies at the skyline height. -/ def skyline_spec (input : Input) (result : Output) : Prop := 2 ≤ result.length ∧ (∀ p ∈ result, p.length = 2) ∧ result.Chain' (fun p q => pointX p < pointX q) ∧ result.head?.map pointX = input.head?.map (·[0]!) ∧ result.getLast?.map pointX = some (maxRight input) ∧ result.getLast?.map pointY = some 0 ∧ result.Chain' (fun p q => pointY p ≠ pointY q) ∧ result.Chain' (fun p q => ∀ x : Int, pointX p ≤ x → x < pointX q → SkylineHeight input x = pointY p) /-! ### Decidable specification (P_check) -/ /-- The integers of the half-open interval `[lo, hi)`, empty when `hi ≤ lo`. -/ def intIco (lo hi : Int) : List Int := (List.range (hi - lo).toNat).map fun n => lo + (n : Int) /-- `true` exactly when every adjacent pair of `l` satisfies `r`. -/ def adjacentAll {α : Type} (l : List α) (r : α → α → Bool) : Bool := (l.zip l.tail).all fun pq => r pq.1 pq.2 /-- Executable checker for `skyline_spec`, truncating each segment's integer quantifier to that segment's integer range. -/ def skyline_check (input : Input) (result : Output) : Bool := decide (2 ≤ result.length) && result.all (fun p => decide (p.length = 2)) && adjacentAll result (fun p q => decide (pointX p < pointX q)) && decide (result.head?.map pointX = input.head?.map (·[0]!)) && decide (result.getLast?.map pointX = some (maxRight input)) && decide (result.getLast?.map pointY = some 0) && adjacentAll result (fun p q => pointY p != pointY q) && adjacentAll result (fun p q => (intIco (pointX p) (pointX q)).all fun x => decide (SkylineHeight input x = pointY p)) theorem skyline_root_of_bridges (hadj : ∀ {α : Type} (l : List α) (r : α → α → Bool), adjacentAll l r = true ↔ l.Chain' (fun a b => r a b = true)) (hmem : ∀ lo hi x : Int, x ∈ intIco lo hi ↔ lo ≤ x ∧ x < hi) (input : Input) (result : Output) : skyline_check input result ↔ skyline_spec input result := by simp [skyline_check, skyline_spec, hadj, List.all_eq_true, hmem, and_assoc] theorem skyline_adjacent_bridge {α : Type} (l : List α) (r : α → α → Bool) : adjacentAll l r = true ↔ l.Chain' (fun a b => r a b = true) := by induction l with | nil => simp [adjacentAll, List.Chain'] | cons a l ih => cases l with | nil => simp [adjacentAll, List.Chain'] | cons b l => change (r a b && adjacentAll (b :: l) r) = true ↔ _ simp only [Bool.and_eq_true, List.Chain', List.isChain_cons_cons] at ih ⊢ exact and_congr Iff.rfl ih theorem skyline_interval_bridge (lo hi x : Int) : x ∈ intIco lo hi ↔ lo ≤ x ∧ x < hi := by simp [intIco] trace_state constructor · rintro ⟨n, hn, rfl⟩ trace_state omega · rintro ⟨hlo, hhi⟩ refine ⟨(x - lo).toNat, ?_, ?_⟩ <;> omega /-- On valid input the checker accepts exactly the specified outputs. -/ theorem skyline_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : skyline_check input result ↔ skyline_spec input result := by exact skyline_root_of_bridges skyline_adjacent_bridge skyline_interval_bridge input result /-! ### Implementation helpers -/ /-- The two-point skyline `[[l, h], [r, 0]]` of one valid building `[l, r, h]`. -/ def skylineOfBuilding (b : List Int) : Output := [[b[0]!, b[2]!], [b[1]!, 0]] /-- Merge two x-sorted skylines into one, scanning points in x order and emitting `[x, max h1 h2]` only when the running maximum height changes. -/ def mergeSkylines : Output → Output → Int → Int → Int → Output → Output | [], [], _, _, _, acc => acc.reverse | p :: s1, [], _, h2, cur, acc => let m := max (pointY p) h2 mergeSkylines s1 [] (pointY p) h2 m (if m = cur then acc else [pointX p, m] :: acc) | [], q :: s2, h1, _, cur, acc => let m := max h1 (pointY q) mergeSkylines [] s2 h1 (pointY q) m (if m = cur then acc else [pointX q, m] :: acc) | p :: s1, q :: s2, h1, h2, cur, acc => if pointX p < pointX q then let m := max (pointY p) h2 mergeSkylines s1 (q :: s2) (pointY p) h2 m (if m = cur then acc else [pointX p, m] :: acc) else if pointX q < pointX p then let m := max h1 (pointY q) mergeSkylines (p :: s1) s2 h1 (pointY q) m (if m = cur then acc else [pointX q, m] :: acc) else let m := max (pointY p) (pointY q) mergeSkylines s1 s2 (pointY p) (pointY q) m (if m = cur then acc else [pointX p, m] :: acc) termination_by a b _ _ _ _ => a.length + b.length decreasing_by all_goals (simp only [List.length_cons, List.length_nil]; omega) /-! ### Main algorithm (impl) -/ /-- Skyline by divide and conquer: halve the building list, compute each half's skyline recursively, and merge the two polylines with a two-pointer scan, in O(n log n). -/ def computeSkyline (buildings : Input) : Output := match buildings with | [] => [] | [b] => skylineOfBuilding b | b1 :: b2 :: rest => mergeSkylines (computeSkyline ((b1 :: b2 :: rest).take ((b1 :: b2 :: rest).length / 2))) (computeSkyline ((b1 :: b2 :: rest).drop ((b1 :: b2 :: rest).length / 2))) 0 0 0 [] termination_by buildings.length decreasing_by · simp only [List.length_take, List.length_cons] omega · simp only [List.length_drop, List.length_cons] omega /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem computeSkyline_correct (input : Input) (h : isValidInput input) : skyline_spec input (computeSkyline input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]] #guard isValidInput [[0, 2, 3], [2, 5, 3]] #guard isValidInput [[1, 2, 1], [1, 2, 2], [1, 2, 3]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [[-1, 2, 1]]) #guard !(isValidInput [[1, 1, 1]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard skyline_check [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]] [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]] #guard skyline_check [[0, 2, 3], [2, 5, 3]] [[0, 3], [5, 0]] #guard skyline_check [[1, 2, 1], [1, 2, 2], [1, 2, 3]] [[1, 3], [2, 0]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(skyline_check [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]] [[2, 10], [3, 15], [5, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]) #guard !(skyline_check [[0, 2, 3], [2, 5, 3]] [[0, 3], [2, 3], [5, 0]]) #guard !(skyline_check [[1, 2, 1], [1, 2, 2], [1, 2, 3]] [[1, 3], [3, 0]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard computeSkyline [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]] == [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]] #guard computeSkyline [[0, 2, 3], [2, 5, 3]] == [[0, 3], [5, 0]] #guard computeSkyline [[1, 2, 1], [1, 2, 2], [1, 2, 3]] == [[1, 3], [2, 0]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard skyline_check [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]] (computeSkyline [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]) #guard skyline_check [[0, 2, 3], [2, 5, 3]] (computeSkyline [[0, 2, 3], [2, 5, 3]]) #guard skyline_check [[1, 2, 1], [1, 2, 2], [1, 2, 3]] (computeSkyline [[1, 2, 1], [1, 2, 2], [1, 2, 3]]) end PTheSkylineProblem