import Mathlib /-! # As Far From Land As Possible Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1. The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|. ## Constraints - n == grid.length - n == grid[i].length - 1 <= n <= 100 - grid[i][j] is 0 or 1 ## Provided examples - `grid = [[1, 0, 1], [0, 0, 0], [1, 0, 1]]` → `2` - `grid = [[1, 0, 0], [0, 0, 0], [0, 0, 0]]` → `4` - `grid = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]` → `-1` ## Synthesized negative examples - invalid input: `grid = []` ([structural] a predicate that admits 1 <= n <= 100. empty grid is below the minimum n; no cell checks see it) - invalid input: `grid = [[1, 0], [0, 1], [1, 1]]` ([structural] a predicate that admits n == grid[i].length. three rows of width two; a predicate checking only values accepts) - invalid input: `grid = [[1, 2], [0, 1]]` ([structural] a predicate that admits grid[i][j] is 0 or 1. a 2 where only 0 or 1 is allowed; nonzero-as-land accepts this) - `grid = [[1, 0, 1], [0, 0, 0], [1, 0, 1]]` → `1` is wrong ([structural] maximality stated as achievability alone. 1 is a valid nearest-land distance but not the greatest) - `grid = [[1, 0, 0], [0, 0, 0], [0, 0, 0]]` → `5` is wrong ([structural] answer need not be a distance attained by any water cell. 5 exceeds every grid distance) - `grid = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]` → `0` is wrong ([structural] the no-water special case is dropped; max over an empty water set defaults to 0. all-land grid returns 0 rather than -1) -/ namespace PAsFarFromLandAsPossible abbrev Input := List (List Nat) abbrev Output := Int /-! ### Specification helpers -/ /-- Cell (i,j) exists in grid and holds value v. -/ def CellValue (grid : List (List Nat)) (i j v : Nat) : Prop := ∃ row : List Nat, grid[i]? = some row ∧ row[j]? = some v /-- Manhattan distance between cells (i,j) and (k,l), as an Int. -/ def ManhattanDist (i j k l : Nat) : Int := (((i - k) + (k - i) + (j - l) + (l - j) : Nat) : Int) /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty square grid of side at most 100 with all cells 0 or 1. -/ def isValidInput (input : Input) : Bool := decide (1 ≤ input.length) && decide (input.length ≤ 100) && input.all (fun row => row.length == input.length) && input.all (fun row => row.all (fun v => v == 0 || v == 1)) /-! ### Ideal specification (P_spec) -/ /-- `result` is -1 exactly when land or water is absent, and otherwise the greatest nearest-land Manhattan distance attained by any water cell. -/ def maxDistance_spec (input : Input) (result : Output) : Prop := (result = -1 ↔ (¬ ∃ i j, CellValue input i j 1) ∨ (¬ ∃ i j, CellValue input i j 0)) ∧ ((∃ i j, CellValue input i j 1) → (∃ i j, CellValue input i j 0) → IsGreatest {d : Int | ∃ i j, CellValue input i j 0 ∧ IsLeast {d' : Int | ∃ k l, CellValue input k l 1 ∧ ManhattanDist i j k l = d'} d} result) /-! ### Decidable specification (P_check) -/ /-- Boolean analogue of `CellValue`: cell (i,j) of `grid` exists and holds `v`. -/ def cellValueEq (grid : List (List Nat)) (i j v : Nat) : Bool := match grid[i]? with | some row => row[j]? == some v | none => false /-- Whether some cell of the `n × n` index square of `input` holds value `v`. -/ def hasCellValue (input : Input) (n : Nat) (v : Nat) : Bool := decide (∃ i ∈ List.range n, ∃ j ∈ List.range n, cellValueEq input i j v = true) /-- Executable checker for `maxDistance_spec`, scanning the finite `n × n` index square. -/ def maxDistance_check (input : Input) (result : Output) : Bool := let n := input.length let hasLand := hasCellValue input n 1 let hasWater := hasCellValue input n 0 ((result == -1) == (!hasLand || !hasWater)) && (!hasLand || !hasWater || (decide (∃ i ∈ List.range n, ∃ j ∈ List.range n, cellValueEq input i j 0 = true ∧ (∃ k ∈ List.range n, ∃ l ∈ List.range n, cellValueEq input k l 1 = true ∧ ManhattanDist i j k l = result) ∧ (∀ k ∈ List.range n, ∀ l ∈ List.range n, cellValueEq input k l 1 = true → result ≤ ManhattanDist i j k l)) && decide (∀ i ∈ List.range n, ∀ j ∈ List.range n, cellValueEq input i j 0 = true → ∃ k ∈ List.range n, ∃ l ∈ List.range n, cellValueEq input k l 1 = true ∧ ManhattanDist i j k l ≤ result))) /-- The Boolean cell test agrees with the declarative `CellValue`. -/ theorem cellValueEq_iff_cellValue (grid : List (List Nat)) (i j v : Nat) : cellValueEq grid i j v = true ↔ CellValue grid i j v := by unfold cellValueEq CellValue cases hg : grid[i]? with | none => simp | some row => simp /-- On valid input every occupied cell index lies inside the `n × n` index square. -/ theorem cellValue_bounds {input : Input} (h : isValidInput input = true) {i j v : Nat} (hc : CellValue input i j v) : i < input.length ∧ j < input.length := by obtain ⟨row, hrow, hcell⟩ := hc obtain ⟨hi, hget⟩ := List.getElem?_eq_some_iff.mp hrow obtain ⟨hj, -⟩ := List.getElem?_eq_some_iff.mp hcell refine ⟨hi, ?_⟩ have hmem : row ∈ input := hget ▸ List.getElem_mem hi have hall : input.all (fun r => r.length == input.length) = true := by unfold isValidInput at h simp only [Bool.and_eq_true] at h exact h.1.2 have hlen : row.length = input.length := by have := List.all_eq_true.mp hall row hmem simpa using this omega /-- The bounded `hasCellValue` scan sees exactly the unbounded existential. -/ theorem hasCellValue_iff_exists {input : Input} (h : isValidInput input = true) (v : Nat) : hasCellValue input input.length v = true ↔ ∃ i j, CellValue input i j v := by unfold hasCellValue rw [decide_eq_true_iff] constructor · rintro ⟨i, -, j, -, hc⟩ exact ⟨i, j, (cellValueEq_iff_cellValue input i j v).mp hc⟩ · rintro ⟨i, j, hc⟩ obtain ⟨hi, hj⟩ := cellValue_bounds h hc exact ⟨i, List.mem_range.mpr hi, j, List.mem_range.mpr hj, (cellValueEq_iff_cellValue input i j v).mpr hc⟩ /-- The nearest-land distance set of any cell has a least element when land exists. -/ theorem exists_isLeast_dist {input : Input} (hL : ∃ i j, CellValue input i j 1) (i j : Nat) : ∃ d : Int, IsLeast {d' : Int | ∃ k l, CellValue input k l 1 ∧ ManhattanDist i j k l = d'} d := by obtain ⟨k0, l0, hk0⟩ := hL obtain ⟨d, hd, hlb⟩ := Int.exists_least_of_bdd (P := fun d' : Int => ∃ k l, CellValue input k l 1 ∧ ManhattanDist i j k l = d') ⟨0, by rintro z ⟨k, l, -, rfl⟩ simp only [ManhattanDist] exact Int.natCast_nonneg _⟩ ⟨ManhattanDist i j k0 l0, k0, l0, hk0, rfl⟩ exact ⟨d, hd, fun z hz => hlb z hz⟩ /-- The checker's first decided clause is membership in the specification's set. -/ theorem check_mem_iff {input : Input} (h : isValidInput input = true) (result : Output) : (∃ i ∈ List.range input.length, ∃ j ∈ List.range input.length, cellValueEq input i j 0 = true ∧ (∃ k ∈ List.range input.length, ∃ l ∈ List.range input.length, cellValueEq input k l 1 = true ∧ ManhattanDist i j k l = result) ∧ (∀ k ∈ List.range input.length, ∀ l ∈ List.range input.length, cellValueEq input k l 1 = true → result ≤ ManhattanDist i j k l)) ↔ (∃ i j, CellValue input i j 0 ∧ IsLeast {d' : Int | ∃ k l, CellValue input k l 1 ∧ ManhattanDist i j k l = d'} result) := by constructor · rintro ⟨i, -, j, -, hw, ⟨k, -, l, -, hkl, hdist⟩, hlbc⟩ refine ⟨i, j, (cellValueEq_iff_cellValue input i j 0).mp hw, ⟨⟨k, l, (cellValueEq_iff_cellValue input k l 1).mp hkl, hdist⟩, ?_⟩⟩ rintro x ⟨k', l', hk', rfl⟩ obtain ⟨hk1, hl1⟩ := cellValue_bounds h hk' exact hlbc k' (List.mem_range.mpr hk1) l' (List.mem_range.mpr hl1) ((cellValueEq_iff_cellValue input k' l' 1).mpr hk') · rintro ⟨i, j, hw, ⟨k, l, hkl, hdist⟩, hlbs⟩ obtain ⟨hi, hj⟩ := cellValue_bounds h hw obtain ⟨hk1, hl1⟩ := cellValue_bounds h hkl refine ⟨i, List.mem_range.mpr hi, j, List.mem_range.mpr hj, (cellValueEq_iff_cellValue input i j 0).mpr hw, ⟨k, List.mem_range.mpr hk1, l, List.mem_range.mpr hl1, (cellValueEq_iff_cellValue input k l 1).mpr hkl, hdist⟩, ?_⟩ intro k' _ l' _ hk' exact hlbs ⟨k', l', (cellValueEq_iff_cellValue input k' l' 1).mp hk', rfl⟩ /-- The checker's second decided clause is the specification's upper-bound clause. -/ theorem check_ub_iff {input : Input} (h : isValidInput input = true) (result : Output) (hL : ∃ i j, CellValue input i j 1) : (∀ i ∈ List.range input.length, ∀ j ∈ List.range input.length, cellValueEq input i j 0 = true → ∃ k ∈ List.range input.length, ∃ l ∈ List.range input.length, cellValueEq input k l 1 = true ∧ ManhattanDist i j k l ≤ result) ↔ (∀ d : Int, (∃ i j, CellValue input i j 0 ∧ IsLeast {d' : Int | ∃ k l, CellValue input k l 1 ∧ ManhattanDist i j k l = d'} d) → d ≤ result) := by constructor · rintro hchk d ⟨i, j, hw, hleast⟩ obtain ⟨hi, hj⟩ := cellValue_bounds h hw obtain ⟨k, -, l, -, hkl, hle⟩ := hchk i (List.mem_range.mpr hi) j (List.mem_range.mpr hj) ((cellValueEq_iff_cellValue input i j 0).mpr hw) exact le_trans (hleast.2 ⟨k, l, (cellValueEq_iff_cellValue input k l 1).mp hkl, rfl⟩) hle · intro hub i _ j _ hw obtain ⟨d, hd⟩ := exists_isLeast_dist hL i j have hdle : d ≤ result := hub d ⟨i, j, (cellValueEq_iff_cellValue input i j 0).mp hw, hd⟩ obtain ⟨k, l, hkl, hdist⟩ := hd.1 obtain ⟨hk1, hl1⟩ := cellValue_bounds h hkl exact ⟨k, List.mem_range.mpr hk1, l, List.mem_range.mpr hl1, (cellValueEq_iff_cellValue input k l 1).mpr hkl, by rw [hdist]; exact hdle⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem maxDistance_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : maxDistance_check input result ↔ maxDistance_spec input result := by have hLf : hasCellValue input input.length 1 = false ↔ ¬ (∃ i j, CellValue input i j 1) := by rw [← hasCellValue_iff_exists h 1, Bool.not_eq_true] have hWf : hasCellValue input input.length 0 = false ↔ ¬ (∃ i j, CellValue input i j 0) := by rw [← hasCellValue_iff_exists h 0, Bool.not_eq_true] unfold maxDistance_check maxDistance_spec simp only [Bool.and_eq_true, Bool.or_eq_true, Bool.not_eq_true', beq_iff_eq, decide_eq_true_eq] rw [Bool.eq_iff_iff] simp only [Bool.or_eq_true, Bool.not_eq_true', beq_iff_eq, hLf, hWf] constructor · rintro ⟨h1, h2⟩ refine ⟨h1, ?_⟩ intro hL hW rcases h2 with (hnl | hnw) | ⟨hd, he⟩ · exact absurd hL hnl · exact absurd hW hnw · exact ⟨(check_mem_iff h result).mp hd, fun d hd' => (check_ub_iff h result hL).mp he d hd'⟩ · rintro ⟨h1, h2⟩ refine ⟨h1, ?_⟩ by_cases hL : (∃ i j, CellValue input i j 1) · by_cases hW : (∃ i j, CellValue input i j 0) · have hg := h2 hL hW exact Or.inr ⟨(check_mem_iff h result).mpr hg.1, (check_ub_iff h result hL).mpr (fun d hd => hg.2 hd)⟩ · exact Or.inl (Or.inr hW) · exact Or.inl (Or.inl hL) /-! ### Implementation helpers -/ /-- Top-left to bottom-right sweep building the distance table, seeded with 0 on land and a sentinel on water. -/ def forwardPass (grid : List (List Nat)) (n : Nat) : Array (Array Nat) := let init := (List.range n).foldl (fun acc i => acc.push ((List.range n).foldl (fun row j => row.push (if cellValueEq grid i j 1 then 0 else 10000)) (#[] : Array Nat))) (#[] : Array (Array Nat)) (List.range n).foldl (fun (d : Array (Array Nat)) i => (List.range n).foldl (fun (d : Array (Array Nat)) j => let cur := (d[i]!)[j]! let left := if j = 0 then 10000 else (d[i]!)[j - 1]! + 1 let up := if i = 0 then 10000 else (d[i - 1]!)[j]! + 1 d.set! i (d[i]!.set! j (min cur (min left up)))) d) init /-- Bottom-right to top-left sweep improving each distance with the right and down neighbors. -/ def backwardPass (table : Array (Array Nat)) (n : Nat) : Array (Array Nat) := (List.range n).reverse.foldl (fun (d : Array (Array Nat)) i => (List.range n).reverse.foldl (fun (d : Array (Array Nat)) j => let cur := (d[i]!)[j]! let right := if j + 1 ≥ n then 10000 else (d[i]!)[j + 1]! + 1 let down := if i + 1 ≥ n then 10000 else (d[i + 1]!)[j]! + 1 d.set! i (d[i]!.set! j (min cur (min right down)))) d) table /-- Largest table entry over water cells, or -1 when none contributes. -/ def maxOverWater (grid : List (List Nat)) (table : Array (Array Nat)) (n : Nat) : Int := (List.range n).foldl (fun best i => (List.range n).foldl (fun best j => if cellValueEq grid i j 0 then max best ((table[i]!)[j]! : Int) else best) best) (-1) /-! ### Main algorithm (impl) -/ /-- Two-pass distance transform computing the maximum nearest-land Manhattan distance over water cells. -/ def maxDistanceToNearestLand (input : Input) : Output := let n := input.length if !hasCellValue input n 1 || !hasCellValue input n 0 then -1 else maxOverWater input (backwardPass (forwardPass input n) n) n /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem maxDistanceToNearestLand_correct (input : Input) (h : isValidInput input) : maxDistance_spec input (maxDistanceToNearestLand input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [[1, 0, 1], [0, 0, 0], [1, 0, 1]] #guard isValidInput [[1, 0, 0], [0, 0, 0], [0, 0, 0]] #guard isValidInput [[1, 1, 1], [1, 1, 1], [1, 1, 1]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [[1, 0], [0, 1], [1, 1]]) #guard !(isValidInput [[1, 2], [0, 1]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard maxDistance_check [[1, 0, 1], [0, 0, 0], [1, 0, 1]] 2 #guard maxDistance_check [[1, 0, 0], [0, 0, 0], [0, 0, 0]] 4 #guard maxDistance_check [[1, 1, 1], [1, 1, 1], [1, 1, 1]] (-1) /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(maxDistance_check [[1, 0, 1], [0, 0, 0], [1, 0, 1]] 1) #guard !(maxDistance_check [[1, 0, 0], [0, 0, 0], [0, 0, 0]] 5) #guard !(maxDistance_check [[1, 1, 1], [1, 1, 1], [1, 1, 1]] 0) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard maxDistanceToNearestLand [[1, 0, 1], [0, 0, 0], [1, 0, 1]] == 2 #guard maxDistanceToNearestLand [[1, 0, 0], [0, 0, 0], [0, 0, 0]] == 4 #guard maxDistanceToNearestLand [[1, 1, 1], [1, 1, 1], [1, 1, 1]] == -1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard maxDistance_check [[1, 0, 1], [0, 0, 0], [1, 0, 1]] (maxDistanceToNearestLand [[1, 0, 1], [0, 0, 0], [1, 0, 1]]) #guard maxDistance_check [[1, 0, 0], [0, 0, 0], [0, 0, 0]] (maxDistanceToNearestLand [[1, 0, 0], [0, 0, 0], [0, 0, 0]]) #guard maxDistance_check [[1, 1, 1], [1, 1, 1], [1, 1, 1]] (maxDistanceToNearestLand [[1, 1, 1], [1, 1, 1], [1, 1, 1]]) end PAsFarFromLandAsPossible