import Mathlib /-! # Shortest Path In Binary Matrix Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1. A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that: All the visited cells of the path are 0. All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner). The length of a clear path is the number of visited cells of this path. ## Constraints - n == grid.length - n == grid[i].length - 1 <= n <= 100 - grid[i][j] is 0 or 1 ## Provided examples - `grid = [[0, 1], [1, 0]]` → `2` - `grid = [[0, 0, 0], [1, 1, 0], [1, 1, 0]]` → `4` - `grid = [[1, 0, 0], [1, 1, 0], [1, 1, 0]]` → `-1` ## Synthesized negative examples - invalid input: `grid = []` ([structural] a predicate that admits 1 <= n <= 100. empty grid, below the minimum n of one) - invalid input: `grid = [[0, 1], [0, 1, 0]]` ([structural] a predicate that admits n == grid[i].length. catches a predicate that checks only the first row) - invalid input: `grid = [[0, 0], [0, 2]]` ([structural] a predicate that admits grid[i][j] is 0 or 1. value 2 above the allowed maximum) - `grid = [[0, 1], [1, 0]]` → `1` is wrong ([structural] answer need not be achieved by any clear path. 1 is below every clear path length) - `grid = [[0, 0, 0], [1, 1, 0], [1, 1, 0]]` → `2` is wrong ([structural] answer is a lower bound not required to be attained by any clear path. No clear path has length 2; it is below every attainable length.) - `grid = [[1, 0, 0], [1, 1, 0], [1, 1, 0]]` → `0` is wrong ([structural] no-path sentinel may be 0 instead of -1. no path returns default zero, a trivial no-work answer) -/ namespace PShortestPathInBinaryMatrix abbrev Input := List (List Nat) abbrev Output := Int /-! ### Specification helpers -/ /-- `path` is a clear path in `grid`: it runs from (0,0) to (n-1,n-1), visits only 0-cells, and consecutive cells are distinct and 8-directionally adjacent. -/ def IsClearPath (grid : List (List Nat)) (path : List (Nat × Nat)) : Prop := path.head? = some (0, 0) ∧ path.getLast? = some (grid.length - 1, grid.length - 1) ∧ (∀ c ∈ path, (grid[c.1]?.bind fun row => row[c.2]?) = some 0) ∧ path.Chain' fun a b => a ≠ b ∧ Nat.dist a.1 b.1 ≤ 1 ∧ Nat.dist a.2 b.2 ≤ 1 /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 100 rows, every row as long as the row count, every entry 0 or 1. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 100 && input.all fun row => row.length == input.length && row.all fun x => x == 0 || x == 1 /-! ### Ideal specification (P_spec) -/ /-- `result` is -1 when no clear path exists, otherwise the length of one clear path that no clear path undercuts. -/ def shortestClearPath_spec (input : Input) (result : Output) : Prop := ((¬ ∃ p : List (Nat × Nat), IsClearPath input p) ∧ result = -1 ∨ ∃ p : List (Nat × Nat), IsClearPath input p ∧ (p.length : Int) = result) ∧ ∀ p : List (Nat × Nat), IsClearPath input p → result ≤ (p.length : Int) /-! ### Decidable specification (P_check) -/ /-- Boolean reading of the spec's adjacency chain: consecutive cells are distinct and 8-directionally adjacent. -/ def chainAdjB : List (Nat × Nat) → Bool | a :: b :: xs => decide (a ≠ b) && decide (Nat.dist a.1 b.1 ≤ 1) && decide (Nat.dist a.2 b.2 ≤ 1) && chainAdjB (b :: xs) | _ => true /-- Boolean reading of `IsClearPath` with the same four clauses. -/ def clearPathB (grid : List (List Nat)) (path : List (Nat × Nat)) : Bool := path.head? == some (0, 0) && path.getLast? == some (grid.length - 1, grid.length - 1) && path.all (fun c => (grid[c.1]?.bind fun row => row[c.2]?) == some 0) && chainAdjB path /-- One-cell continuations of a reversed partial path: unvisited in-grid 0-cells adjacent to its latest cell. -/ def pathExtensions (grid : List (List Nat)) (revPath : List (Nat × Nat)) : List (List (Nat × Nat)) := match revPath with | [] => [] | c :: rest => ((List.product (List.range grid.length) (List.range grid.length)).filter fun d => decide (c ≠ d) && decide (Nat.dist c.1 d.1 ≤ 1) && decide (Nat.dist c.2 d.2 ≤ 1) && !((c :: rest).contains d) && ((grid[d.1]?.bind fun row => row[d.2]?) == some 0)).map fun d => d :: c :: rest /-- All reversed loop-free paths from (0, 0) through 0-cells of `grid`, after `fuel` extension rounds. -/ def genRevPaths (grid : List (List Nat)) : Nat → List (List (Nat × Nat)) | 0 => [[(0, 0)]] | fuel + 1 => let prev := genRevPaths grid fuel prev ++ prev.flatMap (pathExtensions grid) /-- Executable checker for `shortestClearPath_spec` over the loop-free paths of `input`. -/ def shortestClearPath_check (input : Input) (result : Output) : Bool := let paths := (genRevPaths input (input.length * input.length)).map List.reverse ((!(paths.any fun p => clearPathB input p) && result == (-1)) || paths.any fun p => clearPathB input p && decide ((p.length : Int) = result)) && paths.all fun p => !(clearPathB input p) || decide (result ≤ (p.length : Int)) theorem wx_loopErase {α : Type} [DecidableEq α] (R : α → α → Prop) (l : List α) (hl : List.IsChain R l) : ∃ q : List α, q.head? = l.head? ∧ q.getLast? = l.getLast? ∧ (∀ x ∈ q, x ∈ l) ∧ List.IsChain R q ∧ q.Nodup ∧ q.length ≤ l.length := by match l with | [] => exact ⟨[], rfl, rfl, (by simp), .nil, List.nodup_nil, Nat.le_refl 0⟩ | a :: as => by_cases ha : a ∈ as · obtain ⟨u, v, huv⟩ := List.mem_iff_append.mp ha subst as have hsuf : List.IsChain R (a :: v) := by have hdrop := hl.drop (u.length + 1) simpa using hdrop obtain ⟨q, hhead, hlast, hmem, hchain, hnodup, hlen⟩ := wx_loopErase R (a :: v) hsuf refine ⟨q, ?_, ?_, ?_, hchain, hnodup, ?_⟩ · simpa using hhead · calc q.getLast? = (a :: v).getLast? := hlast _ = ((a :: u) ++ a :: v).getLast? := (List.getLast?_append_cons (a :: u) a v).symm _ = (a :: (u ++ a :: v)).getLast? := by rw [List.cons_append] · intro x hx have hx' : x ∈ a :: v := hmem x hx simp only [List.mem_cons, List.mem_append] at hx' ⊢ aesop · simp only [List.length_cons, List.length_append] at hlen ⊢ omega · obtain ⟨q, hhead, hlast, hmem, hchain, hnodup, hlen⟩ := wx_loopErase R as hl.tail cases q with | nil => have has : as = [] := by cases as with | nil => rfl | cons b bs => simp at hhead subst as exact ⟨[a], rfl, rfl, by simp, by simp, by simp, by simp⟩ | cons b bs => have hab : R a b := by cases as with | nil => simp at hhead | cons c cs => simp only [List.head?_cons, Option.some.injEq] at hhead subst c exact hl.rel refine ⟨a :: b :: bs, rfl, ?_, ?_, ?_, ?_, ?_⟩ · calc (b :: bs).getLast? = as.getLast? := hlast _ = (a :: as).getLast? := by cases as <;> simp_all · intro x hx simp only [List.mem_cons] at hx ⊢ rcases hx with rfl | hx · exact Or.inl rfl · exact Or.inr (hmem x (by simpa using hx)) · exact List.IsChain.cons_cons hab hchain · apply List.nodup_cons.mpr refine ⟨?_, hnodup⟩ intro ham exact ha (hmem a ham) · simp only [List.length_cons] at hlen ⊢ omega termination_by l.length decreasing_by · simp_all · simp_all theorem wx_shorten (grid : Input) (p : List (Nat × Nat)) (hp : IsClearPath grid p) : ∃ q : List (Nat × Nat), IsClearPath grid q ∧ q.Nodup ∧ q.length ≤ p.length := by obtain ⟨q, hhead, hlast, hmem, hchain, hnodup, hlen⟩ := wx_loopErase (fun a b : Nat × Nat => a ≠ b ∧ Nat.dist a.1 b.1 ≤ 1 ∧ Nat.dist a.2 b.2 ≤ 1) p hp.2.2.2 refine ⟨q, ?_, hnodup, hlen⟩ refine ⟨hhead.trans hp.1, hlast.trans hp.2.1, ?_, hchain⟩ intro c hc exact hp.2.2.1 c (hmem c hc) lemma wx_chain (p : List (Nat × Nat)) : chainAdjB p = true ↔ p.IsChain (fun a b => a ≠ b ∧ Nat.dist a.1 b.1 ≤ 1 ∧ Nat.dist a.2 b.2 ≤ 1) := by induction p using List.twoStepInduction with | nil => simp [chainAdjB] | singleton a => simp [chainAdjB] | cons_cons a b l ih1 ih2 => simp [chainAdjB, List.isChain_cons_cons, ih2, and_assoc] lemma wx_clear (g : Input) (p : List (Nat × Nat)) : clearPathB g p = true ↔ IsClearPath g p := by simp [clearPathB, IsClearPath, List.Chain', wx_chain, and_assoc] lemma wx_root (g : Input) (r : Output) (dom : ∀ p, IsClearPath g p → ∃ q ∈ (genRevPaths g (g.length*g.length)).map List.reverse, IsClearPath g q ∧ q.length ≤ p.length) : shortestClearPath_check g r ↔ shortestClearPath_spec g r := by classical simp only [shortestClearPath_check, Bool.and_eq_true, Bool.or_eq_true, Bool.not_eq_true', List.any_eq_false, List.any_eq_true, List.all_eq_true, beq_iff_eq, decide_eq_true_eq, Bool.eq_false_iff, wx_clear] simp only [ne_eq, List.any_eq_true, wx_clear, not_exists, not_and] constructor · rintro ⟨hcase, hlo⟩ have lower : ∀ p, IsClearPath g p → r ≤ (p.length : Int) := by intro p hp obtain ⟨q, hq, hclear, hlen⟩ := dom p hp have := (hlo q hq).resolve_left (not_not_intro hclear) exact le_trans this (by exact_mod_cast hlen) refine ⟨?_, lower⟩ rcases hcase with ⟨hn, hr⟩ | ⟨p, hm, hp, hr⟩ · left refine ⟨?_, hr⟩ rintro ⟨p, hp⟩ obtain ⟨q, hm, hq, _⟩ := dom p hp exact hn q hm hq · exact Or.inr ⟨p, hp, hr⟩ · rintro ⟨hcase, hlo⟩ refine ⟨?_, fun p hm => ?_⟩ · rcases hcase with ⟨hn, hr⟩ | ⟨p, hp, hr⟩ · exact Or.inl ⟨fun p _ hp => hn ⟨p, hp⟩, hr⟩ · obtain ⟨q, hm, hq, hlen⟩ := dom p hp refine Or.inr ⟨q, hm, hq, ?_⟩ have hlow := hlo q hq have : (q.length : Int) ≤ (p.length : Int) := by exact_mod_cast hlen exact le_antisymm (hr ▸ this) hlow · by_cases hp : IsClearPath g p · exact Or.inr (hlo p hp) · exact Or.inl hp lemma wx_gen (g : Input) (fuel : Nat) (p : List (Nat × Nat)) (hlast : p.getLast? = some (0,0)) (hchain : p.IsChain (fun a b => a ≠ b ∧ Nat.dist a.1 b.1 ≤ 1 ∧ Nat.dist a.2 b.2 ≤ 1)) (hnd : p.Nodup) (hcells : ∀ c ∈ p, c.1 < g.length ∧ c.2 < g.length ∧ (g[c.1]?.bind fun row => row[c.2]?) = some 0) (hlen : p.length ≤ fuel + 1) : p ∈ genRevPaths g fuel := by induction fuel generalizing p with | zero => cases p with | nil => simp at hlast | cons a l => have : l = [] := by simpa using hlen subst l simp only [List.getLast?_singleton, Option.some.injEq] at hlast subst a simp [genRevPaths] | succ fuel ih => cases p with | nil => simp at hlast | cons a l => cases l with | nil => apply List.mem_append_left exact ih [a] hlast hchain hnd hcells (by simp) | cons b l => have ht : b :: l ∈ genRevPaths g fuel := by apply ih (b :: l) · simpa using hlast · exact (List.isChain_cons_cons.mp hchain).2 · exact hnd.of_cons · intro c hc; exact hcells c (List.mem_cons_of_mem a hc) · simp only [List.length_cons] at hlen ⊢; omega apply List.mem_append_right apply List.mem_flatMap.mpr refine ⟨b :: l, ht, ?_⟩ have ha := hcells a (by simp) have hab := (List.isChain_cons_cons.mp hchain).1 have hn := (List.nodup_cons.mp hnd).1 simp only [pathExtensions, List.mem_map, List.mem_filter, List.mem_product, List.mem_range, Bool.and_eq_true, decide_eq_true_eq, Bool.not_eq_true', List.contains_eq_mem, decide_eq_false_iff_not, beq_iff_eq] refine ⟨a, ⟨List.pair_mem_product.mpr ⟨List.mem_range.mpr ha.1, List.mem_range.mpr ha.2.1⟩, ?_⟩, rfl⟩ exact ⟨⟨⟨⟨Ne.symm hab.1, by simpa [Nat.dist_comm] using hab.2.1⟩, by simpa [Nat.dist_comm] using hab.2.2⟩, hn⟩, ha.2.2⟩ lemma wx_cells (g : Input) (hv : isValidInput g) (c : Nat × Nat) (hc : (g[c.1]?.bind fun row => row[c.2]?) = some 0) : c.1 < g.length ∧ c.2 < g.length := by have hrows : ∀ row ∈ g, row.length = g.length := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, beq_iff_eq, Bool.or_eq_true] at hv exact fun row hr => (hv.2 row hr).1 cases he : g[c.1]? with | none => simp [he] at hc | some row => have hr := List.getElem?_eq_some_iff.mp he have hcol : row[c.2]? = some 0 := by simpa [he] using hc have hcolb := (List.getElem?_eq_some_iff.mp hcol).1 have hrowlen := hrows row (List.mem_of_getElem? he) exact ⟨hr.1, hrowlen ▸ hcolb⟩ lemma wx_enumerated (g : Input) (hv : isValidInput g) (q : List (Nat × Nat)) (hq : IsClearPath g q) (hnd : q.Nodup) : q ∈ (genRevPaths g (g.length*g.length)).map List.reverse := by have hcells : ∀ c ∈ q, c.1 < g.length ∧ c.2 < g.length ∧ (g[c.1]?.bind fun row => row[c.2]?) = some 0 := by intro c hc have ho := hq.2.2.1 c hc exact ⟨(wx_cells g hv c ho).1, (wx_cells g hv c ho).2, ho⟩ have hbound : q.length ≤ g.length * g.length := by rw [← List.toFinset_card_of_nodup hnd] have hs : q.toFinset ⊆ (Finset.range g.length) ×ˢ (Finset.range g.length) := by intro c hc have hh := hcells c (List.mem_toFinset.mp hc) exact Finset.mem_product.mpr ⟨Finset.mem_range.mpr hh.1, Finset.mem_range.mpr hh.2.1⟩ simpa using Finset.card_le_card hs apply List.mem_map.mpr refine ⟨q.reverse, ?_, List.reverse_reverse q⟩ apply wx_gen · simpa using hq.1 · apply List.isChain_reverse.mpr have hch : q.IsChain (fun a b => a ≠ b ∧ Nat.dist a.1 b.1 ≤ 1 ∧ Nat.dist a.2 b.2 ≤ 1) := hq.2.2.2 apply hch.imp intro a b hab exact ⟨Ne.symm hab.1, by simpa [Nat.dist_comm] using hab.2.1, by simpa [Nat.dist_comm] using hab.2.2⟩ · simpa only [List.nodup_reverse] using hnd · intro c hc exact hcells c (List.mem_reverse.mp hc) · simp only [List.length_reverse] omega /-- On valid input the checker accepts exactly the specified outputs. -/ theorem shortestClearPath_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : shortestClearPath_check input result ↔ shortestClearPath_spec input result := by apply wx_root intro p hp obtain ⟨q, hq, hnd, hlen⟩ := wx_shorten input p hp exact ⟨q, wx_enumerated input h q hq hnd, hq, hlen⟩ /-! ### Implementation helpers -/ /-- Whether `p` lies inside `grid` and holds a 0. -/ def isOpenCell (grid : List (List Nat)) (p : Nat × Nat) : Bool := (grid[p.1]?.bind fun row => row[p.2]?) == some 0 /-- Cells of `l` where `p` holds, in order. -/ def passCells (p : (Nat × Nat) → Bool) : List (Nat × Nat) → List (Nat × Nat) | [] => [] | c :: cs => if p c then c :: passCells p cs else passCells p cs /-- Cells of `l` where `p` fails, in order. -/ def dropCells (p : (Nat × Nat) → Bool) : List (Nat × Nat) → List (Nat × Nat) | [] => [] | c :: cs => if p c then dropCells p cs else c :: dropCells p cs /-- Whether `c` is an open cell 8-directionally adjacent to some frontier cell of the `n × n` grid. -/ def bfsCond (grid : List (List Nat)) (n : Nat) (frontier : List (Nat × Nat)) (c : Nat × Nat) : Bool := isOpenCell grid c && (frontier.flatMap fun f => let rows := (f.1 :: (f.1 + 1) :: (if f.1 = 0 then [] else [f.1 - 1])).filter (· < n) let cols := (f.2 :: (f.2 + 1) :: (if f.2 = 0 then [] else [f.2 - 1])).filter (· < n) (rows.product cols).filter fun d => !(d == f)).contains c /-- Level-order BFS: the frontier's distance to `(n-1, n-1)` through open cells, with `rem` the cells not yet on any frontier. -/ def bfsLevel (grid : List (List Nat)) (n : Nat) (frontier rem : List (Nat × Nat)) (dist : Nat) : Int := if frontier.isEmpty then -1 else if frontier.contains (n - 1, n - 1) then (dist : Int) else match h : passCells (bfsCond grid n frontier) rem with | [] => -1 | y :: yes => bfsLevel grid n (y :: yes) (dropCells (bfsCond grid n frontier) rem) (dist + 1) termination_by rem.length decreasing_by have dec : ∀ (p : (Nat × Nat) → Bool) (l : List (Nat × Nat)), (dropCells p l).length ≤ l.length ∧ ((passCells p l).isEmpty = false → (dropCells p l).length < l.length) := by intro p l induction l with | nil => simp only [passCells, dropCells, List.length_nil] exact ⟨Nat.le_refl 0, fun h => absurd h (by decide)⟩ | cons c cs ih => obtain ⟨ihle, ihlt⟩ := ih by_cases hc : p c = true · simp only [passCells, dropCells, if_pos hc, List.length_cons] exact ⟨Nat.le_succ_of_le ihle, fun _ => Nat.lt_succ_of_le ihle⟩ · simp only [passCells, dropCells, if_neg hc, List.length_cons] exact ⟨Nat.succ_le_succ ihle, fun h => Nat.succ_lt_succ (ihlt h)⟩ have hne : (passCells (bfsCond grid n frontier) rem).isEmpty = false := by rw [h] rfl exact (dec (bfsCond grid n frontier) rem).2 hne /-! ### Main algorithm (impl) -/ /-- Shortest clear-path length by breadth-first search level by level from `(0, 0)`. -/ def findShortestClearPath (input : Input) : Output := let n := input.length if n = 0 then -1 else if !isOpenCell input (0, 0) || !isOpenCell input (n - 1, n - 1) then -1 else let rem := ((List.range n).product (List.range n)).filter fun c => !(c == (0, 0)) bfsLevel input n [(0, 0)] rem 1 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findShortestClearPath_correct (input : Input) (h : isValidInput input) : shortestClearPath_spec input (findShortestClearPath input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [[0, 1], [1, 0]] #guard isValidInput [[0, 0, 0], [1, 1, 0], [1, 1, 0]] #guard isValidInput [[1, 0, 0], [1, 1, 0], [1, 1, 0]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [[0, 1], [0, 1, 0]]) #guard !(isValidInput [[0, 0], [0, 2]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard shortestClearPath_check [[0, 1], [1, 0]] 2 #guard shortestClearPath_check [[0, 0, 0], [1, 1, 0], [1, 1, 0]] 4 #guard shortestClearPath_check [[1, 0, 0], [1, 1, 0], [1, 1, 0]] (-1) /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(shortestClearPath_check [[0, 1], [1, 0]] 1) #guard !(shortestClearPath_check [[0, 0, 0], [1, 1, 0], [1, 1, 0]] 2) #guard !(shortestClearPath_check [[1, 0, 0], [1, 1, 0], [1, 1, 0]] 0) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findShortestClearPath [[0, 1], [1, 0]] == 2 #guard findShortestClearPath [[0, 0, 0], [1, 1, 0], [1, 1, 0]] == 4 #guard findShortestClearPath [[1, 0, 0], [1, 1, 0], [1, 1, 0]] == -1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard shortestClearPath_check [[0, 1], [1, 0]] (findShortestClearPath [[0, 1], [1, 0]]) #guard shortestClearPath_check [[0, 0, 0], [1, 1, 0], [1, 1, 0]] (findShortestClearPath [[0, 0, 0], [1, 1, 0], [1, 1, 0]]) #guard shortestClearPath_check [[1, 0, 0], [1, 1, 0], [1, 1, 0]] (findShortestClearPath [[1, 0, 0], [1, 1, 0], [1, 1, 0]]) end PShortestPathInBinaryMatrix