import Mathlib /-! # Unique Paths Ii You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time. An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle. Return the number of possible unique paths that the robot can take to reach the bottom-right corner. The testcases are generated so that the answer will be less than or equal to 2 * 109. ## Constraints - m == obstacleGrid.length - n == obstacleGrid[i].length - 1 <= m, n <= 100 - obstacleGrid[i][j] is 0 or 1. ## Provided examples - `obstacleGrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]` → `2` - `obstacleGrid = [[0, 1], [0, 0]]` → `1` - `obstacleGrid = [[1]]` → `0` ## Synthesized negative examples - invalid input: `obstacleGrid = []` ([structural] a predicate that admits 1 <= m, n <= 100. empty outer list; no rows at all) - invalid input: `obstacleGrid = [[0, 0], [0]]` ([structural] a predicate that admits n == obstacleGrid[i].length. row lengths differ; a predicate checking values only accepts it) - invalid input: `obstacleGrid = [[2]]` ([structural] a predicate that admits obstacleGrid[i][j] is 0 or 1.. 2 outside stated set; predicate checking only ==1 treats it as free) - `obstacleGrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]` → `3` is wrong ([structural] count is one above the true value. accepts a spec whose path count is off by one) - `obstacleGrid = [[0, 1], [0, 0]]` → `0` is wrong ([structural] zero returned whenever any obstacle exists; no search required. valid path exists but answer is 0) - `obstacleGrid = [[1]]` → `1` is wrong ([structural] obstacle restriction is dropped. start equals end, empty path counted despite obstacle) -/ namespace PUniquePathsIi abbrev Input := List (List Nat) abbrev Output := Nat /-! ### Specification helpers -/ /-- `path` is a route from the top-left cell of `grid` to the bottom-right cell, moving only down or right and stepping only on cells that hold 0. -/ def IsPath (grid : List (List Nat)) (path : List (Nat × Nat)) : Prop := path.head? = some (0, 0) ∧ path.getLast? = some (grid.length - 1, (grid.head?.map List.length).getD 0 - 1) ∧ path.Chain' (fun a b => b = (a.1 + 1, a.2) ∨ b = (a.1, a.2 + 1)) ∧ ∀ c ∈ path, (grid[c.1]?).bind (fun row => row[c.2]?) = some 0 /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty grid of at most 100 rows, all rows sharing one common length between 1 and 100, and every cell equal to 0 or 1. -/ def isValidInput (input : Input) : Bool := match input with | [] => false | row₀ :: _ => input.length ≤ 100 && input.all (fun row => row.length == row₀.length) && 1 ≤ row₀.length && row₀.length ≤ 100 && input.all (fun row => row.all (fun c => c == 0 || c == 1)) /-! ### Ideal specification (P_spec) -/ /-- `result` is the number of valid paths through `input`: some finite collection of paths has cardinality `result` and contains a path exactly when it is a valid path of `input`. -/ def uniquePathsWithObstacles_spec (input : Input) (result : Output) : Prop := ∃ S : Finset (List (Nat × Nat)), S.card = result ∧ ∀ p : List (Nat × Nat), p ∈ S ↔ IsPath input p /-! ### Decidable specification (P_check) -/ /-- The number of moves in any down/right path across `grid`: `rows - 1` down moves plus `cols - 1` right moves. -/ def moveCount (grid : List (List Nat)) : Nat := grid.length + (grid.head?.map List.length).getD 0 - 2 /-- All `2^k` move codes of length `k`; `true` steps down and `false` steps right. -/ def allMoveCodes : (k : Nat) → List (List Bool) | 0 => [[]] | k + 1 => (allMoveCodes k).flatMap fun code => [true :: code, false :: code] /-- The cells visited by walking from `(0, 0)` according to `moves`, starting cell included. -/ def walkPath (moves : List Bool) : List (Nat × Nat) := moves.scanl (fun cell down => if down then (cell.1 + 1, cell.2) else (cell.1, cell.2 + 1)) (0, 0) /-- Boolean form of the specification's step relation along a cell list. -/ def stepChain : List (Nat × Nat) → Bool | [] => true | [_] => true | a :: b :: rest => (b == (a.1 + 1, a.2) || b == (a.1, a.2 + 1)) && stepChain (b :: rest) /-- Boolean form of `IsPath`: the same four clauses, decided against the grid. -/ def isPathB (grid : List (List Nat)) (path : List (Nat × Nat)) : Bool := path.head? == some (0, 0) && path.getLast? == some (grid.length - 1, (grid.head?.map List.length).getD 0 - 1) && stepChain path && path.all fun c => (grid[c.1]?).bind (fun row => row[c.2]?) == some 0 /-- Executable checker for `uniquePathsWithObstacles_spec`: count the move codes whose walked path is valid and compare with `result`. -/ def uniquePathsWithObstacles_check (input : Input) (result : Output) : Bool := ((allMoveCodes (moveCount input)).filter fun code => isPathB input (walkPath code)).length == result lemma wc_mem_codes (k : Nat) (code : List Bool) : code ∈ allMoveCodes k ↔ code.length = k := by induction k generalizing code with | zero => cases code <;> simp [allMoveCodes] | succ k ih => cases code with | nil => simp [allMoveCodes] | cons b bs => cases b <;> simp [allMoveCodes, ih] lemma wc_encode_chain (a z : Nat × Nat) (tail : List (Nat × Nat)) (hc : (a :: tail).Chain' (fun x y => y = (x.1 + 1, x.2) ∨ y = (x.1, x.2 + 1))) (hl : (a :: tail).getLast? = some z) : ∃ code : List Bool, List.scanl (fun cell down => if down then (cell.1 + 1, cell.2) else (cell.1, cell.2 + 1)) a code = a :: tail ∧ a.1 + a.2 + code.length = z.1 + z.2 := by induction tail generalizing a z with | nil => simp at hl subst z exact ⟨[], by simp, by simp⟩ | cons b rest ih => have hc' : (b = (a.1 + 1, a.2) ∨ b = (a.1, a.2 + 1)) ∧ (b :: rest).Chain' (fun x y => y = (x.1 + 1, x.2) ∨ y = (x.1, x.2 + 1)) := by simpa [List.Chain'] using hc have hs : b = (a.1 + 1, a.2) ∨ b = (a.1, a.2 + 1) := by exact hc'.1 have ht : (b :: rest).Chain' (fun x y => y = (x.1 + 1, x.2) ∨ y = (x.1, x.2 + 1)) := hc'.2 have hl' : (b :: rest).getLast? = some z := by simpa using hl obtain ⟨code, hwalk, hlen⟩ := ih b z ht hl' rcases hs with hdown | hright · subst b refine ⟨true :: code, ?_, ?_⟩ · simp only [List.scanl_cons, if_true, Prod.fst, Prod.snd] simpa using congrArg (List.cons a) hwalk · simp only [List.length_cons] omega · subst b refine ⟨false :: code, ?_, ?_⟩ · simp only [List.scanl_cons, if_false, Prod.fst, Prod.snd] simpa using congrArg (List.cons a) hwalk · simp only [List.length_cons] omega theorem wx_coverage (grid : Input) (hv : isValidInput grid) (p : List (Nat × Nat)) (hp : IsPath grid p) : ∃ code ∈ allMoveCodes (moveCount grid), walkPath code = p := by rcases hp with ⟨hhead, hlast, hchain, hfree⟩ cases p with | nil => simp at hhead | cons a tail => simp at hhead subst a obtain ⟨code, hwalk, hlen⟩ := wc_encode_chain (0, 0) (grid.length - 1, (grid.head?.map List.length).getD 0 - 1) tail hchain hlast have hcode : code.length = moveCount grid := by cases grid with | nil => simp [isValidInput] at hv | cons row rows => have hpos : 1 ≤ row.length := by simp [isValidInput] at hv omega simp only [moveCount, List.length_cons, List.head?_cons, Option.map_some, Option.getD_some, Prod.fst, Prod.snd] at hlen ⊢ omega refine ⟨code, (wc_mem_codes _ _).2 hcode, ?_⟩ exact hwalk theorem wx_root (reflect : ∀ g p, isPathB g p = true ↔ IsPath g p) (nd : ∀ n, ((allMoveCodes n).map walkPath).Nodup) (cover : ∀ (g : Input), isValidInput g → ∀ p, IsPath g p → ∃ c ∈ allMoveCodes (moveCount g), walkPath c = p) (input : Input) (result : Output) (h : isValidInput input) : uniquePathsWithObstacles_check input result ↔ uniquePathsWithObstacles_spec input result := by classical let L := ((allMoveCodes (moveCount input)).filter (fun c => isPathB input (walkPath c))).map walkPath have hn : L.Nodup := by dsimp [L] simpa only [List.filter_map, Function.comp_def] using (nd (moveCount input)).filter (isPathB input) have hm : ∀ p, p ∈ L.toFinset ↔ IsPath input p := by intro p simp only [List.mem_toFinset, L, List.mem_map, List.mem_filter] constructor · rintro ⟨c, ⟨hc, hb⟩, rfl⟩ exact (reflect _ _).mp hb · intro hp obtain ⟨c, hc, rfl⟩ := cover input h p hp exact ⟨c, ⟨hc, (reflect _ _).mpr hp⟩, rfl⟩ have card : L.toFinset.card = ((allMoveCodes (moveCount input)).filter (fun c => isPathB input (walkPath c))).length := by rw [List.toFinset_card_of_nodup hn] exact List.length_map _ simp only [uniquePathsWithObstacles_check, beq_iff_eq] constructor · intro he exact ⟨L.toFinset, card.trans he, hm⟩ · rintro ⟨S, hs, hmS⟩ have e : S = L.toFinset := Finset.ext fun p => (hmS p).trans (hm p).symm simpa only [e, card] using hs theorem wx_step (p : List (Nat × Nat)) : stepChain p = true ↔ p.Chain' (fun a b => b = (a.1 + 1, a.2) ∨ b = (a.1, a.2 + 1)) := by induction p with | nil => simp [stepChain, List.Chain'] | cons a p ih => cases p with | nil => simp [stepChain, List.Chain'] | cons b p => simp only [stepChain, Bool.and_eq_true, Bool.or_eq_true, beq_iff_eq, List.Chain', List.isChain_cons_cons] exact and_congr_right (fun _ => ih) theorem wx_reflect (g : Input) (p : List (Nat × Nat)) : isPathB g p = true ↔ IsPath g p := by simp [isPathB, IsPath, wx_step, and_assoc] theorem wx_codes_nd (n : Nat) : (allMoveCodes n).Nodup := by induction n with | zero => simp [allMoveCodes] | succ n ih => rw [allMoveCodes, List.nodup_flatMap] refine ⟨?_, ih.imp ?_⟩ · intro x hx simp · intro a b hab simp only [Function.onFun, List.disjoint_left, List.mem_cons, List.not_mem_nil, or_false] intro x hx hy rcases hx with rfl | rfl <;> simp_all theorem wx_scan_inj (xs ys : List Bool) (a : Nat × Nat) (h : xs.scanl (fun cell down => if down then (cell.1 + 1, cell.2) else (cell.1, cell.2 + 1)) a = ys.scanl (fun cell down => if down then (cell.1 + 1, cell.2) else (cell.1, cell.2 + 1)) a) : xs = ys := by induction xs generalizing ys a with | nil => have hh := congrArg List.length h simpa using hh.symm | cons x xs ih => cases ys with | nil => have hh := congrArg List.length h simp at hh | cons y ys => simp only [List.scanl_cons, List.cons.injEq, true_and] at h have hh := congrArg List.head? h cases x <;> cases y · exact congrArg (false :: ·) (ih ys _ h) · simp at hh · simp at hh · exact congrArg (true :: ·) (ih ys _ h) theorem wx_nodup (n : Nat) : ((allMoveCodes n).map walkPath).Nodup := by apply (wx_codes_nd n).map intro xs ys h exact wx_scan_inj xs ys (0, 0) h /-- On valid input the checker accepts exactly the specified outputs. -/ theorem uniquePathsWithObstacles_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : uniquePathsWithObstacles_check input result ↔ uniquePathsWithObstacles_spec input result := by exact wx_root wx_reflect wx_nodup wx_coverage input result h /-! ### Implementation helpers -/ /-- Path counts along a row reachable only from the left: `carry` propagates until an obstacle, after which every cell is 0. -/ def firstRowCounts (carry : Nat) : List Nat → List Nat | [] => [] | c :: cs => if c == 1 then 0 :: firstRowCounts 0 cs else carry :: firstRowCounts carry cs /-- One DP row from the previous row's counts: each cell is 0 for an obstacle, otherwise the left count plus the count from above. -/ def nextRowCounts (left : Nat) : List Nat → List Nat → List Nat | [], _ => [] | _, [] => [] | up :: ups, c :: cs => let cur := if c == 1 then 0 else left + up cur :: nextRowCounts cur ups cs /-- The bottom-right cell count: the last entry of the final DP row, 0 if that row is empty. -/ def lastCount : List Nat → Nat | [] => 0 | [x] => x | _ :: xs => lastCount xs /-! ### Main algorithm (impl) -/ /-- Number of valid paths by dynamic programming over the rows, keeping only the previous row's counts. -/ def countUniquePaths (input : Input) : Output := match input with | [] => 0 | row₀ :: rows => let first := firstRowCounts 1 row₀ let final := rows.foldl (fun prev row => nextRowCounts 0 prev row) first lastCount final /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem countUniquePaths_correct (input : Input) (h : isValidInput input) : uniquePathsWithObstacles_spec input (countUniquePaths input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [[0, 0, 0], [0, 1, 0], [0, 0, 0]] #guard isValidInput [[0, 1], [0, 0]] #guard isValidInput [[1]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [[0, 0], [0]]) #guard !(isValidInput [[2]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard uniquePathsWithObstacles_check [[0, 0, 0], [0, 1, 0], [0, 0, 0]] 2 #guard uniquePathsWithObstacles_check [[0, 1], [0, 0]] 1 #guard uniquePathsWithObstacles_check [[1]] 0 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(uniquePathsWithObstacles_check [[0, 0, 0], [0, 1, 0], [0, 0, 0]] 3) #guard !(uniquePathsWithObstacles_check [[0, 1], [0, 0]] 0) #guard !(uniquePathsWithObstacles_check [[1]] 1) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard countUniquePaths [[0, 0, 0], [0, 1, 0], [0, 0, 0]] == 2 #guard countUniquePaths [[0, 1], [0, 0]] == 1 #guard countUniquePaths [[1]] == 0 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard uniquePathsWithObstacles_check [[0, 0, 0], [0, 1, 0], [0, 0, 0]] (countUniquePaths [[0, 0, 0], [0, 1, 0], [0, 0, 0]]) #guard uniquePathsWithObstacles_check [[0, 1], [0, 0]] (countUniquePaths [[0, 1], [0, 0]]) #guard uniquePathsWithObstacles_check [[1]] (countUniquePaths [[1]]) end PUniquePathsIi