import Mathlib /-! # Minimum Path Sum Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. ## Constraints - m == grid.length - n == grid[i].length - 1 <= m, n <= 200 - 0 <= grid[i][j] <= 200 ## Provided examples - `grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]` → `7` - `grid = [[1, 2, 3], [4, 5, 6]]` → `12` - `grid = [[1]]` → `1` ## Synthesized negative examples - invalid input: `grid = []` ([structural] a predicate that admits 1 <= m, n <= 200. empty grid: m below minimum) - invalid input: `grid = [[0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0]]` ([structural] a predicate that admits 1 <= m, n <= 200. 201 rows: one past m maximum) - invalid input: `grid = [[1, 2], [3]]` ([structural] a predicate that admits n == grid[i].length. ragged rows: not an m x n grid) - `grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]` → `9` is wrong ([structural] minimality stated as achievability alone. path via (2,0) sums 9 but is not least) - `grid = [[1, 2, 3], [4, 5, 6]]` → `14` is wrong ([structural] minimality stated as achievability alone. 14 is attainable by a valid path but not minimal) - `grid = [[1]]` → `2` is wrong ([structural] counts the single cell twice as both start and end. true path cost is 1) -/ namespace PMinimumPathSum abbrev Input := List (List Nat) abbrev Output := Nat /-! ### Specification helpers -/ /-- `path` visits positions of `grid` from the top-left cell to the bottom-right cell, each step moving one cell right or one cell down, with every position inside the grid. -/ def IsValidPath (grid : List (List Nat)) (path : List (Nat × Nat)) : Prop := path.head? = some (0, 0) ∧ path.getLast? = some (grid.length - 1, (grid.headD []).length - 1) ∧ (∀ pos ∈ path, pos.1 < grid.length ∧ pos.2 < (grid.headD []).length) ∧ path.Chain' (fun p q => q = (p.1 + 1, p.2) ∨ q = (p.1, p.2 + 1)) /-- Sum of the grid values at the positions visited by `path`. -/ def PathCost (grid : List (List Nat)) (path : List (Nat × Nat)) : Nat := (path.map (fun p => (grid.getD p.1 []).getD p.2 0)).sum /-! ### Validity predicate (V) -/ /-- Valid input: a rectangular grid of 1 to 200 rows and 1 to 200 columns whose cell values are all at most 200. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 200 && input.all (fun row => row.length == (input.headD []).length && 1 ≤ row.length && row.length ≤ 200 && row.all (· ≤ 200)) /-! ### Ideal specification (P_spec) -/ /-- `result` is the least cell-value sum attained by any valid path through `input`: some path achieves it and no path does better. -/ def minPathSum_spec (input : Input) (result : Output) : Prop := IsLeast {k | ∃ path : List (Nat × Nat), IsValidPath input path ∧ PathCost input path = k} result /-! ### Decidable specification (P_check) -/ /-- One monotone step: down one cell when `down` is true, otherwise right one cell. -/ def stepPos (pos : Nat × Nat) (down : Bool) : Nat × Nat := if down then (pos.1 + 1, pos.2) else (pos.1, pos.2 + 1) /-- The position list traced from `pos` by following the remaining moves. -/ def tracePath : Nat × Nat → List Bool → List (Nat × Nat) | pos, [] => [pos] | pos, m :: ms => pos :: tracePath (stepPos pos m) ms /-- The path from the top-left cell selected by the down/right move code `code`. -/ def decodePath (grid : Input) (code : Fin (grid.length + (grid.headD []).length - 2) → Bool) : List (Nat × Nat) := tracePath (0, 0) ((List.finRange (grid.length + (grid.headD []).length - 2)).map code) /-- All move codes of length `n`, as lists of down/right flags. -/ def allBoolLists : Nat → List (List Bool) | 0 => [[]] | n + 1 => let rest := allBoolLists n rest.map (false :: ·) ++ rest.map (true :: ·) /-- Boolean counterpart of `IsValidPath`: the path starts at the top-left cell, ends at the bottom-right cell, stays inside the grid, and moves only right or down. -/ def isValidPathBool (grid : List (List Nat)) (path : List (Nat × Nat)) : Bool := path.head? == some (0, 0) && path.getLast? == some (grid.length - 1, (grid.headD []).length - 1) && path.all (fun pos => decide (pos.1 < grid.length) && decide (pos.2 < (grid.headD []).length)) && (path.zip path.tail).all (fun (p, q) => q == (p.1 + 1, p.2) || q == (p.1, p.2 + 1)) /-- Executable checker for `minPathSum_spec` over the finite move codes. -/ def minPathSum_check (input : Input) (result : Output) : Bool := let numMoves := input.length + (input.headD []).length - 2 let paths := (allBoolLists numMoves).map (fun bits => tracePath (0, 0) bits) let validCosts := (paths.filter (isValidPathBool input)).map (PathCost input) validCosts.any (· == result) && validCosts.all (fun c => decide (result ≤ c)) lemma root_of_bridges (input : Input) (result : Output) (bridge : ∀ path, path ∈ ((allBoolLists (input.length + (input.headD []).length - 2)).map (tracePath (0, 0))).filter (isValidPathBool input) ↔ IsValidPath input path) : minPathSum_check input result ↔ minPathSum_spec input result := by simp only [minPathSum_check, Bool.and_eq_true, List.any_eq_true, List.all_eq_true, beq_iff_eq, decide_eq_true_eq, List.mem_map, minPathSum_spec, IsLeast, Set.mem_setOf_eq, lowerBounds] constructor · rintro ⟨⟨k, ⟨p, hp, rfl⟩, he⟩, hall⟩ exact ⟨⟨p, (bridge p).mp hp, he⟩, fun k ⟨q, hq, hcost⟩ => hall k ⟨q, (bridge q).mpr hq, hcost⟩⟩ · rintro ⟨⟨p, hp, he⟩, hall⟩ exact ⟨⟨PathCost input p, ⟨p, (bridge p).mpr hp, rfl⟩, he⟩, fun k ⟨q, hq, hcost⟩ => hall ⟨q, (bridge q).mp hq, hcost⟩⟩ lemma bits_mem (n : Nat) (bits : List Bool) : bits ∈ allBoolLists n ↔ bits.length = n := by induction n generalizing bits with | zero => cases bits <;> simp [allBoolLists] | succ n ih => cases bits with | nil => simp [allBoolLists] | cons b bs => cases b <;> simp [allBoolLists, ih] lemma zip_chain (path : List (Nat × Nat)) : (path.zip path.tail).all (fun (p, q) => q == (p.1 + 1, p.2) || q == (p.1, p.2 + 1)) = true ↔ path.Chain' (fun p q => q = (p.1 + 1, p.2) ∨ q = (p.1, p.2 + 1)) := by induction path using List.twoStepInduction with | nil => simp [List.Chain'] | singleton p => simp [List.Chain'] | cons_cons p q ps ih ihcons => simpa [List.Chain', List.isChain_cons_cons, Bool.or_eq_true, beq_iff_eq] using and_congr (Iff.rfl : (q = (p.1 + 1, p.2) ∨ q = (p.1, p.2 + 1)) ↔ _) (ihcons q) lemma valid_reflect (grid : Input) (path : List (Nat × Nat)) : isValidPathBool grid path = true ↔ IsValidPath grid path := by simp only [isValidPathBool, IsValidPath, Bool.and_eq_true, beq_iff_eq, List.all_eq_true, decide_eq_true_eq] rw [← zip_chain] simp only [List.all_eq_true, and_assoc] lemma reconstruct (ps : List (Nat × Nat)) (p e : Nat × Nat) (hc : (p :: ps).Chain' (fun p q => q = (p.1 + 1, p.2) ∨ q = (p.1, p.2 + 1))) (he : (p :: ps).getLast? = some e) : ∃ bits, tracePath p bits = p :: ps ∧ bits.length + p.1 + p.2 = e.1 + e.2 := by induction ps generalizing p with | nil => have hp : p = e := by simpa using he subst e exact ⟨[], rfl, by simp⟩ | cons q qs ih => have hc' := (List.isChain_cons_cons.mp hc) obtain ⟨bits, hb, hn⟩ := ih q hc'.2 (by simpa using he) rcases hc'.1 with hq | hq · refine ⟨true :: bits, ?_, ?_⟩ · simp only [tracePath, stepPos, Bool.true_eq, ↓reduceIte, ← hq, hb] · simp only [List.length_cons] rw [hq] at hn dsimp at hn omega · refine ⟨false :: bits, ?_, ?_⟩ · simp only [tracePath, stepPos, Bool.false_eq_true, ↓reduceIte, ← hq, hb] · simp only [List.length_cons] rw [hq] at hn dsimp at hn omega lemma paths_bridge (input : Input) (_h : isValidInput input) (path : List (Nat × Nat)) : path ∈ ((allBoolLists (input.length + (input.headD []).length - 2)).map (tracePath (0, 0))).filter (isValidPathBool input) ↔ IsValidPath input path := by rw [List.mem_filter, valid_reflect] constructor · exact And.right · intro hp refine ⟨?_, hp⟩ cases path with | nil => simpa [IsValidPath] using hp | cons p ps => have hp0 : p = (0, 0) := by simpa using hp.1 subst p obtain ⟨bits, hb, hn⟩ := reconstruct ps (0, 0) (input.length - 1, (input.headD []).length - 1) hp.2.2.2 hp.2.1 have hbounds := hp.2.2.1 (0, 0) (by simp) have hlen : bits.length = input.length + (input.headD []).length - 2 := by dsimp at hn hbounds omega exact List.mem_map.mpr ⟨bits, (bits_mem _ _).mpr hlen, hb⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem minPathSum_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : minPathSum_check input result ↔ minPathSum_spec input result := by exact root_of_bridges input result (paths_bridge input h) /-! ### Implementation helpers -/ /-- Prefix sums of the first grid row, giving the initial DP row. -/ def firstRowPrefixSums (row : List Nat) : List Nat := match row with | [] => [] | r :: rs => let step := fun (acc : Nat × List Nat) (x : Nat) => let cur := acc.1 + x (cur, cur :: acc.2) (rs.foldl step (r, [r])).2.reverse /-- One DP row from a grid row and the previous row's minimal sums. -/ def rowMinPathSums (row prev : List Nat) : List Nat := match row, prev with | [], _ => [] | r :: rs, p :: ps => let first := r + p let step := fun (acc : Nat × List Nat) (cell : Nat × Nat) => let cur := cell.1 + Nat.min cell.2 acc.1 (cur, cur :: acc.2) ((rs.zip ps).foldl step (first, [first])).2.reverse | _ :: _, [] => [] /-! ### Main algorithm (impl) -/ /-- Minimum path sum by row-by-row dynamic programming keeping only the previous row. -/ def computeMinPathSum (input : Input) : Output := match input with | [] => 0 | firstRow :: rest => let firstCosts := firstRowPrefixSums firstRow let finalCosts := rest.foldl (fun prev row => rowMinPathSums row prev) firstCosts finalCosts.reverse.headD 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem computeMinPathSum_correct (input : Input) (h : isValidInput input) : minPathSum_spec input (computeMinPathSum input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [[1, 3, 1], [1, 5, 1], [4, 2, 1]] #guard isValidInput [[1, 2, 3], [4, 5, 6]] #guard isValidInput [[1]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [[0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0], [0]]) #guard !(isValidInput [[1, 2], [3]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard minPathSum_check [[1, 3, 1], [1, 5, 1], [4, 2, 1]] 7 #guard minPathSum_check [[1, 2, 3], [4, 5, 6]] 12 #guard minPathSum_check [[1]] 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(minPathSum_check [[1, 3, 1], [1, 5, 1], [4, 2, 1]] 9) #guard !(minPathSum_check [[1, 2, 3], [4, 5, 6]] 14) #guard !(minPathSum_check [[1]] 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard computeMinPathSum [[1, 3, 1], [1, 5, 1], [4, 2, 1]] == 7 #guard computeMinPathSum [[1, 2, 3], [4, 5, 6]] == 12 #guard computeMinPathSum [[1]] == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard minPathSum_check [[1, 3, 1], [1, 5, 1], [4, 2, 1]] (computeMinPathSum [[1, 3, 1], [1, 5, 1], [4, 2, 1]]) #guard minPathSum_check [[1, 2, 3], [4, 5, 6]] (computeMinPathSum [[1, 2, 3], [4, 5, 6]]) #guard minPathSum_check [[1]] (computeMinPathSum [[1]]) end PMinimumPathSum