import Mathlib /-! # Max Increase To Keep City Skyline There is a city composed of n x n blocks, where each block contains a single building shaped like a vertical square prism. You are given a 0-indexed n x n integer matrix grid where grid[r][c] represents the height of the building located in the block at row r and column c. A city's skyline is the outer contour formed by all the building when viewing the side of the city from a distance. The skyline from each cardinal direction north, east, south, and west may be different. We are allowed to increase the height of any number of buildings by any amount (the amount can be different per building). The height of a 0-height building can also be increased. However, increasing the height of a building should not affect the city's skyline from any cardinal direction. Return the maximum total sum that the height of the buildings can be increased by without changing the city's skyline from any cardinal direction. ## Constraints - n == grid.length - n == grid[r].length - 2 <= n <= 50 - 0 <= grid[r][c] <= 100 ## Provided examples - `grid = [[3, 0, 8, 4], [2, 4, 5, 7], [9, 2, 6, 3], [0, 3, 1, 0]]` → `35` - `grid = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]` → `0` - `grid = [[1, 2], [3, 4]]` → `1` ## Synthesized negative examples - invalid input: `grid = [[0, 0], [0, 0], [0, 0]]` ([structural] a predicate that admits n == grid.length. 3 rows, 2 columns; row width n=2, row count differs) - invalid input: `grid = [[0]]` ([structural] a predicate that admits 2 <= n <= 50. 1x1, n=1 below minimum) - invalid input: `grid = [[-1, 0], [0, 0]]` ([structural] a predicate that admits 0 <= grid[r][c] <= 100. cell -1 below nonnegative floor) - `grid = [[3, 0, 8, 4], [2, 4, 5, 7], [9, 2, 6, 3], [0, 3, 1, 0]]` → `34` is wrong ([structural] off-by-one in the maximal total computation. one below the true maximum) - `grid = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]` → `1` is wrong ([structural] answer not required to be attained by a valid increase. raises total above the only feasible value 0) - `grid = [[1, 2], [3, 4]]` → `0` is wrong ([structural] specification states only that the sum is attainable, not that it is maximum. 0 is attained by making no increases, but is not the max.) -/ namespace PMaxIncreaseToKeepCitySkyline abbrev Input := List (List Int) abbrev Output := Int /-! ### Specification helpers -/ /-- The largest entry of `l`, or 0 when `l` is empty. -/ def listMax (l : List Int) : Int := l.foldl max 0 /-- The `c`-th column of `grid`: the `c`-th entry of each row that has one. -/ def colOf (grid : List (List Int)) (c : Nat) : List Int := grid.filterMap (fun row => row[c]?) /-- `newGrid` raises buildings of `grid` keeping all four skylines: same dimensions, no building lowered, and none exceeding its original row or column maximum. -/ def IsValidIncrease (grid newGrid : List (List Int)) : Prop := newGrid.length = grid.length ∧ ∀ r : Nat, ∀ hr : r < grid.length, ∃ hr' : r < newGrid.length, newGrid[r].length = grid[r].length ∧ ∀ c : Nat, ∀ hc : c < grid[r].length, ∃ hc' : c < newGrid[r].length, grid[r][c] ≤ newGrid[r][c] ∧ newGrid[r][c] ≤ min (listMax grid[r]) (listMax (colOf grid c)) /-- The total height added: the sum of the per-building differences from `grid` to `newGrid`. -/ def totalIncrease (grid newGrid : List (List Int)) : Int := ((grid.zip newGrid).map fun (row, newRow) => ((row.zip newRow).map fun (x, y) => y - x).sum).sum /-! ### Validity predicate (V) -/ /-- Valid input: a square grid with side between 2 and 50 and every height between 0 and 100. -/ def isValidInput (input : Input) : Bool := 2 ≤ input.length && input.length ≤ 50 && input.all (fun row => row.length == input.length && row.all (fun h => 0 ≤ h && h ≤ 100)) /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest total increase attained by any skyline-preserving raising of `input`'s buildings. -/ def maxIncreaseKeepingSkyline_spec (input : Input) (result : Output) : Prop := IsGreatest {t : Int | ∃ g : List (List Int), IsValidIncrease input g ∧ totalIncrease input g = t} result /-! ### Decidable specification (P_check) -/ /-- The componentwise-greatest skyline-preserving raising of `grid`: each building lifted to the lesser of its original row maximum and column maximum. -/ def capGrid (grid : List (List Int)) : List (List Int) := grid.map fun row => row.mapIdx fun c _ => min (listMax row) (listMax (colOf grid c)) /-- Decidable form of `IsValidIncrease`: same dimensions, no building lowered, and none exceeding its original row or column maximum. -/ def isValidIncreaseBool (grid newGrid : List (List Int)) : Bool := newGrid.length == grid.length && (grid.zip newGrid).all fun (row, newRow) => newRow.length == row.length && (List.finRange row.length).all fun c => match newRow[c.val]? with | none => false | some y => row[c.val]'c.isLt ≤ y && y ≤ min (listMax row) (listMax (colOf grid c.val)) /-- Executable checker for `maxIncreaseKeepingSkyline_spec`: the cellwise-greatest raising is a valid increase attaining `result`, and its total, which bounds every valid raising's total, is at most `result`. -/ def maxIncreaseKeepingSkyline_check (input : Input) (result : Output) : Bool := isValidIncreaseBool input (capGrid input) && result == totalIncrease input (capGrid input) && totalIncrease input (capGrid input) ≤ result theorem sum_zip_map_le {α β γ : Type} (xs : List α) (ys : List β) (zs : List γ) (f : α → β → Int) (k : α → γ → Int) (hy : ys.length = xs.length) (hz : zs.length = xs.length) (hle : ∀ i : Nat, ∀ hi : i < xs.length, f xs[i] ys[i] ≤ k xs[i] zs[i]) : ((xs.zip ys).map fun p => f p.1 p.2).sum ≤ ((xs.zip zs).map fun p => k p.1 p.2).sum := by induction xs generalizing ys zs with | nil => simp | cons x xs ih => cases ys with | nil => simp at hy | cons y ys => cases zs with | nil => simp at hz | cons z zs => simp only [List.length_cons, Nat.succ.injEq] at hy hz have hhead : f x y ≤ k x z := by have hh := hle 0 (by simp) change f x y ≤ k x z at hh exact hh have htail : ∀ i : Nat, ∀ hi : i < xs.length, f xs[i] ys[i] ≤ k xs[i] zs[i] := by intro i hi have hh := hle (i + 1) (by simp; omega) change f xs[i] ys[i] ≤ k xs[i] zs[i] at hh exact hh have hrest := ih ys zs hy hz htail simp only [List.zip_cons_cons, List.map_cons, List.sum_cons] omega theorem cap_dom (grid g : Input) (hv : IsValidIncrease grid g) : totalIncrease grid g ≤ totalIncrease grid (capGrid grid) := by unfold totalIncrease refine sum_zip_map_le grid g (capGrid grid) (fun row newRow => ((row.zip newRow).map fun p => p.2 - p.1).sum) (fun row newRow => ((row.zip newRow).map fun p => p.2 - p.1).sum) hv.1 ?_ ?_ · simp [capGrid] · intro r hr obtain ⟨hrg, hlen, hcells⟩ := hv.2 r hr have hrcap : r < (capGrid grid).length := by simpa [capGrid] using hr let capRow : List Int := (capGrid grid).get ⟨r, hrcap⟩ have hcaplen : capRow.length = grid[r].length := by simp [capRow, capGrid] refine sum_zip_map_le grid[r] g[r] capRow (fun x y => y - x) (fun x y => y - x) hlen hcaplen ?_ · intro c hc obtain ⟨hcg, _, hupper⟩ := hcells c hc have hcap : capRow[c] = min (listMax grid[r]) (listMax (colOf grid c)) := by simp [capRow, capGrid] rw [hcap] omega theorem root_of_bridges (input : Input) (result : Output) (hv : IsValidIncrease input (capGrid input)) (hb : isValidIncreaseBool input (capGrid input) = true) (hd : ∀ g, IsValidIncrease input g → totalIncrease input g ≤ totalIncrease input (capGrid input)) : maxIncreaseKeepingSkyline_check input result ↔ maxIncreaseKeepingSkyline_spec input result := by simp only [maxIncreaseKeepingSkyline_check, hb, Bool.true_and, Bool.and_eq_true, beq_iff_eq, decide_eq_true_eq] constructor · rintro ⟨rfl, _⟩ exact ⟨⟨capGrid input, hv, rfl⟩, fun _ ⟨g, hg, he⟩ => he ▸ hd g hg⟩ · intro hs have hl := hs.2 (show totalIncrease input (capGrid input) ∈ {t | ∃ g, IsValidIncrease input g ∧ totalIncrease input g = t} from ⟨capGrid input, hv, rfl⟩) obtain ⟨g, hg, he⟩ := hs.1 have hu := hd g hg exact ⟨le_antisymm (he ▸ hu) hl, hl⟩ theorem fold_max_bound (l : List Int) (a x : Int) (hx : x ≤ a ∨ x ∈ l) : x ≤ l.foldl max a := by induction l generalizing a with | nil => simpa using hx | cons y ys ih => simp only [List.foldl_cons] apply ih rcases hx with hx | hx · exact Or.inl (hx.trans (le_max_left _ _)) · rcases List.mem_cons.mp hx with rfl | hx · exact Or.inl (le_max_right _ _) · exact Or.inr hx theorem cell_le_cap (grid : Input) (row : List Int) (hr : row ∈ grid) (c : Nat) (hc : c < row.length) : row[c] ≤ min (listMax row) (listMax (colOf grid c)) := by apply le_min · exact fold_max_bound row 0 row[c] (Or.inr (List.getElem_mem hc)) · apply fold_max_bound _ 0 _ (Or.inr ?_) exact List.mem_filterMap.mpr ⟨row, hr, List.getElem?_eq_some_iff.mpr ⟨hc, rfl⟩⟩ theorem cap_valid (grid : Input) : IsValidIncrease grid (capGrid grid) := by refine ⟨by simp [capGrid], ?_⟩ intro r hr refine ⟨by simpa [capGrid] using hr, by simp [capGrid], ?_⟩ intro c hc refine ⟨by simpa [capGrid] using hc, ?_⟩ simp only [capGrid, List.getElem_map, List.getElem_mapIdx] exact ⟨cell_le_cap grid grid[r] (List.getElem_mem hr) c hc, le_rfl⟩ theorem root_with_valid (input : Input) (result : Output) (hb : isValidIncreaseBool input (capGrid input) = true) (hd : ∀ g, IsValidIncrease input g → totalIncrease input g ≤ totalIncrease input (capGrid input)) : maxIncreaseKeepingSkyline_check input result ↔ maxIncreaseKeepingSkyline_spec input result := root_of_bridges input result (cap_valid input) hb hd theorem cap_bool (grid : Input) : isValidIncreaseBool grid (capGrid grid) = true := by simp only [isValidIncreaseBool, capGrid, List.length_map, beq_self_eq_true, Bool.true_and, List.zip_eq_zipWith, List.zipWith_map_right, List.zipWith_self, List.all_map, List.all_eq_true] intro row hr simp only [Function.comp_apply, List.length_mapIdx, beq_self_eq_true, Bool.true_and, List.all_eq_true] intro c hc simp [List.getElem?_mapIdx, List.getElem?_eq_getElem c.isLt, cell_le_cap grid row hr c.val c.isLt] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem maxIncreaseKeepingSkyline_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : maxIncreaseKeepingSkyline_check input result ↔ maxIncreaseKeepingSkyline_spec input result := by exact root_of_bridges input result (cap_valid input) (cap_bool input) (cap_dom input) /-! ### Main algorithm (impl) -/ /-- Maximum total increase: raise every building to the lesser of its row and column maximum (the checker's `capGrid`) and sum the per-building differences with `totalIncrease`. -/ def maxIncreaseKeepingSkylineImpl (input : Input) : Output := totalIncrease input (capGrid input) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem maxIncreaseKeepingSkylineImpl_correct (input : Input) (h : isValidInput input) : maxIncreaseKeepingSkyline_spec input (maxIncreaseKeepingSkylineImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [[3, 0, 8, 4], [2, 4, 5, 7], [9, 2, 6, 3], [0, 3, 1, 0]] #guard isValidInput [[0, 0, 0], [0, 0, 0], [0, 0, 0]] #guard isValidInput [[1, 2], [3, 4]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput [[0, 0], [0, 0], [0, 0]]) #guard !(isValidInput [[0]]) #guard !(isValidInput [[(-1), 0], [0, 0]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard maxIncreaseKeepingSkyline_check [[3, 0, 8, 4], [2, 4, 5, 7], [9, 2, 6, 3], [0, 3, 1, 0]] 35 #guard maxIncreaseKeepingSkyline_check [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 0 #guard maxIncreaseKeepingSkyline_check [[1, 2], [3, 4]] 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(maxIncreaseKeepingSkyline_check [[3, 0, 8, 4], [2, 4, 5, 7], [9, 2, 6, 3], [0, 3, 1, 0]] 34) #guard !(maxIncreaseKeepingSkyline_check [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 1) #guard !(maxIncreaseKeepingSkyline_check [[1, 2], [3, 4]] 0) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard maxIncreaseKeepingSkylineImpl [[3, 0, 8, 4], [2, 4, 5, 7], [9, 2, 6, 3], [0, 3, 1, 0]] == 35 #guard maxIncreaseKeepingSkylineImpl [[0, 0, 0], [0, 0, 0], [0, 0, 0]] == 0 #guard maxIncreaseKeepingSkylineImpl [[1, 2], [3, 4]] == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard maxIncreaseKeepingSkyline_check [[3, 0, 8, 4], [2, 4, 5, 7], [9, 2, 6, 3], [0, 3, 1, 0]] (maxIncreaseKeepingSkylineImpl [[3, 0, 8, 4], [2, 4, 5, 7], [9, 2, 6, 3], [0, 3, 1, 0]]) #guard maxIncreaseKeepingSkyline_check [[0, 0, 0], [0, 0, 0], [0, 0, 0]] (maxIncreaseKeepingSkylineImpl [[0, 0, 0], [0, 0, 0], [0, 0, 0]]) #guard maxIncreaseKeepingSkyline_check [[1, 2], [3, 4]] (maxIncreaseKeepingSkylineImpl [[1, 2], [3, 4]]) end PMaxIncreaseToKeepCitySkyline