import Mathlib /-! # Unique Paths There is a robot on an m x n grid. The robot is 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. Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner. The test cases are generated so that the answer will be less than or equal to 2 * 109. ## Constraints - 1 <= m, n <= 100 ## Provided examples - `m = 3, n = 7` → `28` - `m = 3, n = 2` → `3` - `m = 1, n = 1` → `1` ## Synthesized negative examples - invalid input: `m = 0, n = 1` ([structural] a predicate that admits 1 <= m, n <= 100. m one below the floor; catches a predicate that forgot the lower bound.) - invalid input: `m = 1, n = 0` ([structural] a predicate that admits 1 <= m, n <= 100. n one below the floor; catches a predicate that forgot n's lower bound.) - invalid input: `m = 101, n = 1` ([structural] a predicate that admits 1 <= m, n <= 100. m one above the ceiling; catches a predicate that forgot the upper bound.) - `m = 3, n = 7` → `29` is wrong ([structural] off-by-one in the final count adds one path. count is one greater than the true number of paths) - `m = 3, n = 2` → `2` is wrong ([structural] counts paths for a grid one row shorter than the stated dimensions. 2x2 grid has two paths, one short of 3x2) - `m = 1, n = 1` → `2` is wrong ([structural] binomial coefficient uses m+n and m rather than m+n-2 and m-1. formula C(2,1)=2 instead of C(0,0)=1) -/ namespace PUniquePaths abbrev Input := (Nat) × (Nat) abbrev Output := Nat /-! ### Specification helpers -/ /-- One cell follows another by a single downward or rightward move. -/ def IsStep (fromCell toCell : Nat × Nat) : Prop := (toCell.1 = fromCell.1 + 1 ∧ toCell.2 = fromCell.2) ∨ (toCell.1 = fromCell.1 ∧ toCell.2 = fromCell.2 + 1) /-- A path visits in-bounds cells from the top-left to the bottom-right by downward and rightward steps. -/ def IsPath (m n : Nat) (path : List (Nat × Nat)) : Prop := path.head? = some (0, 0) ∧ path.getLast? = some (m - 1, n - 1) ∧ List.Chain' IsStep path ∧ ∀ cell ∈ path, cell.1 < m ∧ cell.2 < n /-! ### Validity predicate (V) -/ /-- Valid input consists of grid dimensions from 1 through 100. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1 && input.1 ≤ 100 && 1 ≤ input.2 && input.2 ≤ 100 /-! ### Ideal specification (P_spec) -/ /-- `result` is the cardinality of a finite collection containing exactly the valid paths. -/ def uniquePaths_spec (input : Input) (result : Output) : Prop := ∃ paths : Finset (List (Nat × Nat)), paths.card = result ∧ ∀ path, path ∈ paths ↔ IsPath input.1 input.2 path /-! ### Decidable specification (P_check) -/ /-- The choices of `count` positions from `positions`, preserving their order. -/ def choosePositions : Nat → List Nat → List (List Nat) | 0, _ => [[]] | _ + 1, [] => [] | count + 1, position :: positions => ((choosePositions count positions).map (fun chosen => position :: chosen)) ++ choosePositions (count + 1) positions /-- The subsets of move positions on which a path moves downward. -/ def downMoveSubsets (m n : Nat) : List (List Nat) := choosePositions (m - 1) (List.range (m + n - 2)) /-- The path obtained by moving downward at the selected positions and rightward otherwise. -/ def decodePath (total : Nat) (downMoves : List Nat) : List (Nat × Nat) := List.scanl (fun cell move => if move ∈ downMoves then (cell.1 + 1, cell.2) else (cell.1, cell.2 + 1)) (0, 0) (List.range total) /-- Boolean check that one cell follows another by a single downward or rightward move. -/ def isStepBool (fromCell toCell : Nat × Nat) : Bool := (toCell.1 == fromCell.1 + 1 && toCell.2 == fromCell.2) || (toCell.1 == fromCell.1 && toCell.2 == fromCell.2 + 1) /-- Boolean check that every consecutive pair of cells is a single downward or rightward step. -/ def isChainBool : List (Nat × Nat) → Bool | [] => true | [_] => true | first :: second :: rest => isStepBool first second && isChainBool (second :: rest) /-- The Boolean realization of the specification's path predicate. -/ def isPathBool (m n : Nat) (path : List (Nat × Nat)) : Bool := path.head? == some (0, 0) && path.getLast? == some (m - 1, n - 1) && isChainBool path && path.all (fun cell => decide (cell.1 < m) && decide (cell.2 < n)) /-- Every encoded candidate that satisfies the specification's path predicate. -/ def validPaths (m n : Nat) : List (List (Nat × Nat)) := ((downMoveSubsets m n).map (decodePath (m + n - 2))).filter (fun path => isPathBool m n path) /-- Executable checker for `uniquePaths_spec` over paths encoded by their downward moves. -/ def uniquePaths_check (input : Input) (result : Output) : Bool := let enumeratedPaths := validPaths input.1 input.2 let paths := enumeratedPaths.toFinset decide (paths.card = result) && enumeratedPaths.all (fun path => isPathBool input.1 input.2 path) lemma wx_chain (p : List (Nat × Nat)) : isChainBool p = true ↔ List.Chain' IsStep p := by induction p using isChainBool.induct with | case1 => simp [isChainBool, List.Chain'] | case2 a => simp [isChainBool, List.Chain'] | case3 a b t ih => simp_all [isChainBool, isStepBool, IsStep, List.Chain'] lemma wx_path (m n : Nat) (p : List (Nat × Nat)) : isPathBool m n p = true ↔ IsPath m n p := by simp [isPathBool, IsPath, wx_chain, List.all_eq_true, and_assoc] lemma root_of_bridges (coverage : ∀ m n p, IsPath m n p → p ∈ (downMoveSubsets m n).map (decodePath (m+n-2))) (input : Input) (result : Output) : uniquePaths_check input result ↔ uniquePaths_spec input result := by have mem (p) : p ∈ (validPaths input.1 input.2).toFinset ↔ IsPath input.1 input.2 p := by simp only [List.mem_toFinset, validPaths, List.mem_filter, wx_path] exact ⟨And.right, fun hp => ⟨coverage _ _ _ hp, hp⟩⟩ have hall : (validPaths input.1 input.2).all (fun p => isPathBool input.1 input.2 p) = true := by apply List.all_eq_true.mpr intro p hp exact (List.mem_filter.mp hp).2 simp only [uniquePaths_check, Bool.and_eq_true, decide_eq_true_eq, hall, and_true] constructor · intro hc exact ⟨_, hc, mem⟩ · rintro ⟨ps, hc, hm⟩ have he : ps = (validPaths input.1 input.2).toFinset := Finset.ext (fun p => (hm p).trans (mem p).symm) simpa [he] using hc def wx_encode (a : Nat × Nat) : List (Nat × Nat) → Nat → List Nat | [], _ => [] | b :: bs, k => if b.1 = a.1 + 1 then k :: wx_encode b bs (k+1) else wx_encode b bs (k+1) lemma wx_encode_sub (a : Nat × Nat) (t : List (Nat × Nat)) (k : Nat) : (wx_encode a t k).Sublist (List.range' k t.length) := by induction t generalizing a k with | nil => simp [wx_encode] | cons b bs ih => simp only [wx_encode, List.length_cons, List.range'_succ] split · exact (ih b (k+1)).cons_cons k · exact (ih b (k+1)).cons k lemma wx_encode_lower (a : Nat × Nat) (t : List (Nat × Nat)) (k i : Nat) (hi : i ∈ wx_encode a t k) : k ≤ i := by have := (wx_encode_sub a t k).subset hi obtain ⟨j, hj, hij⟩ := List.mem_range'.mp this omega lemma wx_metrics (a b : Nat × Nat) (t : List (Nat × Nat)) (k : Nat) (hc : List.Chain' IsStep (a::t)) (he : (a::t).getLast? = some b) : (wx_encode a t k).length + a.1 = b.1 ∧ t.length + a.1 + a.2 = b.1 + b.2 := by induction t generalizing a k with | nil => simp only [List.getLast?_singleton, Option.some.injEq] at he subst b simp [wx_encode] | cons c cs ih => have hh : IsStep a c ∧ List.Chain' IsStep (c::cs) := by simpa [List.Chain'] using hc have ht := ih c (k+1) hh.2 (by simpa using he) rcases hh.1 with hd | hr · simp only [wx_encode, hd.1, if_pos, List.length_cons] constructor <;> omega · have hn : ¬ c.1 = a.1 + 1 := by omega simp only [wx_encode, hn, if_false, List.length_cons] constructor <;> omega lemma wx_scan (a : Nat × Nat) (t : List (Nat × Nat)) (k : Nat) (hc : List.Chain' IsStep (a::t)) (extra : List Nat) (hl : ∀ i ∈ extra, i < k) : List.scanl (fun (c : Nat × Nat) i => if i ∈ extra ++ wx_encode a t k then (c.1+1,c.2) else (c.1,c.2+1)) a (List.range' k t.length) = a :: t := by induction t generalizing a k extra with | nil => simp | cons b bs ih => have hh : IsStep a b ∧ List.Chain' IsStep (b::bs) := by simpa [List.Chain'] using hc have hn : k ∉ extra := by intro hm; have := hl k hm; omega have ht : k ∉ wx_encode b bs (k+1) := by intro hm have := wx_encode_lower b bs (k+1) k hm omega rcases hh.1 with hd | hr · have hb : (a.1+1,a.2) = b := by exact Prod.ext hd.1.symm hd.2.symm have hp : ∀ i ∈ extra ++ [k], i < k+1 := by intro i hi simp only [List.mem_append, List.mem_singleton] at hi rcases hi with hi | rfl · have := hl i hi; omega · omega have hi := ih b (k+1) hh.2 (extra ++ [k]) hp simp only [wx_encode, hd.1, if_pos, List.length_cons, List.range'_succ, List.scanl_cons] simp only [List.mem_append, List.mem_cons, true_or, or_true, if_true, hb] congr 1 simpa only [List.append_assoc, List.singleton_append, List.mem_append, List.mem_cons] using hi · have hd : ¬ b.1 = a.1 + 1 := by omega have hb : (a.1,a.2+1) = b := by exact Prod.ext hr.1.symm hr.2.symm have hp : ∀ i ∈ extra, i < k+1 := by intro i hi; have := hl i hi; omega have hi := ih b (k+1) hh.2 extra hp simp only [wx_encode, hd, if_false, List.length_cons, List.range'_succ, List.scanl_cons] simp only [List.mem_append, hn, ht, or_self, if_false, hb] simpa only [List.mem_append] using congrArg (List.cons a) hi lemma wx_coverage_of_choose (choose : ∀ (k : Nat) (xs ys : List Nat), ys ∈ choosePositions k xs ↔ ys.Sublist xs ∧ ys.length = k) (m n : Nat) (p : List (Nat × Nat)) (hp : IsPath m n p) : p ∈ (downMoveSubsets m n).map (decodePath (m+n-2)) := by cases p with | nil => simp [IsPath] at hp | cons a t => have ha : a = (0,0) := by simpa using hp.1 subst a have hb := hp.2.2.2 (0,0) (by simp) have hm := wx_metrics (0,0) (m-1,n-1) t 0 hp.2.2.1 hp.2.1 have hlen : t.length = m+n-2 := by simp only [Prod.fst, Prod.snd] at hb hm; omega have hcount : (wx_encode (0,0) t 0).length = m-1 := by simpa using hm.1 apply List.mem_map.mpr refine ⟨wx_encode (0,0) t 0, ?_, ?_⟩ · apply (choose _ _ _).mpr constructor · simpa only [downMoveSubsets, List.range_eq_range', ← hlen] using wx_encode_sub (0,0) t 0 · exact hcount · have hs := wx_scan (0,0) t 0 hp.2.2.1 [] (by simp) simp only [List.nil_append] at hs rw [decodePath, List.range_eq_range', ← hlen] convert hs using 1 congr 1 lemma wx_choose : ∀ (k : Nat) (xs ys : List Nat), ys ∈ choosePositions k xs ↔ ys.Sublist xs ∧ ys.length = k := by intro k xs induction xs generalizing k with | nil => cases k with | zero => intro ys simp [choosePositions] | succ k => intro ys cases ys <;> simp [choosePositions] | cons a xs ih => cases k <;> intro ys · cases ys <;> simp [choosePositions] · cases ys <;> simp [choosePositions, ih, List.sublist_cons_iff] <;> grind only [] lemma wx_coverage (m n : Nat) (p : List (Nat × Nat)) (hp : IsPath m n p) : p ∈ (downMoveSubsets m n).map (decodePath (m+n-2)) := wx_coverage_of_choose wx_choose m n p hp /-- On valid input the checker accepts exactly the specified outputs. -/ theorem uniquePaths_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : uniquePaths_check input result ↔ uniquePaths_spec input result := by exact root_of_bridges wx_coverage input result /-! ### Implementation helpers -/ /-- The all-ones first row of the DP table, of length `n`. -/ def firstRow (n : Nat) : List Nat := List.replicate n 1 /-- The DP row below `row`: first entry 1, each later entry the entry above plus the entry to its left. -/ def nextRow (row : List Nat) : List Nat := match row with | [] => [] | _ :: tail => List.scanl (fun acc above => acc + above) 1 tail /-- Iterates `nextRow` over `remaining` further rows, returning the bottom row. -/ def buildRows : Nat → List Nat → List Nat | 0, row => row | remaining + 1, row => buildRows remaining (nextRow row) /-! ### Main algorithm (impl) -/ /-- Unique paths by row-by-row dynamic programming: each cell is the cell above plus the cell to its left. -/ def uniquePathsImpl (input : Input) : Output := ((buildRows (input.1 - 1) (firstRow input.2)).getLast?).getD 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem uniquePathsImpl_correct (input : Input) (h : isValidInput input) : uniquePaths_spec input (uniquePathsImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (3, 7) #guard isValidInput (3, 2) #guard isValidInput (1, 1) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (0, 1)) #guard !(isValidInput (1, 0)) #guard !(isValidInput (101, 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard uniquePaths_check (3, 7) 28 #guard uniquePaths_check (3, 2) 3 #guard uniquePaths_check (1, 1) 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(uniquePaths_check (3, 7) 29) #guard !(uniquePaths_check (3, 2) 2) #guard !(uniquePaths_check (1, 1) 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard uniquePathsImpl (3, 7) == 28 #guard uniquePathsImpl (3, 2) == 3 #guard uniquePathsImpl (1, 1) == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard uniquePaths_check (3, 7) (uniquePathsImpl (3, 7)) #guard uniquePaths_check (3, 2) (uniquePathsImpl (3, 2)) #guard uniquePaths_check (1, 1) (uniquePathsImpl (1, 1)) end PUniquePaths