import Mathlib /-! # Cherry Pickup You are given an n x n grid representing a field of cherries, each cell is one of three possible integers. 0 means the cell is empty, so you can pass through, 1 means the cell contains a cherry that you can pick up and pass through, or -1 means the cell contains a thorn that blocks your way. Return the maximum number of cherries you can collect by following the rules below: Starting at the position (0, 0) and reaching (n - 1, n - 1) by moving right or down through valid path cells (cells with value 0 or 1). After reaching (n - 1, n - 1), returning to (0, 0) by moving left or up through valid path cells. When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell 0. If there is no valid path between (0, 0) and (n - 1, n - 1), then no cherries can be collected. ## Constraints - n == grid.length - n == grid[i].length - 1 <= n <= 50 - grid[i][j] is -1, 0, or 1. - grid[0][0] != -1 - grid[n - 1][n - 1] != -1 ## Provided examples - `grid = [[0, 1, -1], [1, 0, -1], [1, 1, 1]]` → `5` - `grid = [[1, 1, -1], [1, -1, 1], [-1, 1, 1]]` → `0` - `grid = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]` → `0` ## Synthesized negative examples - invalid input: `grid = [[0, 0]]` ([structural] a predicate that admits n == grid[i].length. one row of width two where square is required; a rectangle-only predicate accepts it) - invalid input: `grid = []` ([structural] a predicate that admits 1 <= n <= 50. empty grid has n = 0; a predicate checking only cell values accepts it) - invalid input: `grid = [[2]]` ([structural] a predicate that admits grid[i][j] is -1, 0, or 1.. 2 outside the allowed set; a predicate checking only for -1 accepts it) - `grid = [[0, 1, -1], [1, 0, -1], [1, 1, 1]]` → `4` is wrong ([structural] the return trip requirement is omitted. maximum for the outbound trip alone is 4) - `grid = [[1, 1, -1], [1, -1, 1], [-1, 1, 1]]` → `2` is wrong ([structural] maximum stated without requiring the answer to be attainable. No valid path exists, so no path collects 2.) - `grid = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]` → `12` is wrong ([structural] counts passable cells as cherries rather than only 1-valued cells. a round trip covers 12 distinct cells, none containing a cherry) -/ namespace PCherryPickup abbrev Input := List (List Int) abbrev Output := Nat /-! ### Specification helpers -/ /-- The value of the cell at position `c` in `grid`, or `0` when `c` lies outside it. -/ def cellValue (grid : List (List Int)) (c : Nat × Nat) : Int := (grid[c.1]?.bind fun row => row[c.2]?).getD 0 /-- `path` walks from `(0, 0)` to `(n - 1, n - 1)` by single right or down steps through non-thorn cells. -/ def IsValidForwardPath (grid : List (List Int)) (path : List (Nat × Nat)) : Prop := path.head? = some (0, 0) ∧ path.getLast? = some (grid.length - 1, grid.length - 1) ∧ path.Chain' (fun a b => b = (a.1 + 1, a.2) ∨ b = (a.1, a.2 + 1)) ∧ ∀ c ∈ path, c.1 < grid.length ∧ c.2 < grid.length ∧ cellValue grid c ≠ -1 /-- Both lists are valid forward paths, the return trip being the second read in reverse, and `count` is the number of distinct cherry cells either visits. -/ def CollectsFromRoundTrip (grid : List (List Int)) (fwd back : List (Nat × Nat)) (count : Nat) : Prop := IsValidForwardPath grid fwd ∧ IsValidForwardPath grid back ∧ ((fwd.toFinset ∪ back.toFinset).filter (fun c => cellValue grid c = 1)).card = count /-! ### Validity predicate (V) -/ /-- Valid input: a square grid of side 1 to 50 whose cells are -1, 0 or 1, with thorn-free corners. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 50 && input.all (fun row => row.length == input.length) && input.all (fun row => row.all (fun cell => cell == -1 || cell == 0 || cell == 1)) && (input[0]?.bind fun row => row[0]?) != some (-1) && (input[input.length - 1]?.bind fun row => row[input.length - 1]?) != some (-1) /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest cherry count any round trip collects, with `0` always attainable so a grid with no valid round trip answers `0`. -/ def maxCherries_spec (input : Input) (result : Output) : Prop := IsGreatest {k | k = 0 ∨ ∃ fwd back : List (Nat × Nat), CollectsFromRoundTrip input fwd back k} result /-! ### Decidable specification (P_check) -/ /-- All binary move words of the requested length. -/ def allBinarySequences : Nat → List (List Bool) | 0 => [[]] | remaining + 1 => (allBinarySequences remaining).flatMap (fun moves => [false :: moves, true :: moves]) /-- The forward path obtained by reading `false` as right and `true` as down from `start`. -/ def decodeForwardPathFrom (start : Nat × Nat) : List Bool → List (Nat × Nat) | [] => [start] | false :: moves => start :: decodeForwardPathFrom (start.1, start.2 + 1) moves | true :: moves => start :: decodeForwardPathFrom (start.1 + 1, start.2) moves /-- The forward path obtained from a move word starting at `(0, 0)`. -/ def decodeForwardPath (moves : List Bool) : List (Nat × Nat) := decodeForwardPathFrom (0, 0) moves /-- The move word of a forward path, with `true` recording each down step. -/ def encodeForwardPath (path : List (Nat × Nat)) : List Bool := (path.zip path.tail).map (fun (a, b) => decide (b = (a.1 + 1, a.2))) /-- Boolean test deciding the `IsValidForwardPath` conditions on a concrete path. -/ def isValidForwardPathBool (grid : Input) (path : List (Nat × Nat)) : Bool := path.head? == some (0, 0) && path.getLast? == some (grid.length - 1, grid.length - 1) && (path.zip path.tail).all (fun (a, b) => b == (a.1 + 1, a.2) || b == (a.1, a.2 + 1)) && path.all (fun c => decide (c.1 < grid.length) && decide (c.2 < grid.length) && cellValue grid c != -1) /-- The valid forward paths named by binary move words for `grid`. -/ def forwardPathCandidates (grid : Input) : List (List (Nat × Nat)) := ((allBinarySequences (2 * (grid.length - 1))).map decodeForwardPath).filter (isValidForwardPathBool grid) /-- The number of distinct cherry cells visited by either of two paths. -/ def roundTripCount (grid : Input) (fwd back : List (Nat × Nat)) : Nat := ((fwd.toFinset ∪ back.toFinset).filter (fun c => cellValue grid c = 1)).card /-- Decidable greatest-count test obtained by enumerating the finite move words. -/ def maxCherries_check (input : Input) (result : Output) : Bool := let paths := forwardPathCandidates input (result == 0 || paths.any (fun fwd => paths.any (fun back => roundTripCount input fwd back == result))) && paths.all (fun fwd => paths.all (fun back => decide (roundTripCount input fwd back ≤ result))) lemma cp_steps_bool (path : List (Nat × Nat)) : (path.zip path.tail).all (fun (a, b) => b == (a.1 + 1, a.2) || b == (a.1, a.2 + 1)) = true ↔ path.Chain' (fun a b => b = (a.1 + 1, a.2) ∨ b = (a.1, a.2 + 1)) := by induction path with | nil => simp [List.Chain'] | cons a path ih => cases path with | nil => simp [List.Chain'] | cons b path => simpa only [List.tail_cons, List.zip_cons_cons, List.all_cons, Bool.and_eq_true, beq_iff_eq, Bool.or_eq_true, List.Chain', List.isChain_cons_cons] using and_congr (by simp only [beq_iff_eq, Bool.or_eq_true]) ih lemma cp_valid_bool (grid : Input) (path : List (Nat × Nat)) : isValidForwardPathBool grid path = true ↔ IsValidForwardPath grid path := by unfold isValidForwardPathBool IsValidForwardPath simp only [Bool.and_eq_true, beq_iff_eq] rw [cp_steps_bool] simp only [List.all_eq_true, Bool.and_eq_true, decide_eq_true_eq, bne_iff_ne] grind only [] lemma cp_binary_mem (n : Nat) (moves : List Bool) : moves ∈ allBinarySequences n ↔ moves.length = n := by induction n generalizing moves with | zero => cases moves <;> simp [allBinarySequences] | succ n ih => cases moves with | nil => simp [allBinarySequences] | cons b bs => cases b <;> simp [allBinarySequences, ih] lemma cp_encode_length (a : Nat × Nat) (tail : List (Nat × Nat)) : (encodeForwardPath (a :: tail)).length = tail.length := by simp [encodeForwardPath] lemma cp_decode_encode (a : Nat × Nat) (tail : List (Nat × Nat)) : (a :: tail).Chain' (fun x y => y = (x.1 + 1, x.2) ∨ y = (x.1, x.2 + 1)) → decodeForwardPathFrom a (encodeForwardPath (a :: tail)) = a :: tail := by induction tail generalizing a with | nil => simp [encodeForwardPath, decodeForwardPathFrom] | cons b tail ih => intro hc have hab := (List.isChain_cons_cons.mp hc).1 have ht := (List.isChain_cons_cons.mp hc).2 rcases hab with rfl | rfl · simpa [encodeForwardPath, decodeForwardPathFrom] using ih (a.1 + 1, a.2) ht · simpa [encodeForwardPath, decodeForwardPathFrom] using ih (a.1, a.2 + 1) ht lemma cp_chain_endpoint_sum (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))) (hlast : (a :: tail).getLast? = some z) : z.1 + z.2 = a.1 + a.2 + tail.length := by induction tail generalizing a with | nil => simpa using (congrArg (fun q => q.map (fun p : Nat × Nat => p.1 + p.2)) hlast).symm | cons b tail ih => have hab := (List.isChain_cons_cons.mp hc).1 have ht := (List.isChain_cons_cons.mp hc).2 have hlast' : (b :: tail).getLast? = some z := by simpa using hlast have hi := ih b ht hlast' rcases hab with rfl | rfl <;> simp_all <;> omega lemma cp_path_complete (grid : List (List Int)) (path : List (Nat × Nat)) : IsValidForwardPath grid path → ∃ moves, moves.length = 2 * (grid.length - 1) ∧ decodeForwardPath moves = path := by intro hv rcases hv with ⟨hhead, hlast, hchain, hcells⟩ cases path with | nil => simp at hhead | cons a tail => have ha : a = (0, 0) := by simpa using hhead subst a refine ⟨encodeForwardPath ((0, 0) :: tail), ?_, ?_⟩ · rw [cp_encode_length] have hs := cp_chain_endpoint_sum (0, 0) (grid.length - 1, grid.length - 1) tail hchain hlast simp only [Prod.fst, Prod.snd, Nat.zero_add] at hs omega · simpa [decodeForwardPath] using cp_decode_encode (0, 0) tail hchain theorem cp_collects_iff (grid : Input) (fwd back : List (Nat × Nat)) (k : Nat) : CollectsFromRoundTrip grid fwd back k ↔ IsValidForwardPath grid fwd ∧ IsValidForwardPath grid back ∧ roundTripCount grid fwd back = k := Iff.rfl theorem cp_root (input : Input) (result : Output) (bridge : ∀ p, p ∈ forwardPathCandidates input ↔ IsValidForwardPath input p) : maxCherries_check input result ↔ maxCherries_spec input result := by simp only [maxCherries_check, maxCherries_spec, Bool.and_eq_true, Bool.or_eq_true, beq_iff_eq, List.any_eq_true, List.all_eq_true, decide_eq_true_eq, IsGreatest, upperBounds, Set.mem_setOf_eq, bridge, cp_collects_iff] grind only [] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem maxCherries_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : maxCherries_check input result ↔ maxCherries_spec input result := by apply cp_root intro p simp only [forwardPathCandidates, List.mem_filter, List.mem_map, cp_valid_bool] constructor · exact fun hp => hp.2 · intro hp obtain ⟨moves, hlen, hdecode⟩ := cp_path_complete input p hp exact ⟨⟨moves, (cp_binary_mem _ _).2 hlen, hdecode⟩, hp⟩ /-! ### Implementation helpers -/ /-- One DP layer: for each row pair at step `t`, take the best reachable predecessor from the previous layer and add the cherries at the two current cells, counting shared cells once, with `-1` marking unreachable pairs. -/ def maxCherriesAtStep (grid : List (List Int)) (t : Nat) (prev : Array (Array Int)) : Array (Array Int) := let n := grid.length (List.range n).foldl (fun rows r1 => rows.push ((List.range n).foldl (fun row r2 => let c1 := t - r1 let c2 := t - r2 if r1 ≤ t ∧ r2 ≤ t ∧ c1 < n ∧ c2 < n ∧ cellValue grid (r1, c1) ≠ -1 ∧ cellValue grid (r2, c2) ≠ -1 then let prevValue (a b : Nat) : Int := (prev[a]?.bind fun r => r[b]?).getD (-1) let best := max (max (prevValue r1 r2) (prevValue r1 (r2 - 1))) (max (prevValue (r1 - 1) r2) (prevValue (r1 - 1) (r2 - 1))) if best < 0 then row.push (-1) else let gained := cellValue grid (r1, c1) + if r1 = r2 then 0 else cellValue grid (r2, c2) row.push (best + gained) else row.push (-1)) (#[] : Array Int))) (#[] : Array (Array Int)) /-! ### Main algorithm (impl) -/ /-- Maximum cherries by two-walker lockstep dynamic programming over the forward trip: after `t` moves each walker sits at row `r` and column `t - r`, and an `n × n` table keeps the best count for every row pair. -/ def cherryPickup (input : Input) : Output := let n := input.length if n = 0 then 0 else let start : Array (Array Int) := (List.range n).foldl (fun rows r1 => rows.push ((List.range n).foldl (fun row r2 => row.push (if r1 = 0 ∧ r2 = 0 ∧ cellValue input (0, 0) ≠ -1 then cellValue input (0, 0) else -1)) (#[] : Array Int))) (#[] : Array (Array Int)) let final := (List.range (2 * (n - 1))).foldl (fun prev i => maxCherriesAtStep input (i + 1) prev) start ((final[n - 1]?.bind fun r => r[n - 1]?).getD (-1)).toNat /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem cherryPickup_correct (input : Input) (h : isValidInput input) : maxCherries_spec input (cherryPickup input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [[0, 1, (-1)], [1, 0, (-1)], [1, 1, 1]] #guard isValidInput [[1, 1, (-1)], [1, (-1), 1], [(-1), 1, 1]] #guard isValidInput [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput [[0, 0]]) #guard !(isValidInput []) #guard !(isValidInput [[2]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard maxCherries_check [[0, 1, (-1)], [1, 0, (-1)], [1, 1, 1]] 5 #guard maxCherries_check [[1, 1, (-1)], [1, (-1), 1], [(-1), 1, 1]] 0 #guard maxCherries_check [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] 0 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(maxCherries_check [[0, 1, (-1)], [1, 0, (-1)], [1, 1, 1]] 4) #guard !(maxCherries_check [[1, 1, (-1)], [1, (-1), 1], [(-1), 1, 1]] 2) #guard !(maxCherries_check [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] 12) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard cherryPickup [[0, 1, (-1)], [1, 0, (-1)], [1, 1, 1]] == 5 #guard cherryPickup [[1, 1, (-1)], [1, (-1), 1], [(-1), 1, 1]] == 0 #guard cherryPickup [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] == 0 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard maxCherries_check [[0, 1, (-1)], [1, 0, (-1)], [1, 1, 1]] (cherryPickup [[0, 1, (-1)], [1, 0, (-1)], [1, 1, 1]]) #guard maxCherries_check [[1, 1, (-1)], [1, (-1), 1], [(-1), 1, 1]] (cherryPickup [[1, 1, (-1)], [1, (-1), 1], [(-1), 1, 1]]) #guard maxCherries_check [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] (cherryPickup [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]) end PCherryPickup